重慶市第二屆程序設(shè)計大賽題目試題

1、1 數(shù)學的游戲輸入文件名“gaspar.in” 輸出文件名“estdout.pc2”問題描述17世紀法國數(shù)學家加斯帕在數(shù)學的游戲問題中講的一個故事：n個教徒和n個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了個辦法：2n個人圍成一個圓圈，從第一個人開始依次循環(huán)報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)直到僅剩n個人為止 。問怎樣的排法，才能使每次投入大海的都是非教徒。輸入輸入文件由一行構(gòu)成，就是n的值。輸出輸出文件中是一行字符串，字符串由n個字符（代表教徒）和n個+ 字符（代表非教徒）排列構(gòu)成。該排列使得按照前面的約定每次投入大海的都是非教徒。輸入樣本15輸出樣本

2、+2 翻譯輸入文件名“trans.in” 輸出文件名“estdout.pc2”問題描述小晨的電腦上安裝了一個機器翻譯軟件，他經(jīng)常用這個軟件來翻譯英語文章。這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應(yīng)的中文含義來替換。對于每個英文單詞，軟件會先在內(nèi)存中查找這個單詞的中文含義，如果內(nèi)存中有，軟件就會用它進行翻譯；如果內(nèi)存中沒有，軟件就會在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。假設(shè)內(nèi)存中有M 個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內(nèi)存前，如果當前內(nèi)存中已存入的單詞數(shù)不超過M，軟件會將新單詞存入一個

3、未使用的內(nèi)存單元；若內(nèi)存中已存入M 個單詞，軟件會清空最早進入內(nèi)存的那個單詞，騰出單元來，存放新單詞。假設(shè)一篇英語文章的長度為N 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開始前，內(nèi)存中沒有任何單詞。輸入多組數(shù)據(jù)，每組數(shù)據(jù)共2 行。每行中兩個數(shù)之間用一個空格隔開。第一行為兩個正整數(shù)M 和N（0M 100，0N 1000），代表內(nèi)存容量和文章的長度。第二行為N 個非負整數(shù)，按照文章的順序，每個數(shù)（大小不超過1000）代表一個英文單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應(yīng)的非負整數(shù)相同。當N=M=0時輸入數(shù)據(jù)結(jié)束。輸出每組數(shù)據(jù)占1行，分別包含一個整數(shù)，為軟件需要

4、查詞典的次數(shù)。輸入樣本3 71 2 1 5 4 4 12 108 824 11 78 11 78 11 78 8 2640 0輸出樣本563 自然數(shù)的計算輸入文件名“natural.in” 輸出文件名“estdout.pc2”問題描述我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n):先輸入一個自然數(shù)n(n=1000),然后對此自然數(shù)按照如下方法進行處理:1.不作任何處理;2.在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)最高位數(shù)字的一半;3.加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.輸入第一行一個數(shù)t，表示有t組數(shù)據(jù)之后每組數(shù)據(jù)占一行，每行一個數(shù)n輸出每組數(shù)據(jù)占一行，一個

5、數(shù)，表示滿足條件的數(shù)的個數(shù)輸入樣本16輸出樣本64自動糾正拼寫錯誤輸入文件: “auto.in” 輸出文件: “estdout.pc2”問題描述某些文本編輯器提供糾正英文單詞拼寫錯誤的功能。你們本次要解決的問題就是實現(xiàn)這樣一個能夠完成自動糾正拼寫錯誤（ACM）功能的應(yīng)用程序。ACM能夠糾正以下幾類的單詞拼寫錯誤：1.漏寫或多寫1個字母（多寫的這個字母是否要求是前一個字母？），例如單詞”letter”被寫成了”leter”，或者是”letter”被寫成了”lettter”。 2.寫錯了1個字母，例如”letter”被寫成了”ketter”。 3.兩個相鄰的字母的書寫順序弄錯了，例如”letter

6、”被寫成了”lettre”。 ACM的糾錯是基于一個已知單詞集的字典來進行的。每當一個文檔中含有字典中不存在的單詞時，ACM就會試圖用字典中與該單詞最相似的單詞代替它。ACM對兩個單詞是相似的有這樣的定義：只要這兩個單詞能夠按照上面敘述的3類拼寫錯誤規(guī)則中任何一種進行相互轉(zhuǎn)換，就認為這兩個單詞是相似的。如果在字典中沒有發(fā)現(xiàn)相似的單詞，就在原文本中保留這個未知單詞。輸入在輸入文件的第1行里將給出字典中的已知單詞的數(shù)量：整數(shù) n，其中0n 10000。在緊接著的n行里包含有字典中的n個單詞。在這n行后的第1行里將給出1個正整數(shù)q，其中0q 1000，它表示需要查詢單詞的數(shù)量。在這之后的q行里包含有

