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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 普及組 （請選手務(wù)必仔細閱讀本頁內(nèi)容） 一題目概況 中文題目名稱 成績 圖書管理員 棋盤 跳房子 英文題目與子目錄名 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 每個測試點時限 1 秒 1 秒 1 秒 2 秒 測試點數(shù)目 10 10 20 10 每個測試

2、點分值 10 10 5 10 附加樣例文件 有 有 有 有 結(jié)果比較方式 全文比較（過濾行末空格及文末回車） 題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運行內(nèi)存上限 256M 256M 256M 256M 二提交源程序文件名 對于 C+語言 score.cpp librarian.cpp chess.cpp jump.cpp 對于 C 語言 score.c librarian.c chess.c jump.c 對于 pascal 語言 score.pas librarian.pas chess.pas jump.pas 三編譯命令（不包含任何優(yōu)化開關(guān)） 對于 C+語言 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 對于 C 語言 gcc -o score score.c -lm gcc -o librarian librarian.c -lm gcc -o chess chess.c -lm gcc -o jump jump.c -lm 對于 pascal 語言 fpc score.pas fpc librarian.pas fpc chess.pas fpc jump.pas 注意事項： 1、 文件名（程序名和輸入輸

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

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

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

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

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

9、所需要的書，則在第 i 行輸出第 i 個讀者所需要的書中圖書編碼最小的那本書的圖書編碼，否則輸出-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 見選手目錄下的librarian /librarian1.in和librarian/librarian1.ans。 【輸入輸出樣例 1 說明】 第一位讀者需要的書有 2123、1123、23，其中 23 是最小的圖書編碼。第二位讀者需要的書有 2123、1123，其中 1123 是最小

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

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

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

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

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

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

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

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

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