NOIP2017復賽普及組試題

1、CCF全國信息學奧林匹克聯(lián)賽NOIP2017復賽 普及組 請選手務必仔細閱讀本頁內容 一題目概況 中文題目名稱 成績 圖書管理員 棋盤 跳房子 英文題目與子目錄名 score librarian chess jump 可執(zhí)行文件名 score librarian chess jump 輸入文件名 score.in librarian.in chess.in jump.in 輸出文件名 每個測試點時限 1 秒 1 秒 1 秒 2 秒 測試點數(shù)目 10 10 20 10 每個測試點分值 10 10 5 10 附加樣例文件 有 有 有 有 結果比較方式 全文比較過濾行末空格及文末回車 題目類型 傳統(tǒng)

2、 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運行內存上限 256M 256M 256M 256M 二提交源程序文件名 對于 C+語言 score.cpp librarian.cpp chess.cpp jump.cpp 對于 C 語言 對于 pascal 語言 三編譯命令不包含任何優(yōu)化開關 對于 C+語言 g+ -o score -lm g+ -o librarian -lm g+ -o chess -lm g+ -o jump -lm 對于 C 語言 gcc -o score -lm gcc -o librarian -lm gcc -o chess -lm gcc -o jump -lm 對于 pascal 語言

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

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

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

6、【數(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ù)。如果一本書的圖書編碼恰好以讀者的需求碼結尾，那么這本書就是這位讀者所需要的。 小 D 剛剛當上圖書館的管理員，她知道圖書館里所有書的圖書編碼，她請你幫她寫一個程序，對于每一位讀者，求出他所需要的書中圖書編

7、碼最小的那本書，如果沒有他需要的書，請輸出-1。 【輸入格式】 輸入文件名為。 輸入文件的第一行，包含兩個正整數(shù) n 和 q，以一個空格分開，分別代表圖書館里書的數(shù)量和讀者的數(shù)量。 接下來的 n 行，每行包含一個正整數(shù)，代表圖書館里某本書的圖書編碼。 接下來的 q 行，每行包含兩個正整數(shù)，以一個空格分開，第一個正整數(shù)代表圖書館里讀者的需求碼的長度，第二個正整數(shù)代表讀者的需求碼。 【輸出格式】 輸出文件名為。 輸出文件有 q 行，每行包含一個整數(shù)，如果存在第 i 個讀者所需要的書，則在第 i 行輸出第 i 個讀者所需要的書中圖書編碼最小的那本書的圖書編碼，否則輸出-1。 【輸入輸出樣例 1】 l

8、ibrarian.in 5 5 2123 1123 23 24 24 2 23 3 123 3 124 2 12 2 12 23 1123 -1 -1 -1 見選手目錄下的和。 【輸入輸出樣例 1 說明】 第一位讀者需要的書有 2123、1123、23，其中 23 是最小的圖書編碼。第二位讀者需要的書有 2123、1123，其中 1123 是最小的圖書編碼。對于第三位，第四位和第五位讀者，沒有書的圖書編碼以他們的需求碼結尾，即沒有他們需要的書，輸出-1。 【輸入輸出樣例 2】 見選手目錄下的和。 【數(shù)據(jù)規(guī)模與約定】 對于 20%的數(shù)據(jù)，1 n 2。 另有 20%的數(shù)據(jù)，q = 1。 另有 20

9、%的數(shù)據(jù)，所有讀者的需求碼的長度均為 1。 另有 20%的數(shù)據(jù)，所有的圖書編碼按從小到大的順序給出。 對于 100%的數(shù)據(jù)，1 n 1,000，1 q 1,000，所有的圖書編碼和需求碼均不超過 10,000,000。 3. 棋盤 (chess.cpp/c/pas) 【問題描述】 有一個m × m的棋盤，棋盤上每一個格子可能是紅色、黃色或沒有任何顏色的。你現(xiàn)在要從棋盤的最左上角走到棋盤的最右下角。 任何一個時刻，你所站在的位置必須是有顏色的不能是無色的，你只能向上、下、左、右四個方向前進。當你從一個格子走向另一個格子時，如果兩個格子的顏色相同，那你不需要花費金幣；如果不同，則你需要花

10、費 1 個金幣。 另外，你可以花費 2 個金幣施展魔法讓下一個無色格子暫時變?yōu)槟阒付ǖ念伾?。但這個魔法不能連續(xù)使用，而且這個魔法的持續(xù)時間很短，也就是說，如果你使用了這個魔法，走到了這個暫時有顏色的格子上，你就不能繼續(xù)使用魔法；只有當你離開這個位置，走到一個本來就有顏色的格子上的時候，你才能繼續(xù)使用這個魔法，而當你離開了這個位置施展魔法使得變?yōu)橛蓄伾母褡訒r，這個格子恢復為無色。 現(xiàn)在你要從棋盤的最左上角，走到棋盤的最右下角，求花費的最少金幣是多少？ 【輸入格式】 輸入文件名為。 數(shù)據(jù)的第一行包含兩個正整數(shù) m，n，以一個空格分開，分別代表棋盤的大小，棋盤上有顏色的格子的數(shù)量。 接下來的 n

