1、精選優(yōu)質(zhì)文檔-傾情為你奉上CCF全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 普及組 （請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容） 一題目概況 中文題目名稱 成績(jī) 圖書(shū)管理員 棋盤 跳房子 英文題目與子目錄名 score librarian chess jump 可執(zhí)行文件名 score librarian chess jump 輸入文件名 score.in librarian.in chess.in jump.in 輸出文件名 score.out librarian.out chess.out jump.out 每個(gè)測(cè)試點(diǎn)時(shí)限 1 秒 1 秒 1 秒 2 秒 測(cè)試點(diǎn)數(shù)目 10 10 20 10 每個(gè)測(cè)試

2、點(diǎn)分值 10 10 5 10 附加樣例文件 有 有 有 有 結(jié)果比較方式 全文比較（過(guò)濾行末空格及文末回車） 題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運(yùn)行內(nèi)存上限 256M 256M 256M 256M 二提交源程序文件名 對(duì)于 C+語(yǔ)言 score.cpp librarian.cpp chess.cpp jump.cpp 對(duì)于 C 語(yǔ)言 score.c librarian.c chess.c jump.c 對(duì)于 pascal 語(yǔ)言 score.pas librarian.pas chess.pas jump.pas 三編譯命令（不包含任何優(yōu)化開(kāi)關(guān)） 對(duì)于 C+語(yǔ)言 g+ -o score scor

3、e.cpp -lm g+ -o librarian librarian.cpp -lm g+ -o chess chess.cpp -lm g+ -o jump jump.cpp -lm 對(duì)于 C 語(yǔ)言 gcc -o score score.c -lm gcc -o librarian librarian.c -lm gcc -o chess chess.c -lm gcc -o jump jump.c -lm 對(duì)于 pascal 語(yǔ)言 fpc score.pas fpc librarian.pas fpc chess.pas fpc jump.pas 注意事項(xiàng)： 1、 文件名（程序名和輸入輸

4、出文件名）必須使用英文小寫(xiě)。 2、 C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時(shí)的返回值必須是 0。 3、 全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，內(nèi)存 4G，上述時(shí)限以此配置為準(zhǔn)。 4、 只提供 Linux 格式附加樣例文件。 5、 提交的程序代碼文件的放置位置請(qǐng)參照各省的具體要求。 6、 特別提醒：評(píng)測(cè)在當(dāng)前最新公布的 NOI Linux 下進(jìn)行，各語(yǔ)言的編譯器版本以其為準(zhǔn)。 1. 成績(jī) (score.cpp/c/pas) 【問(wèn)題描述】 牛牛最近學(xué)習(xí)了 C+入門課程，這門課程的總成

5、績(jī)計(jì)算方法是： 總成績(jī)=作業(yè)成績(jī)×20%+小測(cè)成績(jī)×30%+期末考試成績(jī)×50% 牛牛想知道，這門課程自己最終能得到多少分。 【輸入格式】 輸入文件名為 score.in。 輸入文件只有 1 行，包含三個(gè)非負(fù)整數(shù)A、B、C，分別表示牛牛的作業(yè)成績(jī)、小測(cè)成績(jī)和期末考試成績(jī)。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)，三項(xiàng)成績(jī)滿分都是 100 分。 【輸出格式】 輸出文件名為 score.out。 輸出文件只有 1 行，包含一個(gè)整數(shù)，即牛牛這門課程的總成績(jī)，滿分也是 100 分。 【輸入輸出樣例 1】 score.in score.out 100 100 80 90 見(jiàn)選手目錄下的

6、 score/score1.in 和 score/score1.ans。 【輸入輸出樣例 1 說(shuō)明】 牛牛的作業(yè)成績(jī)是 100 分，小測(cè)成績(jī)是 100 分，期末考試成績(jī)是 80 分，總成績(jī)是 100×20%+100×30%+80×50%=20+30+40=90。 【輸入輸出樣例 2】 score.in score.out 60 90 80 79 見(jiàn)選手目錄下的 score/score2.in 和 score/score2.ans。 【輸入輸出樣例 2 說(shuō)明】 牛牛的作業(yè)成績(jī)是 60 分，小測(cè)成績(jī)是 90 分，期末考試成績(jī)是 80 分，總成績(jī)是 60×20

