NOIP2015復(fù)賽普及組試題

1、CCF 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015 ）復(fù)賽普及組（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）一題目概況中文題目名稱金幣掃雷游戲求和推銷員英文題目與子目錄名coi nmi nesumsalesma n可執(zhí)行文件名coi nmi nesumsalesma n輸入文件名輸出文件名每個(gè)測試點(diǎn)時(shí)限1 秒1 秒1 秒1 秒測試點(diǎn)數(shù)目10101010每個(gè)測試點(diǎn)分值10101010附加樣例文件有有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M128M128M提交源程序文件名對(duì)于 C+語言對(duì)于 C 語言對(duì)于 pascal 語言三編譯命令（不包含任何優(yōu)化開關(guān)

2、）對(duì)于 C+語言g+ -o coin -lmg+ -o mine -lmg+ -o sum -lmg+ -o salesma n - lm對(duì)于 C 語言gcc -o coin-lmgcc -o mine-lmgcc -o sum-lmgcc -o salesma n-lm對(duì)于 pascal 語言fpcfpcfpcfpc注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、 C/C+中函數(shù) main（）的返回值類型必須是 int,程序正常結(jié)束時(shí)的返回值必須是0。3、 全國統(tǒng)一評(píng)測時(shí)采用的機(jī)器配置為：CPU AMD Athlon（tm） II x2 240 processor ,，內(nèi)

3、存 4G, 上述時(shí)限以此配置為準(zhǔn)。4、只提供 Linux 格式附加樣例文件。5、 特別提醒：評(píng)測在當(dāng)前最新公布的NOI Lin ux 下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。1.金幣c/pas）國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第 二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天） ，每天收到三枚金 幣；之后四天（第七、八、九、十天），每天收到四枚金幣；這種工資發(fā)放模式會(huì)一 直這樣延續(xù)下去：當(dāng)連續(xù)N天每天收到N枚金幣后，騎士會(huì)在之后的連續(xù)N+1天里, 每天收到N+1枚金幣。請計(jì)算在前K天里，騎士一共獲得了多少金幣?！据斎敫袷健枯斎胛募麨?。輸入文件

4、只有1行，包含一個(gè)正整數(shù)K，表示發(fā)放金幣的天數(shù)?！据敵龈袷健枯敵鑫募麨椤］敵鑫募挥?行，包含一個(gè)正整數(shù)，即騎士收到的金幣數(shù)?！据斎胼敵鰳永?】614見選手目錄下的coin/和coin/?！据斎胼敵鰳永?說明】騎士第一天收到一枚金幣；第二天和第三天，每天收到兩枚金幣；第四、五、六 天，每天收到三枚金幣。因此一共收到1+2+2+3+3+3=14枚金幣。【輸入輸出樣例2】100029820見選手目錄下的coin/和coin/?！緮?shù)據(jù)說明】對(duì)于100%的數(shù)據(jù)，1K10,000。2.掃雷游戲（c/pas ）掃雷游戲是一款十分經(jīng)典的單機(jī)小游戲。在n行m列的雷區(qū)中有一些格子含有地雷（稱之為地雷格），其他

5、格子不含地雷（稱之為非地雷格）。玩家翻開一個(gè)非地雷格時(shí), 該格將會(huì)出現(xiàn)一個(gè)數(shù)字一一提示周圍格子中有多少個(gè)是地雷格。游戲的目標(biāo)是在不翻出 任何地雷格的條件下，找出所有的非地雷格。現(xiàn)在給出n行m列的雷區(qū)中的地雷分布，要求計(jì)算出每個(gè)非地雷格周圍的地雷格 數(shù)。注：一個(gè)格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八個(gè)方 向上與之直接相鄰的格子?！据斎敫袷健枯斎胛募麨?。輸入文件第一行是用一個(gè)空格隔開的兩個(gè)整數(shù)n和m，分別表示雷區(qū)的行數(shù)和列數(shù)接下來n行，每行m個(gè)字符，描述了雷區(qū)中的地雷分布情況。字符*表示相應(yīng)格子是地雷格，字符？表示相應(yīng)格子是非地雷格。相鄰字符之間無分隔符?！据敵龈袷健枯敵鑫?/p>

6、件名為。輸出文件包含n行，每行m個(gè)字符，描述整個(gè)雷區(qū)。用*表示地雷格，用周圍的地 雷個(gè)數(shù)表示非地雷格。相鄰字符之間無分隔符。【輸入輸出樣例1】3 3 *?*?*102211*1見選手目錄下的mine/和mine/?！据斎胼敵鰳永?】2 3 ?*?*?2*1*21見選手目錄下的mine/和mine/。【輸入輸出樣例3】見選手目錄下的mine/和mine/?！緮?shù)據(jù)說明】對(duì)于100%的數(shù)據(jù)，1WnWIOO,1m100o3.求和c/pas)一條狹長的紙帶被均勻劃分出了n 個(gè)格子，格子編號(hào)從1 到 n。每個(gè)格子上都染了一種顏色?用?1 , m當(dāng)中的一個(gè)整數(shù)表示)，并且寫了一個(gè)數(shù)字？?5532221234

7、56組要求滿足以下兩個(gè)條件:1.?, ?都是整數(shù),? ? ?, ? - ? = ? - ?2.?=?滿足上述條件的三元組的分?jǐn)?shù)規(guī)定為(x + z) ? (?+?整個(gè)紙帶的分?jǐn)?shù)規(guī)定為所有滿足條件的三元組的分?jǐn)?shù)的和。這個(gè)分?jǐn)?shù)可能會(huì)很大，你只要輸出整個(gè)紙帶的分?jǐn)?shù)除以 10,007 所得的余數(shù)即可?！据斎敫袷健枯斎胛募麨?。第一行是用一個(gè)空格隔開的兩個(gè)正整數(shù)的種類數(shù)。第二行有？個(gè)用空格隔開的正整數(shù)，第字。第三行有？個(gè)用空格隔開的正整數(shù)，第【輸出格式】輸出文件名為共一行，一個(gè)整數(shù)，表示所求的紙帶分?jǐn)?shù)除以10,007 所得的余數(shù)。【輸入輸出樣例1】6 25 5 3 2 2 22 2 1 1 2 182見選

