{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"8d012aba-5660-517c-a422-491ddbbe9c59","task_key":"ICPC~2dWorld~2dFinals--examples--2013~5fE","task_revision_id":"3","upstream_id":"2013_E","short_description":"Harvard","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem Description\\n\\nThe term **“Harvard architecture”** applies to a computer that has physically separate memories for instructions and data. The term originated with the Harvard Mark I computer, delivered by IBM in 1944, which used paper tape for instructions and relays for data.\\n\\nSome modern microcontrollers use the Harvard architecture – but not paper tape and relays! Data memory is organized in banks, each containing the same number of data items. Each data-referencing instruction has a byte offset \\\\( f \\\\) to a bank, and a bit \\\\( a \\\\) that is used to select the bank to be referenced. If \\\\( a = 0 \\\\), then bank 0 is referenced. If \\\\( a = 1 \\\\), then the value in a bank select register (BSR) identifies the bank to be used. Assume each instruction takes the same time to execute, and there is an instruction that can set the BSR’s value.\\n\\nFor example, suppose there are 4 banks of 8 bytes each. To access location 5, either use a single instruction with \\\\( a = 0 \\\\) and \\\\( f = 5 \\\\), or set the BSR to 0 in one instruction and then use an instruction with \\\\( a = 1 \\\\) and \\\\( f = 5 \\\\). The first approach is faster since it does not require setting the BSR.\\n\\nNow suppose (with the same memory) the location to access is 20. Only one approach will work here: execute an instruction that sets the BSR to 2 (unless the BSR already has the value 2) and then use an instruction with \\\\( a = 1 \\\\) and \\\\( f = 4 \\\\).\\n\\nA program is a sequence of operations. Each operation is either:\\n\\n- A variable reference, written as \\\\( V_i \\\\), where \\\\( i \\\\) is a positive integer, or\\n- A repetition, written as \\\\( R_n <\\\\text{program}> E \\\\), where \\\\( n \\\\) is a positive integer and \\\\<program\\\\> is an arbitrary program. This operation is equivalent to \\\\( n \\\\) sequential occurrences of \\\\<program\\\\>.\\n\\nYour problem is to determine the minimum running time of programs. In particular, given the number and size of the memory banks and a program to be executed, find the minimum number of instructions (which reference memory location and possibly set the BSR) that must be executed to run the program.\\n\\nTo do this you must identify a mapping of variables to memory banks that yields the smallest execution time, and report that execution time – that is, the number of memory references and BSR register settings required. The BSR’s value is initially undefined, and changes only when an instruction explicitly sets its value.\\n\\n## Input\\n\\nThe input consists of a single test case. A test case consists of two lines. The first line contains two integers \\\\( b \\\\) and \\\\( s \\\\), where \\\\( 1 \\\\leq b \\\\leq 13 \\\\) is the number of memory banks and \\\\( 1 \\\\leq s \\\\leq 13 \\\\) is the number of variables that can be stored in each memory bank. The second line contains a non-empty program with at most 1000 space-separated elements (each \\\\( R_n \\\\), \\\\( V_i \\\\), and \\\\( E \\\\) counts as one element).\\n\\nYou may assume the following:\\n\\n- In a repetition \\\\( R_n \\\\), the number of repetitions satisfies \\\\( 1 \\\\leq n \\\\leq 10^6 \\\\).\\n- In a loop operation \\\\( R_n <\\\\text{program}> E \\\\), the loop body \\\\<program\\\\> is not empty.\\n- In a variable reference \\\\( V_i \\\\), the variable index satisfies \\\\( 1 \\\\leq i \\\\leq \\\\min(b \\\\cdot s, 13) \\\\).\\n- The total number of variable references performed by an execution of the program is at most \\\\( 10^{12} \\\\).\\n\\n## Output\\n\\nDisplay the minimum number of instructions that must be executed to complete the program.\\n\\n## Sample Input/Output\\n\\n```\\nSample Input 1\\n1 2\\nV1 V2 V1 V1 V2\\n\\nSample Output 1\\n5\\n```\\n\\n```\\nSample Input 2\\n2 1\\nV1 V2 V1 V1 V2\\n\\nSample Output 2\\n6\\n```\\n\\n```\\nSample Input 3\\n1 2\\nR10 V1 V2 V1 E\\n\\nSample Output 3\\n30\\n```\\n\\n```\\nSample Input 4\\n4 1\\nV1 R2 V2 V4 R2 V1 E V3 E\\n\\nSample Output 4\\n17\\n```\",\"question_title\":\"Harvard\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}