7、%+90×30%+80×50%=12+27+40=79。 【數(shù)據(jù)說(shuō)明】 對(duì)于 30% 的數(shù)據(jù)，A=B=0。 對(duì)于另外 30% 的數(shù)據(jù)，A=B=100。 對(duì)于 100% 的數(shù)據(jù)， 0A、B、C100 且 A、B、C 都是 10 的整數(shù)倍。 2. 圖書(shū)管理員 (librarian.cpp/c/pas) 【問(wèn)題描述】 圖書(shū)館中每本書(shū)都有一個(gè)圖書(shū)編碼，可以用于快速檢索圖書(shū)，這個(gè)圖書(shū)編碼是一個(gè)正整數(shù)。 每位借書(shū)的讀者手中有一個(gè)需求碼，這個(gè)需求碼也是一個(gè)正整數(shù)。如果一本書(shū)的圖書(shū)編碼恰好以讀者的需求碼結(jié)尾，那么這本書(shū)就是這位讀者所需要的。 小 D 剛剛當(dāng)上圖書(shū)館的管理員，她知道圖書(shū)館里所

8、有書(shū)的圖書(shū)編碼，她請(qǐng)你幫她寫(xiě)一個(gè)程序，對(duì)于每一位讀者，求出他所需要的書(shū)中圖書(shū)編碼最小的那本書(shū)，如果沒(méi)有他需要的書(shū)，請(qǐng)輸出-1。 【輸入格式】 輸入文件名為librarian.in。 輸入文件的第一行，包含兩個(gè)正整數(shù) n 和 q，以一個(gè)空格分開(kāi)，分別代表圖書(shū)館里書(shū)的數(shù)量和讀者的數(shù)量。 接下來(lái)的 n 行，每行包含一個(gè)正整數(shù)，代表圖書(shū)館里某本書(shū)的圖書(shū)編碼。 接下來(lái)的 q 行，每行包含兩個(gè)正整數(shù)，以一個(gè)空格分開(kāi)，第一個(gè)正整數(shù)代表圖書(shū)館里讀者的需求碼的長(zhǎng)度，第二個(gè)正整數(shù)代表讀者的需求碼。 【輸出格式】 輸出文件名為librarian.out。 輸出文件有 q 行，每行包含一個(gè)整數(shù)，如果存在第 i 個(gè)讀者

9、所需要的書(shū)，則在第 i 行輸出第 i 個(gè)讀者所需要的書(shū)中圖書(shū)編碼最小的那本書(shū)的圖書(shū)編碼，否則輸出-1。 【輸入輸出樣例 1】 librarian.in librarian.out 5 5 2123 1123 23 24 24 2 23 3 123 3 124 2 12 2 12 23 1123 -1 -1 -1 見(jiàn)選手目錄下的librarian /librarian1.in和librarian/librarian1.ans。 【輸入輸出樣例 1 說(shuō)明】 第一位讀者需要的書(shū)有 2123、1123、23，其中 23 是最小的圖書(shū)編碼。第二位讀者需要的書(shū)有 2123、1123，其中 1123 是最小

10、的圖書(shū)編碼。對(duì)于第三位，第四位和第五位讀者，沒(méi)有書(shū)的圖書(shū)編碼以他們的需求碼結(jié)尾，即沒(méi)有他們需要的書(shū)，輸出-1。 【輸入輸出樣例 2】 見(jiàn)選手目錄下的librarian/librarian2.in和librarian/librarian2.ans。 【數(shù)據(jù)規(guī)模與約定】 對(duì)于 20%的數(shù)據(jù)，1 n 2。 另有 20%的數(shù)據(jù)，q = 1。 另有 20%的數(shù)據(jù)，所有讀者的需求碼的長(zhǎng)度均為 1。 另有 20%的數(shù)據(jù)，所有的圖書(shū)編碼按從小到大的順序給出。 對(duì)于 100%的數(shù)據(jù)，1 n 1,000，1 q 1,000，所有的圖書(shū)編碼和需求碼均不超過(guò) 10,000,000。 3. 棋盤 (chess.cpp/

11、c/pas) 【問(wèn)題描述】 有一個(gè)m × m的棋盤，棋盤上每一個(gè)格子可能是紅色、黃色或沒(méi)有任何顏色的。你現(xiàn)在要從棋盤的最左上角走到棋盤的最右下角。 任何一個(gè)時(shí)刻，你所站在的位置必須是有顏色的（不能是無(wú)色的），你只能向上、下、左、右四個(gè)方向前進(jìn)。當(dāng)你從一個(gè)格子走向另一個(gè)格子時(shí)，如果兩個(gè)格子的顏色相同，那你不需要花費(fèi)金幣；如果不同，則你需要花費(fèi) 1 個(gè)金幣。 另外，你可以花費(fèi) 2 個(gè)金幣施展魔法讓下一個(gè)無(wú)色格子暫時(shí)變?yōu)槟阒付ǖ念伾?。但這個(gè)魔法不能連續(xù)使用，而且這個(gè)魔法的持續(xù)時(shí)間很短，也就是說(shuō)，如果你使用了這個(gè)魔法，走到了這個(gè)暫時(shí)有顏色的格子上，你就不能繼續(xù)使用魔法；只有當(dāng)你離開(kāi)這個(gè)位置，

