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

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

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

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

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

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

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

7、q個(gè)需要查詢的單詞。你可以假設(shè)在輸入文件中每一個(gè)的單詞只能由26個(gè)小寫字母(a 到 z)構(gòu)成。輸出針對(duì)每一個(gè)需要查詢單詞，輸出一行字符串。要求：該字符串以需要查詢的單詞開(kāi)始；并從下面3個(gè)黑體描述中選擇合適的一個(gè)子串添加在之后。1.如果需要查詢的單詞在字典中就添加子串：“is correct”。 2.如果需要查詢的單詞不在字典中，則添加子串：“is a misspelling of ”， 其中是指字典中與需要查詢的單詞相似的單詞。若有多個(gè)，則選擇在字典中出現(xiàn)最早的那個(gè)單詞輸出。 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”問(wèn)題描述“我該怎么辦？”飛行員klux向你求助。事實(shí)上，klux面對(duì)的是一個(gè)很簡(jiǎn)單的問(wèn)題，但是他實(shí)在太菜了。klux要想轟炸某個(gè)區(qū)域內(nèi)的一些

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

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

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

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

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

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

15、四個(gè)整數(shù)(含正負(fù)號(hào)，0 除外)，相鄰兩個(gè)整數(shù)之間以一個(gè)空格分開(kāi)，符號(hào)和數(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”問(wèn)題描述XX大學(xué)城離市中心距離略遠(yuǎn)，因此占地面積巨大，因而XX團(tuán)市委準(zhǔn)備充分利用

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