1、全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽普及組CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015 ）復(fù)賽普及組（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）一.題目概況文文題目名稱金幣掃雷游戲求和推銷員英文題目與子目錄名coinminesumsalesman可執(zhí)行文件名coinminesumsalesman輸入文件名coin.inmine.insum.insalesman.in輸出文件名coin.outmine.outsum.outsalesman.out每個(gè)測試點(diǎn)時(shí)限1秒1秒1秒1秒測試點(diǎn)數(shù)目10101010每個(gè)測試點(diǎn)分值10101010附加樣例文件有有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題

2、目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M128M128M.提交源程序文件名對(duì)于C+語百coin.cppmine.cppsum.cppsalesman.cpp對(duì)于C語言coin.cmine.csum.csalesman.c對(duì)于pascal語百coin.pasmine.passum.passalesman.pas三.編譯命令（不包含任何優(yōu)化開關(guān)）對(duì)于C+語百g+ -o coin coin.cpp -lmg+ -o mine mine.cpp -lmg+ -o sum sum.cpp -lmg+ -o salesman salesman.cpp -lm對(duì)于C語言gcc -o coin co

3、in.cgcc -o mine mine.cgcc -o sumgcc -o salesman-lm-lmsum.c -lmsalesman.c -lm對(duì)于pascal語百fpccoin.pasfpcmine.pasfpcsum.pasfpcsalesman.pas【問題描述】注意事項(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 , 2.8GHz ,內(nèi)存4G,上述時(shí)限以此配置為準(zhǔn)。4、

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

5、正整數(shù) K,表示發(fā)放金幣的天數(shù)?！据敵龈袷健枯敵鑫募麨閏oin.out。輸出文件只有1行，包含一個(gè)正整數(shù)，即騎士收到的金幣數(shù)?！据斎胼敵鰳永?】coin.incoin.out【問題描述】614見選手目錄下的 coin/coinl.in 和 coin/coinl.ans。【輸入輸出樣例1說明】騎士第一天收到一枚金幣；第二天和第三天，每天收到兩枚金幣；第四、五、六天, 每天收到三枚金幣。因此一共收到1+2+2+3+3+3=14枚金幣?！据斎胼敵鰳永?】coin.incoin.out100029820見選手目錄下的 coin/coin2.in 和 coin/coin2.ans?！緮?shù)據(jù)說明】對(duì)于 1

6、00% 的數(shù)據(jù)，1 < K < 10,00002.掃雷游戲（mine.cpp/c/pas ）掃雷游戲是一款十分經(jīng)典的單機(jī)小游戲。在n行m列的雷區(qū)中有一些格子含有地雷（稱之為地雷格），其他格子不含地雷（稱之為非地雷格）。玩家翻開一個(gè)非地雷格時(shí), 該格將會(huì)出現(xiàn)一個(gè)數(shù)字一一提示周圍格子中有多少個(gè)是地雷格。游戲的目標(biāo)是在不翻出任何地雷格的條件下，找出所有的非地雷格。現(xiàn)在給出n行m列的雷區(qū)中的地雷分布，要求計(jì)算出每個(gè)非地雷格周圍的地雷格數(shù)。第3頁共10頁全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽普及組【問題描述】注：一個(gè)格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八個(gè)方 向

7、上與之直接相鄰的格子。【輸入格式】輸入文件名為mine.in。輸入文件第一行是用一個(gè)空格隔開的兩個(gè)整數(shù)n和m,分別表示雷區(qū)的行數(shù)和列數(shù)。接下來n行，每行m個(gè)字符，描述了雷區(qū)中的地雷分布情況。字符 *'表示相應(yīng) 格子是地雷格，字符？表示相應(yīng)格子是非地雷格。相鄰字符之間無分隔符?！据敵龈袷健枯敵鑫募麨閙ine.out。輸出文件包含n行，每行m個(gè)字符，描述整個(gè)雷區(qū)。用*'表示地雷格，用周圍的地 雷個(gè)數(shù)表示非地雷格。相鄰字符之間無分隔符?！据斎胼敵鰳永?】mine.inmine.out3 3 *?*10?221?*?1*1見選手目錄下的 mine/minel.in 和 mine/mi

8、nel.ans。【輸入輸出樣例2】mine.inmine.out2 3 ?*?*?2*1*21見選手目錄下的 mine/mine2.in 和 mine/mine2.ans。【問題描述】見選手目錄下的 mine/mine3.in 和 mine/mine3.ans。【數(shù)據(jù)說明】對(duì)于100%的數(shù)據(jù)，1&n<100,1 <m<10Oo3.求和（sum.cpp/c/pas）一條狹長的紙帶被均勻劃分出了n個(gè)格子，格子編號(hào)從1到no每個(gè)格子上都染了一種顏色？?？?R , m當(dāng)中的一個(gè)整數(shù)表示），并且寫了一個(gè)數(shù)字 ？?？?？?？編號(hào)5532第9頁共10頁定義一種特殊白三元組：（x,