7、q個需要查詢的單詞。你可以假設(shè)在輸入文件中每一個的單詞只能由26個小寫字母(a 到 z)構(gòu)成。輸出針對每一個需要查詢單詞，輸出一行字符串。要求：該字符串以需要查詢的單詞開始；并從下面3個黑體描述中選擇合適的一個子串添加在之后。1.如果需要查詢的單詞在字典中就添加子串：“is correct”。 2.如果需要查詢的單詞不在字典中，則添加子串：“is a misspelling of ”， 其中是指字典中與需要查詢的單詞相似的單詞。若有多個，則選擇在字典中出現(xiàn)最早的那個單詞輸出。 3.如果前面兩種情況都不滿足，則添加子串：“is unknown”。輸入樣本10thisisadictionaryth

8、atwewilluseforus6suasthedictonaryuswilll輸出樣本su is a misspelling of usas is a misspelling of isthe is unknowndictonary is a misspelling of dictionaryus is correctwilll is a misspelling of will5 轟炸輸入文件: “bomb.in” 輸出文件: “estdout.pc2”問題描述“我該怎么辦？”飛行員klux向你求助。事實上，klux面對的是一個很簡單的問題，但是他實在太菜了。klux要想轟炸某個區(qū)域內(nèi)的一些

9、地方，它們是位于平面上的一些點，但是（顯然地）klux遇到了抵抗，所以klux只能飛一次，而且由于飛機比較破，一點起飛就只能沿直線飛行，無法轉(zhuǎn)彎?，F(xiàn)在他想一次轟炸最多的地方。輸入輸入由若干組數(shù)據(jù)構(gòu)成，每組數(shù)據(jù)的第一行是整數(shù)n，然后是n行整數(shù)對組成(1n700)，每對整數(shù)表示一個點的坐標，且沒有一個點會出現(xiàn)兩次。當n為0時表示輸入結(jié)束。輸出針對每組數(shù)據(jù)輸出一個整數(shù)，它表示一條直線能覆蓋的最多的點數(shù)。輸入樣本51 12 23 39 1010 110輸出樣本36國家利益輸入文件名“country.in”輸出文件名“estdout.pc2”問題描述沒有永遠的朋友，也沒有永遠的敵人，國家的行為取決于國家

10、利益，國家的地位取決于國家實力。伊拉克戰(zhàn)爭結(jié)束后N個國家正在聯(lián)合國開會商討如何分配伊拉克的M塊油田。N個國家按國家實力編號1，2，3.N，1號國家實力最強，第一個發(fā)言，N號最后一個發(fā)言；依次類推發(fā)言國家會提出一個分配方案，所有有表決權(quán)的國家進行表決（包括發(fā)言國家自己）；如果50%或以上同意此方案，則會議結(jié)束，按照此國的方案分配油田，否則該國喪失表決權(quán)，下個國家重復(fù)上述過程。那么第一個國家提出怎樣的方案才能使本國利益最大化？提示：每個國家分得的油田都是整數(shù)，不會出現(xiàn)幾個國家共同擁有一塊油田每個國家都不希望別人的方案通過，但是每個國家都按照本國利益投票，比如1號國家提出一個方案，X號國家分Y油田，

11、X號國家會進行比較，如果該方案被否決，那么下次2號提出的方案X號國家分Z油田，而Z Y，那么X號國家會贊成1號的方案，否則反對輸入輸入文件有由若干行構(gòu)成，每行包括一組數(shù)據(jù)由2個整數(shù)N，M構(gòu)成，（N,M = 108），輸入文件的最后一行是#表示文件結(jié)束。輸出按照輸入文件的順序?qū)τ诿拷M輸入數(shù)據(jù)輸出一行，每行包括1個整數(shù)，1號國家可能獲得的最多油田數(shù)。輸入樣本7 100#輸出樣本977拱豬計分輸入文件名“pig.in”輸出文件名“estdout.pc2”問題描述拱豬是一種很有趣的撲克牌游戲。 即使你不知道它的玩法，你也可以由它的計分方式來了解它的趣味性。 假設(shè)在此我們僅考慮四個人的拱豬牌局，本題要求

