《ACM算法與程序設計》期末問題集

1、一、綜合處理題1、兩倍 - http:/ 比如給定1 4 3 2 9 7 18 22，得到的答案是3，因為2是1的兩倍，4是2個兩倍，18是9的兩倍。 Input輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出2到15個兩兩不同且小于100的正整數(shù)。每一行最后一個數(shù)是0，表示這一行的結束后，這個數(shù)不屬于那2到15個給定的正整數(shù)。輸入的最后一行只包括一個整數(shù)-1,這行表示輸入數(shù)據(jù)的結束，不用進行處理。Output對每組輸入數(shù)據(jù)，輸出一行，給出有多少個數(shù)對滿足其中一個數(shù)是另一個數(shù)的兩倍。Sample Input1 4 3 2 9 7 18 22 02 4 8 10 07 5 11 13 1 3 0-1

2、Sample Output3202、誰拿了最多獎學金 - http:/ 1) 院士獎學金，每人8000元，期末平均成績高于80分（80），并且在本學期內(nèi)發(fā)表1篇或1篇以上論文的學生均可獲得； 2) 五四獎學金，每人4000元，期末平均成績高于85分（85），并且班級評議成績高于80分（80）的學生均可獲得； 3) 成績優(yōu)秀獎，每人2000元，期末平均成績高于90分（90）的學生均可獲得； 4) 西部獎學金，每人1000元，期末平均成績高于85分（85）的西部省份學生均可獲得； 5) 班級貢獻獎，每人850元，班級評議成績高于80分（80）的學生干部均可獲得； 只要符合條件就可以得獎，每項獎學金

3、的獲獎人數(shù)沒有限制，每名學生也可以同時獲得多項獎學金。例如姚林的期末平均成績是87分，班級評議成績82分，同時他還是一位學生干部，那么他可以同時獲得五四獎學金和班級貢獻獎，獎金總數(shù)是4850元。 現(xiàn)在給出若干學生的相關數(shù)據(jù)，請計算哪些同學獲得的獎金總數(shù)最高（假設總有同學能滿足獲得獎學金的條件）。 Input輸入的第一行是一個整數(shù)N（1 = N = 100），表示學生的總數(shù)。接下來的N行每行是一位學生的數(shù)據(jù)，從左向右依次是姓名，期末平均成績，班級評議成績，是否是學生干部，是否是西部省份學生，以及發(fā)表的論文數(shù)。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級評議成

4、績都是0到100之間的整數(shù)（包括0和100）；是否是學生干部和是否是西部省份學生分別用一個字符表示，Y表示是，N表示不是；發(fā)表的論文數(shù)是0到10的整數(shù)（包括0和10）。每兩個相鄰數(shù)據(jù)項之間用一個空格分隔。Output輸出包括三行，第一行是獲得最多獎金的學生的姓名，第二行是這名學生獲得的獎金總數(shù)。如果有兩位或兩位以上的學生獲得的獎金最多，輸出他們之中在輸入文件中出現(xiàn)最早的學生的姓名。第三行是這N個學生獲得的獎學金的總數(shù)。Sample Input4YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1

5、Sample OutputChenRuiyi900028700二、字符串處理1、古代密碼 - http:/ 替換方法是將所有出現(xiàn)的字符替換成其它的字符。有些字符會碰巧替換成它自己。例如：替換規(guī)則可以是將A 到 Y替換成它的下一個字符，將Z替換成 A，如果原詞是 VICTORIOUS 則它變成 WJDUPSJPVT。 排列方法改變原來單詞中字母的順序。例如：將順序 應用到 VICTORIOUS 上，則得到IVOTCIRSUO。 人們很快意識到單獨應用替換方法或排列方法，加密是很不保險的。但是如果結合這兩種方法，在當時就可以得到非?？煽康募用芊椒āＫ?，很多重要信息先使用替換方法加密，再將加密的結

6、果用排列的方法加密。用兩中方法結合就可以將VICTORIOUS 加密成JWPUDJSTVP。 考古學家最近在一個石臺上發(fā)現(xiàn)了一些信息。初看起來它們毫無意義，所以有人設想它們可能是用替換和排列的方法被加密了。人們試著解讀了石臺上的密碼，現(xiàn)在他們想檢查解讀的是否正確。他們需要一個計算機程序來驗證她，你的任務就是寫這個驗證程序。 Input輸入有兩行。第一行是石臺上的文字。文字中沒有空格，并且只有大寫英文字母。第二行是被解讀出來的加密前的文字。第二行也是由大寫英文字母構成的。 兩行字符數(shù)目的長度都不超過計劃100。Output如果第二行經(jīng)過某種加密方法后可以產(chǎn)生第一行的信息，輸出 YES，否則輸出N

