1、全國信息學奧林匹克聯賽（NOIP2017）復賽 普及組 CCF全國信息學奧林匹克聯賽（NOIP2017）復賽 普及組 （請選手務必仔細閱讀本頁內容） 一題目概況 中文題目名稱 成績 圖書管理員 棋盤 跳房子 英文題目與子目錄名 score librarian chess jump 可執行文件名 score librarian chess jump 輸入文件名 score.in librarian.in chess.in jump.in 輸出文件名 score.out librarian.out chess.out jump.out 每個測試點時限 1 秒 1 秒 1 秒 2 秒 測試點數目 1

2、0 10 20 10 每個測試點分值 10 10 5 10 附加樣例文件 有 有 有 有 結果比較方式 全文比較（過濾行末空格及文末回車） 題目類型 傳統 傳統 傳統 傳統 運行內存上限 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 三編譯命令（不包含任何優化開關） 對于 C+語言 g

3、+ -o score score.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 注意事項：

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

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

6、0 80 90 見選手目錄下的 score/score1.in 和 score/score1.ans。 【輸入輸出樣例 1 說明】 牛牛的作業成績是 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 說明】 牛牛的作業成績是 60 分，小測成績是 90 分，期末考試成績是 80 分，

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

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

9、個整數，如果存在第 i 個讀者所需要的書，則在第 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、1

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

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

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

13、m）。 棋盤上其余的格子都是無色。保證棋盤的左上角，也就是（1，1）一定是有顏色的。 【輸出格式】 輸出文件名為chess.out。 輸出一行，一個整數，表示花費的金幣的最小值，如果無法到達，輸出-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）變為黃色

14、，花費 2 枚金幣從（2，2）走到（2，3）不花費金幣從（2，3）走到（3，3）不花費金幣從（3，3）走到（3，4）花費 1 枚金幣從（3，4）走到（4，4）花費 1 枚金幣從（4，4）施展魔法，將（4，5）變為黃色，花費 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

15、，2），不花費金幣從（1，2）走到（2，2），花費 1 金幣施展魔法將（2，3）變為黃色，并從（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。 【數據規模與約定】 對于 30%的數據，1 m 5， 1 n 10。 對于 60%的數據，1 m 20， 1 n 200。 對于 100%的數據，1 m 100， 1 n 1,000。 4.

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

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

18、機器人彈跳的固定距離，以及希望至少獲得的分數。相鄰兩個數之間用一個空格隔開。 接下來 n 行，每行兩個正整數𝑥𝑖, 𝑠𝑖，分別表示起點到第i個格子的距離以及第i個格子的分數。兩個數之間用一個空格隔開。保證𝑥𝑖按遞增順序輸入。 【輸出格式】 輸出文件名為jump.out。 共一行，一個整數，表示至少要花多少金幣來改造他的機器人。若無論如何他都無法獲得至少 k 分，輸出-1。 【輸入輸出樣例 1】 jump.in jump.out 7 4 10 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2