12、你根據(jù)下面的計分規(guī)則，在牌局結(jié)束時計算四位玩家所得分數(shù)。1.我們分別以 S、H、D 及 C 來代表黑桃，紅心，方塊及梅花，并以數(shù)字 1 至 13 來代表 A、2、Q、K 等牌點，例如 H1 為紅心 A，S13 為黑桃 K。2.牌局結(jié)束時，由各玩家持有的有關(guān)計分的牌(計分牌)僅有S12 (豬)，所有紅心牌，D11 (羊)及 C10 (加倍)等16張牌。其它牌均棄置不計。若未持有這 16 張牌之任一張則以得零分計算。3.若持有 C10 的玩家只有該張牌而沒有任何其它牌則得 +50 分，若除了 C10 還有其它計分牌，則將其它計分牌所得分數(shù)加倍計算。4.若紅心牌不在同一家，則 H1 至 H13 等

13、13 張牌均以負分計，其數(shù)值為 -50，-2，-3，-4，-5，-6，-7，-8，-9，-10，-20，-30，-40。而且 S12 與 D11 分別以 -100 及 +100 分計算。5.若紅心牌 H1 至H13 均在同一家，有下列情形o所有紅心牌以+200分計算。o若 S12、D11 皆在吃下所有紅心牌之一家，則此玩家得 +500 分。o而 C10 還是以前面所述原則計算之。例一：若各玩家持有計分牌如下：(每列代表一玩家所持有之牌)S12 H3 H5 H13D11 H8 H9C10 H1 H2 H4 H6 H7H10 H11 H12則各家之得分依序為：-148、+83、-138 及 -60

14、。例二：若各玩家持有計分牌如下：(第四家未持有任何計分牌)H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13S12 C10D11則各家之得分依序為：+200、-200、+100 及 0。例三：若有一玩家持有所有 16 張計分牌，則得 +1000 分。其余三家均得零分。輸入每個輸入文件由多組測試數(shù)據(jù)構(gòu)成，每組測試數(shù)據(jù)有四行，每一行第一個數(shù)為該玩家所持有計分牌總數(shù)，而后列出其所持有之所有計分牌，牌數(shù)與各計分牌均以一個以上的空格分開。相鄰兩組測試數(shù)據(jù)之間不會有空白行，讀到四家持牌數(shù)都為 0 表示文件結(jié)束。輸出每一行輸出一組測試數(shù)據(jù)對應(yīng)的結(jié)果，依次輸出各家所得分數(shù)，共

15、四個整數(shù)(含正負號，0 除外)，相鄰兩個整數(shù)之間以一個空格分開，符號和數(shù)字間不可以有空格。每組輸出間不需要有空白行。輸入樣本4 S12 H3 H5 H133 D11 H8 H96 C10 H1 H2 H4 H6 H73 H10 H11 H1213 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H132 S12 C101 D1100000輸出樣本-148 +83 -138 -60+200 -200 +100 08 定向越野輸入文件名“cross.in輸出文件名“estdout.pc2”問題描述XX大學城離市中心距離略遠，因此占地面積巨大，因而XX團市委準備充分利用

16、資源，在大學城里舉辦定向越野比賽，但規(guī)則與普通定向越野不同，每個隊被要求從某個起點出發(fā)最后到達終點，只要是地圖上每個被標注的點都可以走，經(jīng)過一個點時必須在打卡器上打卡作記錄，記錄該點的打卡器所在位置的海拔高度，高度用一個非負整數(shù)來量度，該數(shù)將會被所保存在卡中。最后到達終點時，該隊的成績就為卡中記錄的最大數(shù)與最小數(shù)之差，差最小的隊伍將摘取桂冠。ZZ和他的同學也參與了這項運動，拿到地圖后，他們想要迅速找到一條最佳路線以確保獲得冠軍。PS：其實光腦子好能算出最佳路線還不夠，還得能跑，但我們假設(shè)ZZ他們隊個個都是SUPERMAN，只要你幫助他們找到了最佳路線，他們就能獲得冠軍。輸入由多組數(shù)據(jù)組成，輸入文件以EOF結(jié)尾。每組數(shù)據(jù)的第一行包含一個正整數(shù)n，表示校園地圖上共有n*n個被標注的點（n100）接下來n行每行有n個非負整數(shù)Ai