7、O。Sample InputJWPUDJSTVPVICTORIOUSSample OutputYES2、詞典 - http:/ Sample Inputdog ogdaycat atcaypig igpayfroot ootfrayloops oopslayatcayittenkayoopslaySample Outputcatehloops3、最短前綴 - http:/ carbon的字串是: c, ca, car, carb, carbo, 和 carbon。注意到這里我們不認為空串是字串, 但是每個非空串是它自身的字串. 我們現(xiàn)在希望能用前綴來縮略的表示單詞。例如, carbohydra

8、te 通常用carb來縮略表示. 現(xiàn)在給你一組單詞, 要求你找到唯一標識每個單詞的最短前綴 在下面的例子中，carbohydrate 能被縮略成carboh, 但是不能被縮略成carbo (或其余更短的前綴) 因為已經(jīng)有一個單詞用carbo開始 一個精確匹配會覆蓋一個前綴匹配，例如，前綴car精確匹配單詞car. 因此 car 是 car的縮略語是沒有二義性的 , “car”不會被當成carriage或者任何在列表中以car開始的單詞. Input輸入包括至少2行，至多1000行. 每行包括一個以小寫字母組成的單詞，單詞長度至少是1，至多是20.Output輸出的行數(shù)與輸入的行數(shù)相同。每行輸出

9、由相應行輸入的單詞開始，后面跟著一個空格接下來是相應單詞的沒有二義性的最短前綴標識符。Sample InputcarbohydratecartcarburetorcaramelcariboucarboniccartilagecarboncarriagecartoncarcarbonateSample Outputcarbohydrate carbohcart cartcarburetor carbucaramel caracaribou caricarbonic carbonicartilage carticarbon carboncarriage carrcarton cartocar ca

10、rcarbonate carbona三、模擬1、數(shù)根 http:/ 比如，對于24來說，把2和4相加得到6，由于6是一位數(shù)，因此6是24的數(shù)根。再比如39，把3和9加起來得到12，由于12不是一位數(shù)，因此還得把1和2加起來，最后得到3，這是一個一位數(shù)，因此3是39的數(shù)根。Input輸入包括一些正整數(shù)(小于101000)，每個一行。輸入的最后一行是0，表示輸入的結束，這一行不用處理。Output對每個正整數(shù)，輸出它的數(shù)根。每個結果占據(jù)一行。Sample Input24390Sample Output632、循環(huán)數(shù) http:/ 位的一個整數(shù)是循環(huán)數(shù)（cyclic）的條件是：當用一個 1 到 n

11、之間的整數(shù)去乘它時, 會得到一個將原來的數(shù)首尾相接循環(huán)移動若干數(shù)字再在某處斷開而得到的數(shù)字。也就是說，如果把原來的數(shù)字和新的數(shù)字都首尾相接，他們得到的環(huán)是相同的。只是兩個數(shù)的起始數(shù)字不一定相同。例如，數(shù)字 142857 是循環(huán)數(shù)，因為: 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142 Input寫一個程序確定給定的數(shù)是否是循環(huán)數(shù)。輸入包括多個長度為 2 位到 60 位的整數(shù)。(注意，先導的0也是合理的輸入不應該被忽略

12、,例如 01是 2 位數(shù)，1 是 1 位數(shù)。) Output對于每一個輸入的整數(shù)，輸出一行表明它是否是循環(huán)數(shù)。 Sample Input142857142856142858010588235294117647Sample Output142857 is cyclic142856 is not cyclic142858 is not cyclic01 is not cyclic0588235294117647 is cyclic四、高精度計算1、孫子問題 http:/ 為解決這個問題民間流傳了如下歌訣：“三人同行七十稀，五樹梅花廿一枝，七子團員正半月，除百零五便得知?！?把上面的問題說得明白一點

13、就是：有一個正整數(shù)N，除以3的余數(shù)是2，除以5的余數(shù)是3，除以7的余數(shù)是2，要求這個數(shù)。 民間給出的解法是：把N除以3的余數(shù)乘以70，把N除以5的余數(shù)乘以21，把N除以7的余數(shù)乘以15，把這三個結果加起來，最后把得到的結果除以105得到的就是答案。 其實在民間的解法中不除以105得到的也是一個符合題意的答案，而且民間的解法對于已知“除以3的余數(shù)，除以5的余數(shù)和除以7的余數(shù)” 的問題都能得到一個符合要求的答案。比如對于上面的問題，得到的結果是2 * 70 + 3 * 21 + 2 * 15 = 233，這個結果也能滿足除以3的余數(shù)是2，除以5的余數(shù)是3，除以7的余數(shù)是2。如果已知的問題是“除以3

