NOIP2018年復(fù)賽普和組試題.doc

WORD資料.可編輯 CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 普及組 （請(qǐng)選手務(wù)必仔細(xì)閱讀本頁內(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 每個(gè)測(cè)試點(diǎn)時(shí)限 1 秒 1 秒 1 秒 2 秒 測(cè)試點(diǎn)數(shù)目 10 10 20 10 每個(gè)測(cè)試點(diǎn)分值 10 10 5 10 附加樣例文件 有 有 有 有 結(jié)果比較方式 全文比較（過濾行末空格及文末回車） 題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 運(yùn)行內(nèi)存上限 256M 256M 256M 256M 二提交源程序文件名 對(duì)于 C+語言 score.cpp librarian.cpp chess.cpp jump.cpp 對(duì)于 C 語言 score.c librarian.c chess.c jump.c 對(duì)于 pascal 語言 score.pas librarian.pas chess.pas jump.pas 三編譯命令（不包含任何優(yōu)化開關(guān)） 對(duì)于 C+語言 g+ -o score score.cpp -lm g+ -o librarian librarian.cpp -lm g+ -o chess chess.cpp -lm g+ -o jump jump.cpp -lm 對(duì)于 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 對(duì)于 pascal 語言 fpc score.pas fpc librarian.pas fpc chess.pas fpc jump.pas 注意事項(xiàng)： 1、 文件名（程序名和輸入輸出文件名）必須使用英文小寫。 2、 C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時(shí)的返回值必須是 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、 只提供 Linux 格式附加樣例文件。 5、 提交的程序代碼文件的放置位置請(qǐng)參照各省的具體要求。 6、 特別提醒：評(píng)測(cè)在當(dāng)前最新公布的 NOI Linux 下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。 1. 成績 (score.cpp/c/pas) 【問題描述】 牛牛最近學(xué)習(xí)了 C+入門課程，這門課程的總成績計(jì)算方法是： 總成績=作業(yè)成績20%+小測(cè)成績30%+期末考試成績50% 牛牛想知道，這門課程自己最終能得到多少分。 【輸入格式】 輸入文件名為 score.in。 輸入文件只有 1 行，包含三個(gè)非負(fù)整數(shù)A、B、C，分別表示牛牛的作業(yè)成績、小測(cè)成績和期末考試成績。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開，三項(xiàng)成績滿分都是 100 分。 【輸出格式】 輸出文件名為 score.out。 輸出文件只有 1 行，包含一個(gè)整數(shù)，即牛牛這門課程的總成績，滿分也是 100 分。 【輸入輸出樣例 1】 score.in score.out 100 100 80 90 見選手目錄下的 score/score1.in 和 score/score1.ans。 【輸入輸出樣例 1 說明】 牛牛的作業(yè)成績是 100 分，小測(cè)成績是 100 分，期末考試成績是 80 分，總成績是 10020%+10030%+8050%=20+30+40=90。 【輸入輸出樣例 2】 score.in score.out 60 90 80 79 見選手目錄下的 score/score2.in 和 score/score2.ans。 【輸入輸出樣例 2 說明】 牛牛的作業(yè)成績是 60 分，小測(cè)成績是 90 分，期末考試成績是 80 分，總成績是 6020%+9030%+8050%=12+27+40=79。 【數(shù)據(jù)說明】 對(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. 圖書管理員 (librarian.cpp/c/pas) 【問題描述】 圖書館中每本書都有一個(gè)圖書編碼，可以用于快速檢索圖書，這個(gè)圖書編碼是一個(gè)正整數(shù)。 每位借書的讀者手中有一個(gè)需求碼，這個(gè)需求碼也是一個(gè)正整數(shù)。如果一本書的圖書編碼恰好以讀者的需求碼結(jié)尾，那么這本書就是這位讀者所需要的。 小 D 剛剛當(dāng)上圖書館的管理員，她知道圖書館里所有書的圖書編碼，她請(qǐng)你幫她寫一個(gè)程序，對(duì)于每一位讀者，求出他所需要的書中圖書編碼最小的那本書，如果沒有他需要的書，請(qǐng)輸出-1。 【輸入格式】 輸入文件名為librarian.in。 輸入文件的第一行，包含兩個(gè)正整數(shù) n 和 q，以一個(gè)空格分開，分別代表圖書館里書的數(shù)量和讀者的數(shù)量。 接下來的 n 行，每行包含一個(gè)正整數(shù)，代表圖書館里某本書的圖書編碼。 接下來的 q 行，每行包含兩個(gè)正整數(shù)，以一個(gè)空格分開，第一個(gè)正整數(shù)代表圖書館里讀者的需求碼的長度，第二個(gè)正整數(shù)代表讀者的需求碼。 【輸出格式】 輸出文件名為librarian.out。 輸出文件有 q 行，每行包含一個(gè)整數(shù)，如果存在第 i 個(gè)讀者所需要的書，則在第 i 行輸出第 i 個(gè)讀者所需要的書中圖書編碼最小的那本書的圖書編碼，否則輸出-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 是最小的圖書編碼。對(duì)于第三位，第四位和第五位讀者，沒有書的圖書編碼以他們的需求碼結(jié)尾，即沒有他們需要的書，輸出-1。 【輸入輸出樣例 2】 見選手目錄下的librarian/librarian2.in和librarian/librarian2.ans。 【數(shù)據(jù)規(guī)模與約定】 對(duì)于 20%的數(shù)據(jù)，1 n 2。 另有 20%的數(shù)據(jù)，q = 1。 另有 20%的數(shù)據(jù)，所有讀者的需求碼的長度均為 1。 另有 20%的數(shù)據(jù)，所有的圖書編碼按從小到大的順序給出。 對(duì)于 100%的數(shù)據(jù)，1 n 1,000，1 q 1,000，所有的圖書編碼和需求碼均不超過 10,000,000。 3. 棋盤 (chess.cpp/c/pas) 【問題描述】 有一個(gè)m m的棋盤，棋盤上每一個(gè)格子可能是紅色、黃色或沒有任何顏色的。你現(xiàn)在要從棋盤的最左上角走到棋盤的最右下角。 任何一個(gè)時(shí)刻，你所站在的位置必須是有顏色的（不能是無色的），你只能向上、下、左、右四個(gè)方向前進(jìn)。當(dāng)你從一個(gè)格子走向另一個(gè)格子時(shí)，如果兩個(gè)格子的顏色相同，那你不需要花費(fèi)金幣；如果不同，則你需要花費(fèi) 1 個(gè)金幣。 另外，你可以花費(fèi) 2 個(gè)金幣施展魔法讓下一個(gè)無色格子暫時(shí)變?yōu)槟阒付ǖ念伾?。但這個(gè)魔法不能連續(xù)使用，而且這個(gè)魔法的持續(xù)時(shí)間很短，也就是說，如果你使用了這個(gè)魔法，走到了這個(gè)暫時(shí)有顏色的格子上，你就不能繼續(xù)使用魔法；只有當(dāng)你離開這個(gè)位置，走到一個(gè)本來就有顏色的格子上的時(shí)候，你才能繼續(xù)使用這個(gè)魔法，而當(dāng)你離開了這個(gè)位置（施展魔法使得變?yōu)橛蓄伾母褡樱r(shí)，這個(gè)格子恢復(fù)為無色。 現(xiàn)在你要從棋盤的最左上角，走到棋盤的最右下角，求花費(fèi)的最少金幣是多少？ 【輸入格式】 輸入文件名為chess.in。 數(shù)據(jù)的第一行包含兩個(gè)正整數(shù) m，n，以一個(gè)空格分開，分別代表棋盤的大小，棋盤上有顏色的格子的數(shù)量。 接下來的 n 行，每行三個(gè)正整數(shù) x，y，c，分別表示坐標(biāo)為（x，y）的格子有顏色 c。其中 c=1 代表黃色，c=0 代表紅色。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開。棋盤左上角的坐標(biāo)為（1, 1），右下角的坐標(biāo)為（m, m）。 棋盤上其余的格子都是無色。保證棋盤的左上角，也就是（1，1）一定是有顏色的。 【輸出格式】 輸出文件名為chess.out。 輸出一行，一個(gè)整數(shù)，表示花費(fèi)的金幣的最小值，如果無法到達(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 見選手目錄下的chess/chess1.in和chess/chess1.ans。 【輸入輸出樣例 1 說明】 從（1，1）開始，走到（1，2）不花費(fèi)金幣從（1，2）向下走到（2，2）花費(fèi) 1 枚金幣從（2，2）施展魔法，將（2，3）變?yōu)辄S色，花費(fèi) 2 枚金幣從（2，2）走到（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 見選手目錄下的chess/chess2.in和chess/chess2.ans。 【輸入輸出樣例 2 說明】 從（1，1）走到（1，2），不花費(fèi)金幣從（1，2）走到（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)均無法到達(dá)（5，5），故無法到達(dá)終點(diǎn)，輸出1 【輸入輸出樣例 3】 見選手目錄下的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/pas) 【問題描述】 跳房子，也叫跳飛機(jī)，是一種世界性的兒童游戲，也是中國民間傳統(tǒng)的體育游戲之一。跳房子的游戲規(guī)則如下： 在地面上確定一個(gè)起點(diǎn)，然后在起點(diǎn)右側(cè)畫 n 個(gè)格子，這些格子都在同一條直線上。每個(gè)格子內(nèi)有一個(gè)數(shù)字（整數(shù)），表示到達(dá)這個(gè)格子能得到的分?jǐn)?shù)。玩家第一次從起點(diǎn)開始向右跳，跳到起點(diǎn)右側(cè)的一個(gè)格子內(nèi)。第二次再從當(dāng)前位置繼續(xù)向右跳，依此類推。規(guī)則規(guī)定：玩家每次都必須跳到當(dāng)前位置右側(cè)的一個(gè)格子內(nèi)。玩家可以在任意時(shí)刻結(jié)束游戲，獲得的分?jǐn)?shù)為曾經(jīng)到達(dá)過的格子中的數(shù)字之和。 現(xiàn)在小 R 研發(fā)了一款彈跳機(jī)器人來參加這個(gè)游戲。但是這個(gè)機(jī)器人有一個(gè)非常嚴(yán)重的缺陷，它每次向右彈跳的距離只能為固定的 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)問他至少要花多少金幣來改造他的機(jī)器人。 【輸入格式】 輸入文件名為jump.in。 第一行三個(gè)正整數(shù) n，d，k，分別表示格子的數(shù)目，改進(jìn)前機(jī)器人彈跳的固定距離，以及希望至少獲得的分?jǐn)?shù)。相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開。 接下來 n 行，每行兩個(gè)正整數(shù), ，分別表示起點(diǎn)到第i個(gè)格子的距離以及第i個(gè)格子的分?jǐn)?shù)。兩個(gè)數(shù)之間用一個(gè)空格隔開。保證按遞增順序輸入。 【輸出格式】 輸出文件名為jump.out。 共一行，一個(gè)整數(shù)，表示至少要花多少金幣來改造他的機(jī)器人。若無論如何他都無法獲得至少 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 說明】 花費(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 見選手目錄下的jump/jump