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

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

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

3、每個月津津的預算，判斷會不會出現(xiàn)這種情況。如果不會，計算到2004年年末，媽媽將津津平常存的錢加上20還給津津之后，津津手中會有多少錢。 【輸入文件】     輸入文件save.in包括12行數(shù)據(jù)，每行包含一個小于350的非負整數(shù)，分別表示1月到12月津津的預算。 【輸出文件】     輸出文件save.out包括一行，這一行只包含一個整數(shù)。如果儲蓄計劃實施過程中出現(xiàn)某個月錢不夠用的情況，輸出-X，X表示出現(xiàn)這種情況的第一個月；否則輸出到2004年年末津津手中會有多少錢。 【樣例輸入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) 【問題描述】     在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。     每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一

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

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

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

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

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

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

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