14、的余數(shù)是1，除以5的余數(shù)是4，除以7的余數(shù)是4”，民間解法得到的結果1 * 70 + 4 * 21 + 4 * 15 = 214，這個結果也滿足除以3的余數(shù)是1，除以5的余數(shù)是4，除以7的余數(shù)是4。 把這個問題推廣到更普遍的情況：對于給定的正整數(shù)a1, a2, . an，是否存在正整數(shù)b1, b2, . bn，使得對于任意的一個正整數(shù)N，如果用N除以a1的余數(shù)是p1，用N除以a2的余數(shù)是p2用N除以an的余數(shù)是pn，那么M = p1 * b1 + p2 * b2 + . + pn * bn能滿足M除以a1的余數(shù)也是p1，M除以a2的余數(shù)也是p2M除以an的余數(shù)也是pn。 Input輸入包括多組

15、測試數(shù)據(jù)，每組數(shù)據(jù)包括一行。在每組數(shù)據(jù)中，首先給出ai的個數(shù)n (1 = n = 10)，然后給出n個不大于50的正整數(shù)a1, a2, . an。最后一組測試數(shù)據(jù)中n = 0，表示輸入的結束，這組數(shù)據(jù)不用處理。Output對于每一組測試數(shù)據(jù)，輸出一行，如果存在正整數(shù)b1, b2, . bn滿足題意，則輸出這n個正整數(shù)（數(shù)的長度不要超過50位）如果有多組答案，輸出任意一組即可，相鄰的正整數(shù)之間用一個空格隔開；否則，輸出“NO”。Sample Input3 3 5 70Sample Output70 21 15五、枚舉1、數(shù)字方格 http:/ = a1, a2, a3 = n，而且a1 + a2

16、是2的倍數(shù)，a2 + a3是3的倍數(shù)， a1 + a2 + a3是5的倍數(shù)。你的任務是找到一組a1，a2，a3，使得a1 + a2 + a3最大。 Input輸入的第一行是一個數(shù)t，表示測試數(shù)據(jù)的數(shù)目。接下來的t行，每行給出一個n (0 = n = 100)的值。Output對于每一個n的值，輸出a1 + a2 + a3的最大值。Sample Input203Sample Output052、畫家問題 http:/ j)個位置的磚時， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的磚都會改變顏色。請你幫助Bob計算出最少需要涂畫多少塊磚，才能使所有磚的顏色

17、都變成黃色。 Input第一行是個整數(shù)t(1t 20)，表示要測試的案例數(shù)。然后是t個案例。每個案例的首行是一個整數(shù)n (1n 15)，表示墻的大小。接下來的n行表示墻的初始狀態(tài)。每一行包含n個字符。第i行的第j個字符表示位于位置(i,j)上的磚的顏色?！皐”表示白磚，“y”表示黃磚。Output每個案例輸出一行。如果Bob能夠?qū)⑺械拇u都涂成黃色，則輸出最少需要涂畫的磚數(shù)，否則輸出“inf”。Sample Input2 3 yyy yyy yyy 5wwwww wwwww wwwww wwwww wwwww Sample Output0 15 3、撥鐘問題 http:/ 現(xiàn)在需要用最少的移動

18、，將9個時鐘的指針都撥到12點的位置。共允許有9種不同的移動。如右表所示，每個移動會將若干個時鐘的指針沿順時針方向撥動90度。 移動 影響的時鐘 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI (圖 2) Input從標準輸入設備讀入9個整數(shù)，表示各時鐘指針的起始位置。1=12點、1=3點、2=6點、3=9點。Output輸出一個最短的移動序列，使得9個時鐘的指針都指向12點。按照移動的序號大小，輸出結果。Sample Input3 3 0 2 2 2 2 1 2 Sample Output4 5 8 9 六、遞歸與動態(tài)規(guī)

19、劃1、算24 http:/ 這里加減乘除以及括號的運算結果和運算的優(yōu)先級跟我們平常的定義一致（這里的除法定義是實數(shù)除法）。 比如，對于5，5，5，1，我們知道5 * (5 1 / 5) = 24，因此可以得到24。又比如，對于1，1，4，2，我們怎么都不能得到24。 Input輸入數(shù)據(jù)包括多行，每行給出一組測試數(shù)據(jù)，包括4個小于10個正整數(shù)。最后一組測試數(shù)據(jù)中包括4個0，表示輸入的結束，這組數(shù)據(jù)不用處理。Output對于每一組測試數(shù)據(jù)，輸出一行，如果可以得到24，輸出“YES”；否則，輸出“NO”。Sample Input5 5 5 11 1 4 20 0 0 0Sample OutputYESNO2、滑雪 http:/ 因為滑雪的確很刺激。可是為了獲得速度，滑的區(qū)域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區(qū)域中最長的滑坡。區(qū)域由一個二維數(shù)組給出。數(shù)組的每個數(shù)字代表點的高度。下面是一個例子 1 2 3 4 516 17