CCF全國信息學奧林匹克聯賽（NOIP2017）復賽普與組（請選手務必仔細閱讀本頁內容）一.題目概況中文題目名稱成績圖書管理員棋盤跳房子英文題目與子目錄名scorelibrarianchessjump可執行文件名scorelibrarianchessjump輸入文件名score.inlibrarian.inchess.injump.in輸出文件名score.outlibrarian.outchess.outjump.out每個測試點時限1秒1秒1秒2秒測試點數目10102010每個測試點分值1010510附加樣例文件有有有有結果比較方式全文比較（過濾行末空格與文末回車）題目類型傳統傳統傳統傳統運行內存上限256M256M256M256M.提交源程序文件名對于C++語言score.cpplibrarian.cppchess.cppjump.cpp對于C語言score.clibrarian.cchess.cjump.c對于pascal語言score.paslibrarian.paschess.pasjump.pas三.編譯命令（不包含任何優化開關）對于C++語言g++-oscorescore.cpp-lmg++-olibrarianlibrarian.cpp-lmg++-ochesschess.cpp-lmg++-ojumpjump.cpp-lm對于C語言gcc-oscorescore.c-lmgcc-olibrarianlibrarian.c-lmgcc-ochesschess.c-lmgcc-ojumpjump.c-lm對于pascal語言fpcscore.pasfpclibrarian.pasfpcchess.pasfpcjump.pas注意事項：1、 文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、 C/C++中函數main（）的返回值類型必須是int，程序正常結束時的返回值必須是0。3、 全國統一評測時采用的機器配置為：CPUAMDAthlon(tm)IIx2240processor,2.8GHz,內存4G,上述時限以此配置為準。4、 只提供Linux格式附加樣例文件。5、 提交的程序代碼文件的放置位置請參照各省的具體要求。6、 特別提醒：評測在當前最新公布的NOILinux下進行，各語言的編譯器版本以其為準。1.成績(score.cpp/c/pas)【問題描述】牛牛最近學習了C++入門課程，這門課程的總成績計算方法是：總成績=作業成績x20%+小測成績X30%+期末考試成績X50%牛牛想知道，這門課程自己最終能得到多少分。【輸入格式】輸入文件名為score.in。輸入文件只有1行，包含三個非負整數A、B、C，分別表示牛牛的作業成績、小測成績和期末考試成績。相鄰兩個數之間用一個空格隔開，三項成績滿分都是100分。【輸出格式】輸出文件名為score.out。輸出文件只有1行，包含一個整數，即牛牛這門課程的總成績，滿分也是100分。【輸入輸出樣例1】score.inscore.out1001008090見選手目錄下的score/score1.in和score/score1.ans。【輸入輸出樣例1說明】牛牛的作業成績是100分，小測成績是100分，期末考試成績是80分，總成績是100x20%+100x30%+80x50%=20+30+40=90。【輸入輸出樣例2】score.inscore.out60908079見選手目錄下的score/score2.in和score/score2.ans。【輸入輸出樣例2說明】牛牛的作業成績是60分，小測成績是90分，期末考試成績是80分，總成績是60x20%+90x30%+80x50%=12+27+40=79。【數據說明】對于30%的數據，A=B=0。對于另外30%的數據，A=B=100。對于100%的數據，0￡A、B、C<100且A、B、C都是10的整數倍。2.圖書管理員(librarian.cpp/c/pas)【問題描述】圖書館中每本書都有一個圖書編碼，可以用于快速檢索圖書，這個圖書編碼是一個正整數。每位借書的讀者手中有一個需求碼，這個需求碼也是一個正整數。如果一本書的圖書編碼恰好以讀者的需求碼結尾，那么這本書就是這位讀者所需要的。小D剛剛當上圖書館的管理員，她知道圖書館里所有書的圖書編碼，她請你幫她寫一個程序，對于每一位讀者，求出他所需要的書中圖書編碼最小的那本書，如果沒有他需要的書，請輸出1。【輸入格式】輸入文件名為librarian.in。輸入文件的第一行，包含兩個正整數n和q，以一個空格分開，分別代表圖書館里書的數量和讀者的數量。接下來的n行，每行包含一個正整數，代表圖書館里某本書的圖書編碼。接下來的q行，每行包含兩個正整數，以一個空格分開，第一個正整數代表圖書館里讀者的需求碼的長度，第二個正整數代表讀者的需求碼。【輸出格式】輸出文件名為librarian.out。輸出文件有q行，每行包含一個整數，如果存在第i個讀者所需要的書，則在第i行輸出第i個讀者所需要的書中圖書編碼最小的那本書的圖書編碼，否則輸出1。【輸入輸出樣例1】librarian.inlibrarian.out23231123-1-11123-1-1-11123232424231231241212見選手目錄下的librarian/librarian1.in和librarian/librarian1.ans。【輸入輸出樣例1說明】第一位讀者需要的書有2123、1123、23，其中23是最小的圖書編碼。第二位讀者需要的書有2123、1123,其中1123是最小的圖書編碼。對于第三位，第四位和第五位讀者，沒有書的圖書編碼以他們的需求碼結尾，即沒有他們需要的書，輸出-1。【輸入輸出樣例2】見選手目錄下的librarian/librarian2.in和librarian/librarian2.ans。【數據規模與約定】對于20%的數據，1WnW2。另有20%的數據，q=1。另有20%的數據，所有讀者的需求碼的長度均為1。另有20%的數據，所有的圖書編碼按從小到大的順序給出。對于100%的數據，1WnW1,000，1WqW1,000，所有的圖書編碼和需求碼均不超過10,000,000。3.棋盤(chess.cpp/c/pas)【問題描述】有一個mxm的棋盤，棋盤上每一個格子可能是紅色、黃色或沒有任何顏色的。你現在要從棋盤的最左上角走到棋盤的最右下角。任何一個時刻，你所站在的位置必須是有顏色的（不能是無色的），你只能向上、下、左、右四個方向前進。當你從一個格子走向另一個格子時，如果兩個格子的顏色相同，那你不需要花費金幣；如果不同，則你需要花費1個金幣。另外，你可以花費2個金幣施展魔法讓下一個無色格子暫時變為你指定的顏色。但這個魔法不能連續使用，而且這個魔法的持續時間很短，也就是說，如果你使用了這個魔法，走到了這個暫時有顏色的格子上，你就不能繼續使用魔法；只有當你離開這個位置，走到一個本來就有顏色的格子上的時候，你才能繼續使用這個魔法，而當你離開了這個位置（施展魔法使得變為有顏色的格子）時，這個格子恢復為無色。現在你要從棋盤的最左上角，走到棋盤的最右下角，求花費的最少金幣是多少？【輸入格式】輸入文件名為chess.in。數據的第一行包含兩個正整數m，n，以一個空格分開，分別代表棋盤的大小，棋盤上有顏色的格子的數量。接下來的n行，每行三個正整數x，y，c，分別表示坐標為（x，y）的格子有顏色c。其中c=1代表黃色，c=0代表紅色。相鄰兩個數之間用一個空格隔開。棋盤左上角的坐標為（1,1），右下角的坐標為（m,m）。棋盤上其余的格子都是無色。保證棋盤的左上角，也就是（1，1）一定是有顏色的。【輸出格式】輸出文件名為chess.out。輸出一行，一個整數，表示花費的金幣的最小值，如果無法到達，輸出-1。【輸入輸出樣例1】chess.inchess.out578110120221331340441550見選手目錄下的chess/chessl.in和chess/chessl.ans。【輸入輸出樣例1說明】