12、走到一個(gè)本來(lái)就有顏色的格子上的時(shí)候，你才能繼續(xù)使用這個(gè)魔法，而當(dāng)你離開(kāi)了這個(gè)位置（施展魔法使得變?yōu)橛蓄伾母褡樱r(shí)，這個(gè)格子恢復(fù)為無(wú)色。 現(xiàn)在你要從棋盤的最左上角，走到棋盤的最右下角，求花費(fèi)的最少金幣是多少？ 【輸入格式】 輸入文件名為chess.in。 數(shù)據(jù)的第一行包含兩個(gè)正整數(shù) m，n，以一個(gè)空格分開(kāi)，分別代表棋盤的大小，棋盤上有顏色的格子的數(shù)量。 接下來(lái)的 n 行，每行三個(gè)正整數(shù) x，y，c，分別表示坐標(biāo)為（x，y）的格子有顏色 c。其中 c=1 代表黃色，c=0 代表紅色。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。棋盤左上角的坐標(biāo)為（1, 1），右下角的坐標(biāo)為（m, m）。 棋盤上其余的格子都是無(wú)

13、色。保證棋盤的左上角，也就是（1，1）一定是有顏色的。 【輸出格式】 輸出文件名為chess.out。 輸出一行，一個(gè)整數(shù)，表示花費(fèi)的金幣的最小值，如果無(wú)法到達(dá)，輸出-1。 【輸入輸出樣例 1】 chess.in chess.out 5 7 1 1 0 1 2 0 2 2 1 3 3 1 3 4 0 4 4 1 5 5 0 8 見(jiàn)選手目錄下的chess/chess1.in和chess/chess1.ans。 【輸入輸出樣例 1 說(shuō)明】 從（1，1）開(kāi)始，走到（1，2）不花費(fèi)金幣從（1，2）向下走到（2，2）花費(fèi) 1 枚金幣從（2，2）施展魔法，將（2，3）變?yōu)辄S色，花費(fèi) 2 枚金幣從（2，2）

14、走到（2，3）不花費(fèi)金幣從（2，3）走到（3，3）不花費(fèi)金幣從（3，3）走到（3，4）花費(fèi) 1 枚金幣從（3，4）走到（4，4）花費(fèi) 1 枚金幣從（4，4）施展魔法，將（4，5）變?yōu)辄S色，花費(fèi) 2 枚金幣，從（4，4）走到（4，5）不花費(fèi)金幣從（4，5）走到（5，5）花費(fèi) 1 枚金幣共花費(fèi) 8 枚金幣。 【輸入輸出樣例 2】 chess.in chess.out 5 5 1 1 0 1 2 0 2 2 1 3 3 1 5 5 0 -1 見(jiàn)選手目錄下的chess/chess2.in和chess/chess2.ans。 【輸入輸出樣例 2 說(shuō)明】 從（1，1）走到（1，2），不花費(fèi)金幣從（1，2）