8、手目錄下的sum/和sum/?！据斎胼敵鰳永?1 說明】紙帶如題目描述中的圖所示。定義一種特殊的三元組：(x, y, z)，其中 x, y, z 都代表紙帶上格子的編號(hào)，這里的三兀?和？?，？代表紙帶上格子的個(gè)數(shù)，？弋表紙帶上顏色?個(gè)數(shù)字？?代表紙帶上編號(hào)為?的格子上面寫的數(shù)?個(gè)數(shù)字？?代?紙帶上編號(hào)為?的格子染的顏色。編號(hào)所有滿足條件的三元組為： (1,3, 5), (4, 5, 6) 。所以紙帶的分?jǐn)?shù)為 (1 + 5) ? (5 + 2) + (4 + 6) ? (2 + 2) = 42 + 40 = 82【輸入輸出樣例 2】15 45 10 8 2 2 2 9 9 7 7 5 6 4 2

9、 42 2 3 3 4 3 3 2 4 4 4 4 1 1 11388見選手目錄下的sum/和sum/?！据斎胼敵鰳永?3】見選手目錄下的sum/和sum/【數(shù)據(jù)說明】對(duì)于第1組至第2組數(shù)據(jù)，1?100,1對(duì)于第3組至第4組數(shù)據(jù)，1w?3000, 1超過20的顏色;?w?TO0000ow?w100對(duì)于第5組至第6組數(shù)據(jù)，1w?w100000, 1對(duì)于全部10組數(shù)據(jù),1w?ww?w1俛?,?且不存在4.推銷員c/pas)【問題描述】阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產(chǎn)品。螺絲街是一條死胡同，出口與入口是同一個(gè)，街道的一側(cè)是圍墻，另一側(cè)是住戶。螺絲街一共有N 家住戶，第 i 家住戶到入

10、口的距離為 Si米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的 距離相等。阿明會(huì)從入口進(jìn)入，依次向螺絲街的X 家住戶推銷產(chǎn)品，然后再原路走出去。阿明每走 1 米就會(huì)積累 1 點(diǎn)疲勞值，向第 i 家住戶推銷產(chǎn)品會(huì)積累 Ai點(diǎn)疲勞值。阿明是工作狂，他想知道，對(duì)于不同的X，在不走多余的路的前提下，他最多可以積累多少點(diǎn)疲勞值。【輸入格式】輸入文件名為。第一行有一個(gè)正整數(shù) N，表示螺絲街住戶的數(shù)量。接下來的一行有 N 個(gè)正整數(shù)，其中第 i 個(gè)整數(shù) Si表示第 i 家住戶到入口的距離。數(shù)據(jù)保證SiWS2W令n108。接下來的一行有 N 個(gè)正整數(shù)，其中第 i 個(gè)整數(shù) Ai表示向第 i 戶住戶

11、推銷產(chǎn)品會(huì)積累的疲勞 值。數(shù)據(jù)保證Ai103?！据敵龈袷健枯敵鑫募麨椤］敵?N 行，每行一個(gè)正整數(shù)，第i 行整數(shù)表示當(dāng) X=i 時(shí)，阿明最多積累的疲勞值?！据斎胼敵鰳永?】51 2 3 4 51 2 3 4 51519222425見選手目錄下的 salesman/禾口 salesman/?！据斎胼敵鰳永?說明】X=1:向住戶5推銷，往返走路的疲勞值為5+5，推銷的疲勞值為5,總疲勞值為15。X=2:向住戶4、5推銷，往返走路的疲勞值為5+5，推銷的疲勞值為4+5,總疲勞值為5+5+4+5=19。X=3:向住戶3、4、5推銷，往返走路的疲勞值為5+5,推銷的疲勞值3+4+5,總疲勞值為5+5+

12、3+4+5=22。X=4:向住戶2、3、4、5推銷，往返走路的疲勞值為5+5，推銷的疲勞值2+3+4+5，總疲勞值5+5+2+3+4+5=24。X=5:向住戶1、2、3、4、5推銷，往返走路的疲勞值為5+5，推銷的疲勞值1+2+3+4+5，總疲勞值5+5+1+2+3+4+5=25?！据斎胼敵鰳永?】51 2 2 4 55 4 3 4 11217212427見選手目錄下的 salesman/禾口 salesman/?！据斎胼敵鰳永?說明】X=1 :向住戶 4 推銷，往返走路的疲勞值為4+4,推銷的疲勞值為4，總疲勞值4+4+4=12。X=2 :向住戶 1、4 推銷，往返走路的疲勞值為4+4，推銷的疲勞值為5+4，總疲勞值 4+4+5+4=17。X=3 :向住戶 1、2、4 推銷，往返走路的疲勞值為4+4，推銷的疲勞值為5+4+4，總疲勞值 4+4+5+4+4=21。X=4 :向住戶 1、2、3、4 推銷，往返走路的疲勞值為4+4，推銷的疲勞值為5+4+3+4，總疲勞值 4+4+5+4+3+4=24?；蛘呦蜃?1、2、4、5 推銷，往返走路的疲勞值 為5+5，推銷的疲勞值為5+4+4+1，總疲勞值 5+5+5+4+4+仁