第十屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽提高組復(fù)賽試題

1、第十屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題 (提高組 3小時(shí)完成) 一、津津的儲(chǔ)蓄計(jì)劃 (Save.pasdprccpp) 【問(wèn)題描述】     津津的零花錢(qián)一直都是自己管理。每個(gè)月的月初媽媽給津津300元錢(qián)，津津會(huì)預(yù)算這個(gè)月的花銷，并且總能做到實(shí)際花銷和預(yù)算的相同。     為了讓津津?qū)W習(xí)如何儲(chǔ)蓄，媽媽提出，津津可以隨時(shí)把整百的錢(qián)存在她那里，到了年末她會(huì)加上20還給津津。因此津津制定了一個(gè)儲(chǔ)蓄計(jì)劃：每個(gè)月的月初，在得到媽媽給的零花錢(qián)后，如果她預(yù)計(jì)到這個(gè)月的月末手中還會(huì)有多于100元或恰好100元，她就會(huì)把整百的錢(qián)

2、存在媽媽那里，剩余的錢(qián)留在自己手中。     例如11月初津津手中還有83元，媽媽給了津津300元。津津預(yù)計(jì)11月的花銷是180元，那么她就會(huì)在媽媽那里存200元，自己留下183元。到了11月月末，津津手中會(huì)剩下3元錢(qián)。     津津發(fā)現(xiàn)這個(gè)儲(chǔ)蓄計(jì)劃的主要風(fēng)險(xiǎn)是，存在媽媽那里的錢(qián)在年末之前不能取出。有可能在某個(gè)月的月初，津津手中的錢(qián)加上這個(gè)月媽媽給的錢(qián)，不夠這個(gè)月的原定預(yù)算。如果出現(xiàn)這種情況，津津?qū)⒉坏貌辉谶@個(gè)月省吃儉用，壓縮預(yù)算。     現(xiàn)在請(qǐng)你根據(jù)2004年1月到12月

3、每個(gè)月津津的預(yù)算，判斷會(huì)不會(huì)出現(xiàn)這種情況。如果不會(huì)，計(jì)算到2004年年末，媽媽將津津平常存的錢(qián)加上20還給津津之后，津津手中會(huì)有多少錢(qián)。 【輸入文件】     輸入文件save.in包括12行數(shù)據(jù)，每行包含一個(gè)小于350的非負(fù)整數(shù)，分別表示1月到12月津津的預(yù)算。 【輸出文件】     輸出文件save.out包括一行，這一行只包含一個(gè)整數(shù)。如果儲(chǔ)蓄計(jì)劃實(shí)施過(guò)程中出現(xiàn)某個(gè)月錢(qián)不夠用的情況，輸出-X，X表示出現(xiàn)這種情況的第一個(gè)月；否則輸出到2004年年末津津手中會(huì)有多少錢(qián)。 【樣例輸入1】 2902302802003

4、0017034050 90 80 20060 【樣例輸出1】 -7 【樣例輸入2】 290 230 280 200 300 170 330 50 90 80 200 60 【樣例輸出2】 1580 二、合并果子 (fruit.pasdprccpp) 【問(wèn)題描述】     在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來(lái)，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。     每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過(guò)n-1次合并之后，就只剩下一

5、堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。     因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。     例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15。可以證明15為最小的

6、體力耗費(fèi)值。 【輸入文件】     輸入文件fruit.in包括兩行，第一行是一個(gè)整數(shù)n(1<n<=10000)，表示果子的種類數(shù)。第二行包含n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)ai(1<ai<=20000)是第i種果子的數(shù)目。 【輸出文件】     輸出文件fruit.out包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于231。 【樣例輸入】 3 1 2 9 【樣例輸出】 15 【數(shù)據(jù)規(guī)模】 對(duì)于30的數(shù)據(jù)，保證有n<=1000： 對(duì)于50的數(shù)據(jù)，保證有n

7、<=5000； 對(duì)于全部的數(shù)據(jù)，保證有n<=10000。 三、合唱隊(duì)形(chorus.pasdprccpp)【問(wèn)題描述】    N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。    合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2，K，他們的身高分別為T(mén)1，T2，TK，  則他們的身高滿足T1<.<Ti>Ti+1>>TK(1<=i<=K)。    

8、;你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形?！据斎胛募?#160;   輸入文件chorus.in的第一行是一個(gè)整數(shù)N(2<=N<=100)，表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高(厘米)?！据敵鑫募?#160;   輸出文件chorus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186 186 150 200 160 130 197 220【樣例輸出】

9、4【數(shù)據(jù)規(guī)?！繉?duì)于50的數(shù)據(jù)，保證有n<=20；對(duì)于全部的數(shù)據(jù)，保證有n<=100。四、蟲(chóng)食算(alpha.pas/dpr/c/cpp)【問(wèn)題描述】    所謂蟲(chóng)食算，就是原先的算式中有一部分被蟲(chóng)子啃掉了，需要我們根據(jù)剩下的數(shù)字來(lái)判定被啃掉的字母。來(lái)看一個(gè)簡(jiǎn)單的例子：       43#9865#045    +    8468#6633     

10、0; 44445506978    其中#號(hào)代表被蟲(chóng)子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：第一行的兩個(gè)數(shù)字分別是5和3，第二行的數(shù)字是5。    現(xiàn)在，我們對(duì)問(wèn)題做兩個(gè)限制：    首先，我們只考慮加法的蟲(chóng)食算。這里的加法是N進(jìn)制加法，算式中三個(gè)數(shù)都有N位，允許有前導(dǎo)的0。    其次，蟲(chóng)子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的，我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。如果這個(gè)算式是N進(jìn)制的，我們就取英文

11、字母表午的前N個(gè)大寫(xiě)字母來(lái)表示這個(gè)算式中的0到N-1這N個(gè)不同的數(shù)字：但是這N個(gè)字母并不一定順序地代表0到N-1)。輸入數(shù)據(jù)保證N個(gè)字母分別至少出現(xiàn)一次。            BADC      +    CRDA            DCCC    上面的算式是一個(gè)4進(jìn)制的算式。很顯然，我們只要讓ABCD分別代表0123，便可以讓這個(gè)式子成立了。你的任務(wù)是，對(duì)于給定的N進(jìn)制加法算式，求出N個(gè)不同的字母分別代表的數(shù)字，使得該加法算式成立。輸入數(shù)據(jù)保證有且僅有一組解，【輸入文件】    輸入文件alpha.in包含4行。第一行有一個(gè)正整數(shù)N(N<=26)，后面的3行每行有一個(gè)由大寫(xiě)字母組成的字符串，分別代表兩個(gè)加數(shù)以及和。這3個(gè)字符串左右兩端都沒(méi)有空格，從高位到低位，并且恰好有N位。【輸出文件】    輸