15、走到（2，2），花費(fèi) 1 金幣施展魔法將（2，3）變?yōu)辄S色，并從（2，2）走到（2，3）花費(fèi) 2 金幣從（2，3）走到（3，3）不花費(fèi)金幣 從（3，3）只能施展魔法到達(dá)（3，2），（2，3），（3，4），（4，3） 而從以上四點(diǎn)均無(wú)法到達(dá)（5，5），故無(wú)法到達(dá)終點(diǎn)，輸出1 【輸入輸出樣例 3】 見(jiàn)選手目錄下的chess/chess3.in和chess/chess3.ans。 【數(shù)據(jù)規(guī)模與約定】 對(duì)于 30%的數(shù)據(jù)，1 m 5， 1 n 10。 對(duì)于 60%的數(shù)據(jù)，1 m 20， 1 n 200。 對(duì)于 100%的數(shù)據(jù)，1 m 100， 1 n 1,000。 4. 跳房子 (jump.cpp/c

16、/pas) 【問(wèn)題描述】 跳房子，也叫跳飛機(jī)，是一種世界性的兒童游戲，也是中國(guó)民間傳統(tǒng)的體育游戲之一。跳房子的游戲規(guī)則如下： 在地面上確定一個(gè)起點(diǎn)，然后在起點(diǎn)右側(cè)畫(huà) n 個(gè)格子，這些格子都在同一條直線上。每個(gè)格子內(nèi)有一個(gè)數(shù)字（整數(shù)），表示到達(dá)這個(gè)格子能得到的分?jǐn)?shù)。玩家第一次從起點(diǎn)開(kāi)始向右跳，跳到起點(diǎn)右側(cè)的一個(gè)格子內(nèi)。第二次再?gòu)漠?dāng)前位置繼續(xù)向右跳，依此類推。規(guī)則規(guī)定：玩家每次都必須跳到當(dāng)前位置右側(cè)的一個(gè)格子內(nèi)。玩家可以在任意時(shí)刻結(jié)束游戲，獲得的分?jǐn)?shù)為曾經(jīng)到達(dá)過(guò)的格子中的數(shù)字之和。 現(xiàn)在小 R 研發(fā)了一款彈跳機(jī)器人來(lái)參加這個(gè)游戲。但是這個(gè)機(jī)器人有一個(gè)非常嚴(yán)重的缺陷，它每次向右彈跳的距離只能為固定的

17、 d。小 R 希望改進(jìn)他的機(jī)器人，如果他花 g 個(gè)金幣改進(jìn)他的機(jī)器人，那么他的機(jī)器人靈活性就能增加 g，但是需要注意的是，每次彈跳的距離至少為 1。具體而言，當(dāng)g < d時(shí)，他的機(jī)器人每次可以選擇向右彈跳的距離為 d-g, d-g+1, d-g+2，d+g-2，d+g-1，d+g；否則（當(dāng)g d時(shí)），他的機(jī)器人每次可以選擇向右彈跳的距離為 1，2，3，d+g-2，d+g-1，d+g。 現(xiàn)在小 R 希望獲得至少 k 分，請(qǐng)問(wèn)他至少要花多少金幣來(lái)改造他的機(jī)器人。 【輸入格式】 輸入文件名為jump.in。 第一行三個(gè)正整數(shù) n，d，k，分別表示格子的數(shù)目，改進(jìn)前機(jī)器人彈跳的固定距離，以及希望

18、至少獲得的分?jǐn)?shù)。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 接下來(lái) n 行，每行兩個(gè)正整數(shù)𝑥𝑖, 𝑠𝑖，分別表示起點(diǎn)到第i個(gè)格子的距離以及第i個(gè)格子的分?jǐn)?shù)。兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。保證𝑥𝑖按遞增順序輸入。 【輸出格式】 輸出文件名為jump.out。 共一行，一個(gè)整數(shù)，表示至少要花多少金幣來(lái)改造他的機(jī)器人。若無(wú)論如何他都無(wú)法獲得至少 k 分，輸出-1。 【輸入輸出樣例 1】 jump.in jump.out 7 4 10 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2 2 見(jiàn)選手目錄下的jump/jump1.in和jump/jump1.ans。 【輸入輸出樣例 1 說(shuō)明】 花費(fèi) 2 個(gè)金幣改進(jìn)后，小 R 的機(jī)器人依次選擇的向右彈跳的距離分別為 2，3，5，3，4， 3，先后到達(dá)的位置分別為 2，5，10，13，17，20，對(duì)應(yīng) 1, 2, 3, 5, 6, 7 這 6 個(gè)格子。這些格子中的數(shù)字之和 15 即為小 R 獲得的分?jǐn)?shù)。 【輸入輸出樣例 2】 jump.in jump.out 7 4 20 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2 -1 見(jiàn)選手目錄下的jump/jump2.in和jump/jump2.an