第二屆程序設(shè)計大賽題目資料

1、1數(shù)字的游戲輸入文件名：gaspar.in 輸出文件名：estdout.pc2問題描述：N個教徒和N個非教徒在深海上遇險，必須將一半的人投入海中，其余的人 才能幸免于難，于是他們想了一個辦法：2N個人圍成一圈，從第一個人開始依 次循環(huán)報數(shù)，每數(shù)到第9個人就將他扔進(jìn)大海，如此循環(huán)直到只剩下N個人為止。問怎樣的站法，才能使得每次投入大海的都是非教徒。輸入：輸入文件由一行構(gòu)成，就是 N的值輸出：輸出文件是一行字符串，字符串由 N個字符（代表教徒）和N個+字符 （代表非教徒）排列組成。該排列使得按照提述方法每次投入大海的都是非教徒。輸入樣本：15輸出樣本：+2翻譯輸入文件：tran s.in輸出文件：

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

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

4、 4 4 12 108 824 11 78 11 78 11 78 8 2640 0輸出樣本：56問題描述：我們要求找出具有以下性質(zhì)的數(shù)的個數(shù)（包含輸入的自然數(shù)本身）先輸入一個自然數(shù)n（n=1000）,然后對此自然數(shù)進(jìn)行如下操作：1. 不作任何操作2. 在他左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)最高位數(shù)字的一 半3加上數(shù)之后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止輸入：第一行一個數(shù)t，表示有t組數(shù)據(jù)輸入之后每組數(shù)據(jù)占一行，每行一個自然數(shù) n 輸出：每組數(shù)據(jù)占一行，一個數(shù)，表示滿足條件的數(shù)的個數(shù) 輸入樣本:16 輸出樣本:64.自動糾正拼與錯誤輸入文件：auto.in輸出文件：estd

5、out.pc2問題描述：某些文件編輯器提供糾正英文單詞拼寫錯誤的功能。你們本次要解決的問題 就是實現(xiàn)這樣一個能夠完成自動糾正拼寫錯誤（ACM ）功能的應(yīng)用程序。ACM能夠糾正以下幾類的單詞拼寫錯誤：1. 漏寫或多寫1個字母，例如單詞“l(fā)etter”被寫成了 “l(fā)eter”，或者是“l(fā)etter” 被寫成了 “l(fā)ettter”。2. 寫錯了一個字母，例如“ letter”被寫成了“ ketter”。3. 兩個相鄰的字母書寫順序弄錯了，例如“ letter”被寫成了 “ lettre”。ACM的糾錯功能是基于一個已知單詞集的字典來進(jìn)行的。每當(dāng)一個文檔中 含有字典中不存在的單詞時，ACM就會試圖用字

6、典中與該單詞最相似的單詞替 代它。ACM對單詞是相似的有這樣的定義：只要兩個單詞能夠按照上面敘述的 3類拼寫錯誤規(guī)則中的任何一種進(jìn)行相互轉(zhuǎn)換，就認(rèn)為這兩個單詞是相似的。如 果在字典中沒有發(fā)現(xiàn)相似的單詞，就在原文本中保留這個未知的單詞。輸入：在輸入文件的第1行里將給出字典中已知的單詞數(shù)量：整數(shù)n,其中0=n=1000。在緊接著的n行里包含有字典中的n個單詞。在這n行后的第1 行里將給出1個正整數(shù)q，其中0=q=1000，它表示需要查詢單詞的數(shù)量。在 這之后的q行里包含有q個需要查詢的單詞。你可以假設(shè)在輸入文件中每一個單 詞只能由26個小寫字母（az）構(gòu)成。輸出：針對每一個需要查詢的單詞，輸出一行

7、字符串。要求：該字符串以需要查詢 的單詞開始，并從下面3個黑體描述中選擇一個合適的字串添加在后。1. 如果需要查詢的單詞在字典中就添加字串“ is correct2. 如果需要查詢的單詞不在字典中，則添加字串“ is a misspelling of ， 其中vx是指字典與需要查詢的單詞相似的單詞。若 x有多個，則選擇在字典 中出現(xiàn)最早的那個單詞輸出。3. 如果前面兩種情況都不滿足，則添加字串“ is unknown 0輸入樣本:10 this is a dictio nary thatwe will use forus6suasthedictio naryuswilll輸出樣本：su is

8、a misspelling of usas is a misspelling of isthe is unknowndictonary is a misspelling of dictionary us is correctwilll is a misspelling of will5.轟炸輸入文件：bomb.i n輸出文件：estdout.pc2問題描述：“我該怎么辦？”飛行員klux向你求助。事實上，klux面對的是一個很簡單 的問題，但是他實在是太菜了。 Klux要想轟炸某個區(qū)域內(nèi)的一些地方，它們是 位于平面上的一些點，但是klux遇到了抵抗，所以他只能飛一次，而且由于飛 機比較破，一旦