從（1,1）開始，走到（1,2）不花費金幣從（1,2）向下走到（2,2）花費1枚金幣從（2,2）施展魔法，將（2,3）變為黃色，花費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.inchess.out55-1110120221331550見選手目錄下的chess/chess2.in和chess/chess2.ans。金幣從（2,3）走到（3,3）不花費金幣從（3，3）只能施展魔法到達（3，2）,（2,3）,（3,4）,（4,3）而從以上四點均無法到達（5,5）,故無法到達終點，輸出一1見選手目錄下的chess/chess3.in和chess/chess3.ans。【數據規模與約定】對于30%的數據，1WmW5,1WnW10。對于60%的數據，1WmW20,1WnW200。對于100%的數據，1WmW100,1WnW1,000。4.跳房子（jump.cpp/c/pas）【問題描述】跳房子，也叫跳飛機，是一種世界性的兒童游戲，也是中國民間傳統的體育游戲之一。跳房子的游戲規則如下：在地面上確定一個起點，然后在起點右側畫n個格子，這些格子都在同一條直線上。每個格子內有一個數字（整數），表示到達這個格子能得到的分數。玩家第一次從起點開始向右跳，跳到起點右側的一個格子內。第二次再從當前位置繼續向右跳，依此類推。規則規定：玩家每次都必須跳到當前位置右側的一個格子內。玩家可以在任意時刻結束游戲，獲得的分數為曾經到達過的格子中的數字之和。現在小R研發了一款彈跳機器人來參加這個游戲。但是這個機器人有一個非常嚴重的缺陷，它每次向右彈跳的距離只能為固定的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+go現在小R希望獲得至少k分，請問他至少要花多少金幣來改造他的機器人。【輸入格式】輸入文件名為jump.in。第一行三個正整數n，d，k，分別表示格子的數目，改進前機器人彈跳的固定距離，以與希望至少獲得的分數。相鄰兩個數之間用一個空格隔開。接下來n行，每行兩個正整數xes，，分別表示起點到第i個格子的距離以與第i個格子的分數。兩個數之間用一個空格隔開。。保證氣按遞增順序輸入。【輸出格式】輸出文件名為jump.out。共一行，一個整數，表示至少要花多少金幣來改造他的機器人。若無論如何他都無法獲得至少k分，輸出1o

jump.injump.out7410265-33-31311762022見選手目錄下的jump/jumpl.in和jump/jumpl.ans。【輸入輸出樣例1說明】花費2個金幣改進后，小R的機器人依次選擇的向右彈跳的距離分別為2,3,5,3,4,3,先后到達的位置分別為2,5,10,13,17,20,對應1,2,3,5,6,7這6個格子。這些格子中的數字之和15即為小R獲得的分數。【輸入輸出樣例2】見選手目錄下的