{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:50.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/08a113c9ba5068bf2d2473373124f573?v\u003d1714808378\" alt\u003d\"/problems/harvard/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eThe term “Harvard architecture” applies to a computer\n that has physically separate memories for instructions and\n data. The term originated with the Harvard Mark I computer,\n delivered by IBM in 1944, which used paper tape for\n instructions and relays for data.\n\n \u003cp\u003eSome modern microcontrollers use the Harvard architecture –\n but not paper tape and relays! Data memory is organized in\n banks, each containing the same number of data items. Each\n data-referencing instruction has a byte offset \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e to a bank, and a bit \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e that is used to select the bank to\n be referenced. If \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e, then bank\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e is referenced. If\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e is \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, then the value in a \u003cem\u003ebank\n select register\u003c/em\u003e (BSR) identifies the bank to be used.\n Assume each instruction takes the same time to execute, and\n there is an instruction that can set the BSR’s value.\u003c/p\u003e\n\n \u003cp\u003eFor example, suppose there are \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e banks of \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e bytes each. To access location\n \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e, either use a single\n instruction with \u003cspan class\u003d\"tex2jax_process\"\u003e$a \u003d 0$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$f \u003d 5$\u003c/span\u003e, or set the\n BSR to \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e in one\n instruction and then use an instruction with \u003cspan class\u003d\"tex2jax_process\"\u003e$a \u003d 1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$f \u003d 5$\u003c/span\u003e. The first approach is faster\n since it does not require setting the BSR.\u003c/p\u003e\n\n \u003cp\u003eNow suppose (with the same memory) the location to access is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e. Only one approach\n will work here: execute an instruction that sets the BSR to\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e (unless the BSR\n already has the value \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e)\n and then use an instruction with \u003cspan class\u003d\"tex2jax_process\"\u003e$a \u003d 1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$f \u003d 4$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eA \u003cem\u003eprogram\u003c/em\u003e is a sequence of operations. Each\n operation is either\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003ea variable reference, written as \u003ctt class\u003d\"ttfamily\"\u003eV\u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e\u003c/tt\u003e,\n where \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e is a\n positive integer, or\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003ea repetition, written as \u003ctt class\u003d\"ttfamily\"\u003eR\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n \u0026lt;program\u0026gt; E\u003c/tt\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e is a positive integer and\n \u003ctt class\u003d\"ttfamily\"\u003e\u0026lt;program\u0026gt;\u003c/tt\u003e is an arbitrary\n program. This operation is equivalent to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e sequential occurrences of\n \u003ctt class\u003d\"ttfamily\"\u003e\u0026lt;program\u0026gt;\u003c/tt\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eYour problem is to determine the minimum running time of\n programs. In particular, given the number and size of the\n memory banks and a program to be executed, find the minimum\n number of instructions (which reference memory location and\n possibly set the BSR) that must be executed to run the program.\n To do this you must identify a mapping of variables to memory\n banks that yields the smallest execution time, and report that\n execution time – that is, the number of memory references and\n BSR register settings required. The BSR’s value is initially\n undefined, and changes only when an instruction explicitly sets\n its value.\u003c/p\u003e\n\n \u003cp\u003e\u003cbr\u003e\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. A test case\n consists of two lines. The first line contains two integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le b \\le 13$\u003c/span\u003e is the number of\n memory banks and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le s \\le\n 13$\u003c/span\u003e is the number of variables that can be stored in\n each memory bank. The second line contains a non-empty program\n with at most \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\, 000$\u003c/span\u003e\n space-separated elements (each \u003ctt class\u003d\"ttfamily\"\u003eR\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\u003c/tt\u003e,\n \u003ctt class\u003d\"ttfamily\"\u003eV\u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e\u003c/tt\u003e, and \u003ctt class\u003d\"ttfamily\"\u003eE\u003c/tt\u003e counts as one element).\u003c/p\u003e\n\n \u003cp\u003eYou may assume the following:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eIn a repetition \u003ctt class\u003d\"ttfamily\"\u003eR\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\u003c/tt\u003e, the number of\n repetitions satisfies \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le\n n \\le 10^6$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eIn a loop operation \u003ctt class\u003d\"ttfamily\"\u003eR\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e \u0026lt;program\u0026gt; E\u003c/tt\u003e, the\n loop body \u003ctt class\u003d\"ttfamily\"\u003e\u0026lt;program\u0026gt;\u003c/tt\u003e is not\n empty.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eIn a variable reference \u003ctt class\u003d\"ttfamily\"\u003eV\u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e\u003c/tt\u003e,\n the variable index satisfies \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le i \\le \\min (b \\cdot s,\n 13)$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThe total number of variable references performed by an\n execution of the program is at most \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{12}$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the minimum number of instructions that must be\n executed to complete the program.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\nV1 V2 V1 V1 V2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1\nV1 V2 V1 V1 V2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\nR10 V1 V2 V1 E\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e30\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 4\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 1\nV1 R2 V2 V4 R2 V1 E V3 E\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}