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

1、CCF 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽 普及組 （請(qǐng)選手務(wù)必認(rèn)真閱讀本頁內(nèi)容） 一題目概況 中文題目名稱 金幣 掃雷玩耍 求和 推銷員 英文題目與子名目名 coin mine sum salesman 可執(zhí)行文件名 coin mine sum salesman 輸入文件名 coin.in mine.in sum.in salesman.in 輸出文件名 coin.out mine.out sum.out salesman.out 每個(gè)測(cè)試點(diǎn)時(shí)限 1 秒 1 秒 1 秒 1 秒 測(cè)試點(diǎn)數(shù)目 10 10 10 10 每個(gè)測(cè)試點(diǎn)分值 10 10 10 10 附加樣例文件 有 有 有

2、有 結(jié)果比較方式 全文比較（過濾行末空格及文末回車） 題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運(yùn)行內(nèi)存上限 128M 128M 128M 128M 二提交源程序文件名 對(duì)于 C+語言 coin.cpp mine.cpp sum.cpp salesman.cpp 對(duì)于 C 語言 coin.c mine.c sum.c salesman.c 對(duì)于 pascal 語言 coin.pas mine.pas sum.pas salesman.pas 三編譯命令（不包含任何優(yōu)化開關(guān)） 對(duì)于 C+語言 g+ -o coin coin.cpp -lm g+ -o mine mine.cpp -lm g+ -o su

3、m sum.cpp -lm g+ -o salesman salesman.cpp -lm 對(duì)于 C 語言 gcc -o coin coin.c -lm gcc -o mine mine.c -lm gcc -o sum sum.c -lm gcc -o salesman salesman.c -lm 對(duì)于 pascal 語言 fpc coin.pas fpc mine.pas fpc sum.pas fpc salesman.pas 留意事項(xiàng)： 1、 文件名（程序名和輸入輸出文件名）必需使用英文小寫。 2、 C/C+中函數(shù) main()的返回值類型必需是 int，程序正常結(jié)束時(shí)的返回值必需是

4、 0。 3、 全國統(tǒng)一評(píng)測(cè)時(shí)接受的機(jī)器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，內(nèi)存 4G，上述時(shí)限以此配置為準(zhǔn)。 4、 只供應(yīng) Linux 格式附加樣例文件。 5、 特殊提示：評(píng)測(cè)在當(dāng)前最新公布的 NOI Linux 下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。 1. 金幣 (coin.cpp/c/pas) 國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（其次天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣；這種工資發(fā)放模式會(huì)始終這樣連續(xù)下

5、去：當(dāng)連續(xù) N 天每天收到 N 枚金幣后，騎士會(huì)在之后的連續(xù) N+1 天里，每天收到 N+1 枚金幣。 請(qǐng)計(jì)算在前 K 天里，騎士一共獲得了多少金幣。 【輸入格式】 輸入文件名為 coin.in。 輸入文件只有 1 行，包含一個(gè)正整數(shù) K，表示發(fā)放金幣的天數(shù)。 【輸出格式】 輸出文件名為 coin.out。 輸出文件只有 1 行，包含一個(gè)正整數(shù)，即騎士收到的金幣數(shù)。 【輸入輸出樣例 1】 coin.in coin.out 6 14 見選手名目下的 coin/coin1.in 和 coin/coin1.ans。 【輸入輸出樣例 1 說明】 騎士第一天收到一枚金幣；其次天和第三天，每天收到兩枚金幣

6、；第四、五、六天，每天收到三枚金幣。因此一共收到 1+2+2+3+3+3=14 枚金幣。 【輸入輸出樣例 2】 coin.in coin.out 1000 29820 見選手名目下的 coin/coin2.in 和 coin/coin2.ans。 【數(shù)據(jù)說明】 對(duì)于 100%的數(shù)據(jù)，1 K 10,000。 2. 掃雷玩耍 （mine.cpp/c/pas） 掃雷玩耍是一款格外經(jīng)典的單機(jī)小玩耍。在 n 行 m 列的雷區(qū)中有一些格子含有地雷（稱之為地雷格），其他格子不含地雷（稱之為非地雷格）。玩家翻開一個(gè)非地雷格時(shí)，該格將會(huì)消滅一個(gè)數(shù)字提示四周格子中有多少個(gè)是地雷格。玩耍的目標(biāo)是在不翻出任何地雷格的

