題目 1957:
藍(lán)橋杯算法提高VIP-Harvard
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 3 解決: 0
題目描述
“哈佛結(jié)構(gòu)”是指一臺(tái)擁有多個(gè)分散內(nèi)存用于記錄指令與數(shù)據(jù)的計(jì)算機(jī)。這個(gè)術(shù)語(yǔ)起源于“哈佛馬克1號(hào)”計(jì)算機(jī)。它由IBM于1944年制造，用紙帶記錄指令，用繼電器來(lái)儲(chǔ)存數(shù)據(jù)。
一些最新的單片機(jī)使用了“哈佛結(jié)構(gòu)”（當(dāng)然沒(méi)有用紙帶和繼電器）。數(shù)據(jù)是由“內(nèi)存庫(kù)”來(lái)組織，每個(gè)“內(nèi)存庫(kù)”擁有相同數(shù)量的數(shù)據(jù)。每一個(gè)訪(fǎng)問(wèn)數(shù)據(jù)的指令都由2個(gè)數(shù)控制。一個(gè)數(shù)a（非0即1）。如果a為0，那么訪(fǎng)問(wèn)的是0號(hào)“內(nèi)存庫(kù)”。如果a為1則訪(fǎng)問(wèn)BSR（bank select register “內(nèi)存庫(kù)”選擇寄存器）中選擇的“內(nèi)存庫(kù)”。另一個(gè)數(shù)f表示訪(fǎng)問(wèn)該“內(nèi)存庫(kù)”的第f個(gè)變量。我們假設(shè)每一個(gè)指令花費(fèi)相同的時(shí)間運(yùn)行。另外還有一個(gè)可以設(shè)定BSR值的命令。
舉例來(lái)說(shuō)，假設(shè)有4個(gè)“內(nèi)存庫(kù)”，每個(gè)“內(nèi)存庫(kù)”有8個(gè)字節(jié)。為了訪(fǎng)問(wèn)位置5（0號(hào)“內(nèi)存庫(kù)”第5個(gè)變量），我們有兩種方法。第一種，使用指令a=0，f=5。第二種，先將BSR的值設(shè)為0，然后使用指令a=1，f=5。第一種方法更快，因?yàn)樗恍枰ㄙM(fèi)時(shí)間設(shè)置BSR。
現(xiàn)在假設(shè)（還是剛才的“內(nèi)存庫(kù)”）我們要訪(fǎng)問(wèn)位置20（2號(hào)“內(nèi)存庫(kù)”第4個(gè)變量）。現(xiàn)在只有1種方法能夠訪(fǎng)問(wèn)。將BSR的值設(shè)為2（除非BSR原來(lái)就是2），然后用指令a=1，f=4。
一個(gè)程序是一個(gè)操作的序列，每個(gè)操作是：
●一個(gè)變量訪(fǎng)問(wèn)操作，寫(xiě)作Vi，i是一個(gè)正整數(shù)。
●一個(gè)循環(huán)操作，寫(xiě)作 Rn <program> E，n是一個(gè)正整數(shù)，<program>是一個(gè)任意的程序。這個(gè)操作等價(jià)于依次執(zhí)行n遍<program>。
你的工作是決定一個(gè)程序最小的運(yùn)行時(shí)間。更確切的說(shuō)，給出“內(nèi)存庫(kù)”的個(gè)數(shù)和大小，需要執(zhí)行的程序，輸出為了執(zhí)行這個(gè)程序最小的指令數(shù)（包括數(shù)據(jù)訪(fǎng)問(wèn)指令和設(shè)定BSR的指令）。為了完成這個(gè)，你必須設(shè)定一個(gè)變量到“內(nèi)存庫(kù)”的映射，使得這個(gè)程序運(yùn)行時(shí)間最短，并且輸出這個(gè)時(shí)間（也就是程序運(yùn)行的指令數(shù)）。開(kāi)始的時(shí)候BSR的值為undefined，直到一條命令顯式的設(shè)定了它的值。
輸入格式
每組輸入包含一個(gè)case，兩行。第一行兩個(gè)整數(shù)b和s，1≤b≤13代表“內(nèi)存庫(kù)”的個(gè)數(shù)，1≤s≤13代表每個(gè)“內(nèi)存庫(kù)”的大小（即能儲(chǔ)存的變量數(shù)）。第二行是一個(gè)非空程序，最多有1000個(gè)元素（每個(gè)Rn，Vi，E都算1個(gè)元素）。
保證：
在循環(huán)Rn中，循環(huán)次數(shù)1≤n≤10^6。
在循環(huán)Rn <program> E中, <program>非空。
在數(shù)據(jù)訪(fǎng)問(wèn)Vi中，1≤i≤min(b*s,13)。
程序訪(fǎng)問(wèn)變量的次數(shù)不超過(guò)10^12次。
輸出格式
輸出運(yùn)行該程序最少需要的指令數(shù)。
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情
標(biāo)簽