9、y, z）,其中x, v, z都代表紙帶上格子的編號(hào)，這里的三元 組要求滿足以下兩個(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ù)即可。【輸入格式】輸入文件名為sum.in。第一行是用一個(gè)空格隔開的兩個(gè)正整數(shù)?和？?，？代表紙帶上格子的個(gè)數(shù)，？?代表紙帶上顏色的種類數(shù)。第二行有？野用空格隔開的正整數(shù)，第?數(shù)字？?薇?氏帶上編號(hào)為我格子上面寫的數(shù)第三行有？牛用空格隔開的正整數(shù)，第?數(shù)字？?硒怒紙

10、帶上編號(hào)為渤格子染的顏色?！締栴}描述】【輸出格式】輸出文件名為sum.out。共一行，一個(gè)整數(shù)，表示所求的紙帶分?jǐn)?shù)除以10,007所得的余數(shù)?！据斎胼敵鰳永?】sum.insum.out6 25 5 3 2 2 22 2 1 1 2 182見選手目錄下的 sum/sum1.in 和 sum/suml.ans【輸入輸出樣例1說明】紙帶如題目描述中的圖所示。所有滿足條件的三元組為：(1,3, 5),(4, 5, 6)。所以紙帶的分?jǐn)?shù)為(1 + 5) ? (5 + 2) + (4 + 6) ?(2 + 2) = 42 + 40 = 82【輸入輸出樣例 2】sum.insum.out15 45 10

11、8 2 2 2 9 9 7 7 5 6 4 2 413882 2 3 3 4 3 3 2 4 4 4 4 1 1 1見選手目錄下的 sum/sum2.in和sum/sum2.an&【輸入輸出樣例3】見選手目錄下的sum/sum3.in和sum/sum3.an$【數(shù)據(jù)說明】對(duì)于第1組至第2組數(shù)據(jù)，1 & ? 100, 14 ?震5對(duì)于第3組至第4組數(shù)據(jù)，1 < ? 3000, 1« 1?對(duì)于第5組至第6組數(shù)據(jù)，1 < ? 100000, 1«100000,且不存在出現(xiàn)次數(shù)超過20的顏色；對(duì)于全部 10 組數(shù)據(jù)，1 < ? 100000, 1&

12、#171;100000,1加?）0000。4.推銷員(salesman.cpp/c/pas)【問題描述】阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產(chǎn)品。螺絲街是一條死胡同，出口與入口是同一個(gè)，街道的一側(cè)是圍墻，另一側(cè)是住戶。螺絲街一共有N家住戶，第i家住戶到入口的距離為 Si米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的距離相等。阿明會(huì)從入口進(jìn)入，依次向螺絲街的X家住戶推銷產(chǎn)品，然后再原路走出去。阿明每走1米就會(huì)積累1點(diǎn)疲勞值，向第i家住戶推銷產(chǎn)品會(huì)積累 Ai點(diǎn)疲勞值。阿明是工作狂，他想知道，對(duì)于不同的 X,在不走多余的路的前提下，他最多可以積累多少點(diǎn)疲勞 值?！据斎敫袷健?/p>

13、輸入文件名為 salesman.in。第一行有一個(gè)正整數(shù) N,表示螺絲街住戶的數(shù)量。接下來的一行有 N個(gè)正整數(shù)，其中第 i個(gè)整數(shù)Si表示第i家住戶到入口的距離。數(shù)據(jù)保證 S1WS2W 冷n<108。接下來的一行有 N個(gè)正整數(shù)，其中第i個(gè)整數(shù)Ai表示向第i戶住戶推銷產(chǎn)品會(huì)積累的疲勞值。 數(shù)據(jù)彳證Ai<103。【輸出格式】輸出文件名為salesman.out輸出N行，每行一個(gè)正整數(shù)，第 i行整數(shù)表示當(dāng)X=i時(shí)，阿明最多積累的疲勞值?！据斎胼敵鰳永?】salesman.insalesman.out5151 2 3 4 5191 2 3 4 5222425見選手目錄下的 salesman/

14、salesmanl.in 和 salesman/salesmanl.ans【輸入輸出樣例1說明】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+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,推

15、銷的疲勞值1+2+3+4+5 ,總疲勞值 5+5+1+2+3+4+5=25?！据斎胼敵鰳永?】salesman.insalesman.out51 2 2 4 55 4 3 4 11217212427見選手目錄下的 salesman/salesman2.in 和 salesman/salesman2.ans【輸入輸出樣例2說明】X=1 :向住戶4推銷，往返走路的疲勞值為 4+4,推銷的疲勞值為 4,總疲勞值4+4+4=12。X=2:向住戶1、4推銷，往返走路的疲勞值為 4+4,推銷的疲勞值為5+4,總疲勞值4+4+5+4=17。全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽普及組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?；蛘呦蜃?、2、4、5推銷，往返走路的疲勞值為 5+5,推銷 的疲勞值為 5+4+4+1