7、條件下，找出全部的非地雷格。 現(xiàn)在給出n行m列的雷區(qū)中的地雷分布，要求計(jì)算出每個(gè)非地雷格四周的地雷格數(shù)。 注：一個(gè)格子的四周格子包括其上、下、左、右、左上、右上、左下、右下八個(gè)方向上與之直接相鄰的格子。 【輸入格式】 輸入文件名為 mine.in。 輸入文件第一行是用一個(gè)空格隔開的兩個(gè)整數(shù)n和m，分別表示雷區(qū)的行數(shù)和列數(shù)。 接下來 n 行，每行 m 個(gè)字符，描述了雷區(qū)中的地雷分布狀況。字符*表示相應(yīng)格子是地雷格，字符?表示相應(yīng)格子是非地雷格。相鄰字符之間無分隔符。 【輸出格式】 輸出文件名為 mine.out。 輸出文件包含 n 行，每行 m 個(gè)字符，描述整個(gè)雷區(qū)。用*表示地雷格，用四周的地雷

8、個(gè)數(shù)表示非地雷格。相鄰字符之間無分隔符。 【輸入輸出樣例 1】 mine.in mine.out 3 3 *? ? ?*? *10 221 1*1 見選手名目下的 mine/mine1.in 和 mine/mine1.ans。 【輸入輸出樣例 2】 mine.in mine.out 2 3 ?*? *? 2*1 *21 見選手名目下的 mine/mine2.in 和 mine/mine2.ans。 【輸入輸出樣例 3】 見選手名目下的 mine/mine3.in 和 mine/mine3.ans。 【數(shù)據(jù)說明】 對(duì)于 100%的數(shù)據(jù)，1n100，1m100。 3. 求和 (sum.cpp/c/

9、pas) 一條狹長的紙帶被均勻劃分出了 n 個(gè)格子，格子編號(hào)從 1 到 n。每個(gè)格子上都染了一種顏色𝑐𝑜𝑙𝑜𝑟𝑖（用1，m當(dāng)中的一個(gè)整數(shù)表示），并且寫了一個(gè)數(shù)字𝑛𝑢𝑚𝑏𝑒𝑟𝑖。 5 5 3 2 2 2 1 2 3 4 5 6 編號(hào) 定義一種特殊的三元組：(x, y, z)，其中 x，y，z 都代表紙帶上格子的編號(hào)，這里的三元組要求滿足以下兩個(gè)條件： 1. 𝑥, ү

10、10;, 𝑧都是整數(shù), 𝑥 < 𝑦 < 𝑧, 𝑦 𝑥 = 𝑧 𝑦 2. 𝑐𝑜𝑙𝑜𝑟𝑥 = 𝑐𝑜𝑙𝑜𝑟𝑧 滿足上述條件的三元組的分?jǐn)?shù)規(guī)定為(x + z) (𝑛𝑢𝑚𝑏𝑒𝑟

11、19909; + 𝑛𝑢𝑚𝑏𝑒𝑟𝑧)。整個(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ù)。 其次行有𝑛個(gè)用空格隔開的正整數(shù)，第𝑖個(gè)數(shù)字𝑛𝑢

12、19898;𝑏𝑒𝑟𝑖代表紙帶上編號(hào)為𝑖的格子上面寫的數(shù)字。 第三行有𝑛個(gè)用空格隔開的正整數(shù)，第𝑖個(gè)數(shù)字𝑐𝑜𝑙𝑜𝑟𝑖代表紙帶上編號(hào)為𝑖的格子染的顏色。 【輸出格式】 輸出文件名為 sum.out。 共一行，一個(gè)整數(shù)，表示所求的紙帶分?jǐn)?shù)除以 10,007 所得的余數(shù)。 【輸入輸出樣例 1】 sum.in sum.out 6 2 5 5 3 2 2 2 2 2 1 1 2 1 8