11、行，每行三個正整數(shù) x，y，c，分別表示坐標為x，y的格子有顏色 c。其中 c=1 代表黃色，c=0 代表紅色。相鄰兩個數(shù)之間用一個空格隔開。棋盤左上角的坐標為1, 1，右下角的坐標為m, m。 棋盤上其余的格子都是無色。保證棋盤的左上角，也就是1，1一定是有顏色的。 【輸出格式】 輸出文件名為。 輸出一行，一個整數(shù)，表示花費的金幣的最小值，如果無法到達，輸出-1。 【輸入輸出樣例 1】 chess.in 5 7 1 1 0 1 2 0 2 2 1 3 3 1 3 4 0 4 4 1 5 5 0 8 見選手目錄下的和。 【輸入輸出樣例 1 說明】 從1，1開始，走到1，2不花費金幣從1，2向下

12、走到2，2花費 1 枚金幣從2，2施展魔法，將2，3變?yōu)辄S色，花費 2 枚金幣從2，2走到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 5 5 1 1 0 1 2 0 2 2 1 3 3 1 5 5 0 -1 見選手目錄下的和。 【輸入輸出樣例 2 說明】 從1，1走到1，2，不花費金幣從1，2走到2，2，花費 1 金幣施展魔法將2，3變?yōu)辄S色，并從2，

13、2走到2，3花費 2 金幣從2，3走到3，3不花費金幣 從3，3只能施展魔法到達3，2，2，3，3，4，4，3 而從以上四點均無法到達5，5，故無法到達終點，輸出1 【輸入輸出樣例 3】 見選手目錄下的和。 【數(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/pas) 【問題描述】 跳房子，也叫跳飛機，是一種世界性的兒童游戲，也是中國民間傳統(tǒng)的體育游戲之一。跳房子的游戲規(guī)則如下： 在地面上確定一個起點，然后在起點右側畫 n

14、個格子，這些格子都在同一條直線上。每個格子內有一個數(shù)字整數(shù)，表示到達這個格子能得到的分數(shù)。玩家第一次從起點開始向右跳，跳到起點右側的一個格子內。第二次再從當前位置繼續(xù)向右跳，依此類推。規(guī)則規(guī)定：玩家每次都必須跳到當前位置右側的一個格子內。玩家可以在任意時刻結束游戲，獲得的分數(shù)為曾經(jīng)到達過的格子中的數(shù)字之和。 現(xiàn)在小 R 研發(fā)了一款彈跳機器人來參加這個游戲。但是這個機器人有一個非常嚴重的缺陷，它每次向右彈跳的距離只能為固定的 d。小 R 希望改良他的機器人，如果他花 g 個金幣改良他的機器人，那么他的機器人靈活性就能增加 g，但是需要注意的是，每次彈跳的距離至少為 1。具體而言，當g <

15、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。 現(xiàn)在小 R 希望獲得至少 k 分，請問他至少要花多少金幣來改造他的機器人。 【輸入格式】 輸入文件名為。 第一行三個正整數(shù) n，d，k，分別表示格子的數(shù)目，改良前機器人彈跳的固定距離，以及希望至少獲得的分數(shù)。相鄰兩個數(shù)之間用一個空格隔開。 接下來 n 行，每行兩個正整數(shù)𝑥𝑖, 𝑠𝑖，分別表示起點到第i個格子的距離以及第

16、i個格子的分數(shù)。兩個數(shù)之間用一個空格隔開。保證𝑥𝑖按遞增順序輸入。 【輸出格式】 輸出文件名為。 共一行，一個整數(shù)，表示至少要花多少金幣來改造他的機器人。假設無論如何他都無法獲得至少 k 分，輸出-1。 【輸入輸出樣例 1】 jump.in 7 4 10 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2 2 見選手目錄下的和。 【輸入輸出樣例 1 說明】 花費 2 個金幣改良后，小 R 的機器人依次選擇的向右彈跳的距離分別為 2，3，5，3，4， 3，先后到達的位置分別為 2，5，10，13，17，20，對應 1, 2, 3, 5, 6, 7 這 6 個格子。這些格子中的數(shù)字之和 15 即為小 R 獲得的分數(shù)。 【輸入輸出樣例 2】 jump.in 7 4 20 2 6 5 -3 10 3 11 -3 13 1 17 6 20 2 -1 見選手目錄下的和。 【輸入輸出樣例 2 說明】 由于樣