9、起飛就只能沿直線飛行，無法轉(zhuǎn)彎?，F(xiàn)在他想一次轟炸最多的地 方。輸入：輸入由若干組數(shù)據(jù)構(gòu)成，每組數(shù)據(jù)的第一行是整數(shù) n,然后是n行整數(shù)對組 成(1n700),每對整數(shù)表示一個點的坐標(biāo)，且沒有一個點會出現(xiàn)兩次。當(dāng)n為0 時表示輸入結(jié)束。輸出：針對沒組數(shù)據(jù)輸出一個數(shù)，它表示一條直線能覆蓋的最多的點數(shù)輸入樣本：51 12 23 39 1010 110 輸出樣本：36. 國家利益輸入文件：cou ntry.in輸出文件：estdout.in問題描述：沒有永遠(yuǎn)的朋友，也沒有永遠(yuǎn)的敵人，國家的行為取決于國家利益，國家的 地位取決于國家實力。伊拉克戰(zhàn)爭結(jié)束后 N個國家正在聯(lián)合國開會商討如何分 配伊拉克的M塊油

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

11、Z油田，而Z 丫，那么X號國家 會贊成1號的方案，否則反對。輸入：輸入文件有由若干行構(gòu)成，每行包括一組數(shù)據(jù)由2個整數(shù)N , M構(gòu)成，(N,M =10A8)，輸入文件的最后一行是 #表示文件結(jié)束。輸出：按照輸入文件的順序?qū)τ诿拷M輸入數(shù)據(jù)輸出一行，每行包括1個整數(shù)，1號國家能獲得的最多油田數(shù)。輸入樣本：7 1006 100#輸出樣本：97987. 拱豬計分輸入文件：pig.in輸出文件：estdout.pc2問題描述：拱豬是一種有趣的撲克牌游戲。即使你不知道他的玩法，你也可以由他的計 分方式來了解他的趣味性。假設(shè)在此我們僅考慮四個人的拱豬牌局，本題要求你 根據(jù)下面的積分規(guī)則，在牌局結(jié)束時計算四位玩

12、家所得分?jǐn)?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還有 其他計分牌，則將其他計分牌所得分?jǐn)?shù)加倍計算。4. 若紅心牌不在同一家，則H1至H13等13張牌均以負(fù)分計，其數(shù)值為-50， -2，-3，-4，-5，

13、-6，-7，-8，-9，-10，-20，-30，-40.而且 S12 和 D11 分別 以-100和+100分計算。5. 若紅心牌H1至H13均在同一家，有下列情形：a）所有紅心牌以+200分計算b）若S12、D11均在吃下所有紅心牌的這一家，則此玩家得+500 分c）而C10還是以前面的原則計算分?jǐn)?shù)例一：若玩家持有計分牌如下：（每列代表一玩家所持有之牌）S12 H3 H5 H13D11 H8 H9C10 H1 H2 H4 H6 H7H10 H11 H12則各玩家得分依次序為：-148，+83,-138及-60。例二：若各玩家持有計分牌如下（第四個玩家未持有任何計分牌）H1 H2 H3 H4

14、H5 H6 H7 H8 H9 H10 H11 H12 H13S12 C10D11則各玩家得分依次序為：+200, -200，+100及0。例三：若有一玩家持有所有16張計分牌，則得分+1000分，其余玩家均得零分。輸入：每個輸入文件有多組數(shù)據(jù)組成，每組測試數(shù)據(jù)有四行，每一行第一個數(shù)為該 玩家所持有計分牌的總數(shù)，而后列出其所持有的所有計分牌，牌數(shù)與各計分牌均 以一個以上的空格分開。相鄰兩組測試數(shù)據(jù)之間不會有空白行，讀到四家持牌數(shù)都為零表示文件結(jié) 束。輸出：每一行輸出一組測試數(shù)據(jù)對應(yīng)的結(jié)果，一次輸出各玩家所得分?jǐn)?shù)，共四個整 數(shù)（含正負(fù)號，0除外），相鄰兩個整數(shù)之間用一個空格隔開，符號和數(shù)字之間 不

15、可以有空格。每組輸出之間不需要空白行。輸入樣本：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.i n輸出文件：estdout.pc2問題描述：XX大學(xué)城離市中心比較遠(yuǎn)，因此占地面積巨大，因而XX市團(tuán)委準(zhǔn)備充分利用資源，在大學(xué)城舉辦定向越野比賽，但規(guī)則與普通定向越野不同，每個隊被要 求從某個

16、起點出發(fā)最后到達(dá)終點，只要是地圖上每個標(biāo)注的點都可以走，經(jīng)過一 個點時必須在打卡器上打卡做記錄， 記錄該點的打卡器所在位置的海拔高度，高度用一個非負(fù)整數(shù)來度量，該書將會被保存在卡中。最后到達(dá)終點時，該隊的成 績就為卡中記錄的最大數(shù)與最小數(shù)之差，差最小的隊伍將摘取桂冠。ZZ和他的同學(xué)也參加了這次比賽，拿到地圖后，他們想要迅速的找到一條最 佳路線以確保獲得冠軍。PS:其實光腦子好使能算出最佳路線還不夠，還得能跑，但是我們假設(shè)ZZ他們隊個個都是SUPERMAN要你能幫助他們找到最佳路線，它們就- 定是冠軍。輸入：由多組數(shù)據(jù)組成，輸入文件以EOF吉尾每組數(shù)據(jù)的第一行包含一個正整數(shù) n，表示校園地圖上共有n*n被標(biāo)注的點 (n=100)，接下來n行每行有n個非負(fù)整數(shù)Ai,j