13、2 見選手名目下的 sum/sum1.in 和 sum/sum1.ans。 【輸入輸出樣例 1 說明】 紙帶如題目描述中的圖所示。 全部滿足條件的三元組為：(1,3, 5), (4, 5, 6)。 所以紙帶的分?jǐn)?shù)為(1 + 5) (5 + 2) + (4 + 6) (2 + 2) = 42 + 40 = 82。 歡迎下載【輸入輸出樣例 2】 sum.in sum.out 15 4 5 10 8 2 2 2 9 9 7 7 5 6 4 2 4 2 2 3 3 4 3 3 2 4 4 4 4 1 1 1 1388 見選手名目下的 sum/sum2.in 和 sum/sum2.ans。 【輸入輸出樣

14、例 3】見選手名目下的 sum/sum3.in 和 sum/sum3.ans。 【數(shù)據(jù)說明】對(duì)于第 1 組至第 2 組數(shù)據(jù)，1 𝑛 100, 1 𝑚 5； 對(duì)于第 3 組至第 4 組數(shù)據(jù)，1 𝑛 3000, 1 𝑚 100； 對(duì)于第 5 組至第 6 組數(shù)據(jù)，1 𝑛 100000, 1 𝑚 100000，且不存在消滅次數(shù)超過 20 的顏色； 對(duì)于全部 10 組數(shù)據(jù)， 1 𝑛 100000, 1 𝑚 100000, 1 𝑐𝑜𝑙

15、;𝑜𝑟𝑖 𝑚, 1 𝑛𝑢𝑚𝑏𝑒𝑟𝑖 100000。 4. 推銷員 (salesman.cpp/c/pas) 【問題描述】 阿明是一名推銷員，他奉命到螺絲街推銷他們公司的產(chǎn)品。螺絲街是一條死胡同，出口與入口是同一個(gè)，街道的一側(cè)是圍墻，另一側(cè)是住戶。螺絲街一共有 N 家住戶，第 i 家住戶到入口的距離為 Si 米。由于同一棟房子里可以有多家住戶，所以可能有多家住戶與入口的距離相等。阿明會(huì)從入口進(jìn)入，依次向螺絲街的 X 家住戶

16、推銷產(chǎn)品，然后再原路走出去。 阿明每走 1 米就會(huì)積累 1 點(diǎn)疲憊值，向第 i 家住戶推銷產(chǎn)品會(huì)積累 Ai 點(diǎn)疲憊值。阿明是工作狂，他想知道，對(duì)于不同的 X，在不走多余的路的前提下，他最多可以積累多少點(diǎn)疲憊值。 【輸入格式】 輸入文件名為 salesman.in。 第一行有一個(gè)正整數(shù) N，表示螺絲街住戶的數(shù)量。 接下來的一行有 N 個(gè)正整數(shù)，其中第 i 個(gè)整數(shù) Si 表示第 i 家住戶到入口的距離。數(shù)據(jù)保證 S1S2Sn<108。 接下來的一行有 N 個(gè)正整數(shù)，其中第 i 個(gè)整數(shù) Ai 表示向第 i 戶住戶推銷產(chǎn)品會(huì)積累的疲憊值。數(shù)據(jù)保證 Ai<103。 【輸出格式】 輸出文件名為

17、 salesman.out。 輸出 N 行，每行一個(gè)正整數(shù)，第 i 行整數(shù)表示當(dāng) X=i 時(shí)，阿明最多積累的疲憊值。 【輸入輸出樣例 1】 salesman.in salesman.out 5 1 2 3 4 5 1 2 3 4 5 15 19 22 24 25 見選手名目下的 salesman/salesman1.in 和 salesman/salesman1.ans。 【輸入輸出樣例 1 說明】 X=1: 向住戶 5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值為 5，總疲憊值為15。 X=2: 向住戶 4、5 推銷，來回走路的疲憊值為 5+5，推銷的疲憊值為 4+5，總疲憊值為 5+5

18、+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，推銷的疲憊值 1+2+3+4+5，總疲憊值 5+5+1+2+3+4+5=25。 【輸入輸出樣例 2】 salesman.in salesman.out 5 1 2 2 4 5 5 4 3 4 1 12 17 21 24 27 見選手名目下的 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。 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