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

全國信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 普及組全國信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽 普及組第頁CCF全國信息學(xué)奧林匹克聯(lián)賽（NOIP2017）復(fù)賽普及組（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）一．題目概況中文題目名稱成績圖書管理員棋盤跳房子英文題目與子目錄名scorelibrarianchessjump可執(zhí)行文件名scorelibrarianchessjump輸入文件名score.inlibrarian.inchess.injump.in輸出文件名score.outlibrarian.outchess.outjump.out每個測試點(diǎn)時限1秒1秒1秒2秒測試點(diǎn)數(shù)目10102010每個測試點(diǎn)分值1010510附加樣例文件有有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限256M256M256M256M二．提交源程序文件名對于C++語言score.cpplibrarian.cppchess.cppjump.cpp對于C語言score.clibrarian.cchess.cjump.c對于pascal語言score.paslibrarian.paschess.pasjump.pas三．編譯命令（不包含任何優(yōu)化開關(guān)）對于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注意事項：文件名（程序名和輸入輸出文件名）必須使用英文小寫。C/C++中函數(shù)main()的返回值類型必須是int，程序正常結(jié)束時的返回值必須是0。全國統(tǒng)一評測時采用的機(jī)器配置為：CPUAMDAthlon(tm)IIx2240processor，2.8GHz，內(nèi)存4G，上述時限以此配置為準(zhǔn)。只提供Linux格式附加樣例文件。提交的程序代碼文件的放置位置請參照各省的具體要求。特別提醒：評測在當(dāng)前最新公布的NOILinux下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。1.成績(score.cpp/c/pas)【問題描述】牛牛最近學(xué)習(xí)了C++入門課程，這門課程的總成績計算方法是：總成績=作業(yè)成績×20%+小測成績×30%+期末考試成績×50%牛牛想知道，這門課程自己最終能得到多少分?！据斎敫袷健枯斎胛募麨閟core.in。輸入文件只有1行，包含三個非負(fù)整數(shù)A、B、C，分別表示牛牛的作業(yè)成績、小測成績和期末考試成績。相鄰兩個數(shù)之間用一個空格隔開，三項成績滿分都是100分?！据敵龈袷健枯敵鑫募麨閟core.out。輸出文件只有1行，包含一個整數(shù)，即牛牛這門課程的總成績，滿分也是100分。【輸入輸出樣例1】score.inscore.out1001008090見選手目錄下的score/score1.in和score/score1.ans。【輸入輸出樣例1說明】牛牛的作業(yè)成績是100分，小測成績是100分，期末考試成績是80分，總成績是100×20%+100×30%+80×50%=20+30+40=90?！据斎胼敵鰳永?】score.inscore.out60908079見選手目錄下的score/score2.in和score/score2.ans?！据斎胼敵鰳永?說明】牛牛的作業(yè)成績是60分，小測成績是90分，期末考試成績是80分，總成績是60×20%+90×30%+80×50%=12+27+40=79。3.棋盤(chess.cpp/c/pas)【問題描述】有一個m×m的棋盤，棋盤上每一個格子可能是紅色、黃色或沒有任何顏色的。你現(xiàn)在要從棋盤的最左上角走到棋盤的最右下角。任何一個時刻，你所站在的位置必須是有顏色的（不能是無色的），你只能向上、下、左、右四個方向前進(jìn)。當(dāng)你從一個格子走向另一個格子時，如果兩個格子的顏色相同，那你不需要花費(fèi)金幣；如果不同，則你需要花費(fèi)1個金幣。另外，你可以花費(fèi)2個金幣施展魔法讓下一個無色格子暫時變?yōu)槟阒付ǖ念伾?。但這個魔法不能連續(xù)使用，而且這個魔法的持續(xù)時間很短，也就是說，如果你使用了這個魔法，走到了這個暫時有顏色的格子上，你就不能繼續(xù)使用魔法；只有當(dāng)你離開這個位置，走到一個本來就有顏色的格子上的時候，你才能繼續(xù)使用這個魔法，而當(dāng)你離開了這個位置（施展魔法使得變?yōu)橛蓄伾母褡樱r，這個格子恢復(fù)為無色?，F(xiàn)在你要從棋盤的最左上角，走到棋盤的最右下角，求花費(fèi)的最少金幣是多少？【輸入格式】輸入文件名為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）。棋盤上其余的格子都是無色。保證棋盤的左上角，也就是（1，1）一定是有顏色的?！据敵龈袷健枯敵鑫募麨閏hess.out。輸出一行，一個整數(shù)，表示花費(fèi)的金幣的最小值，如果無法到達(dá)，輸出-1?！据斎胼敵鰳永?】chess.inchess.out571102021314041508見選手目錄下的chess/chess1.in和chess/chess1.ans?！据斎胼敵鰳永?說明】 從（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枚金幣?！据斎胼敵鰳永?】chess.inchess.out55110202131550-1見選手目錄下的chess/chess2.in和chess/chess2.ans?！据斎胼敵鰳永?說明】從（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ī)模與約定】對于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)【問題描述】跳房子，也叫跳飛機(jī)，是一種世界性的兒童游戲，也是中國民間傳統(tǒng)的體育游戲之一。跳房子的游戲規(guī)則如下：在地面上確定一個起點(diǎn)，然后在起點(diǎn)右側(cè)畫n個格子，這些格子都在同一條直線上。每個格子內(nèi)有一個數(shù)字（整數(shù)），表示到達(dá)這個格子能得到的分?jǐn)?shù)。玩家第一次從起點(diǎn)開始向右跳，跳到起點(diǎn)右側(cè)的一個格子內(nèi)。第二次再從當(dāng)前位置繼續(xù)向右跳，依此類推。規(guī)則規(guī)定：玩家每次都必須跳到當(dāng)前位置右側(cè)的一個格子內(nèi)。玩家可以在任意時刻結(jié)束游戲，獲得的分?jǐn)?shù)為曾經(jīng)到達(dá)過的格子中的數(shù)字之和?，F(xiàn)在小R研發(fā)了一款彈跳機(jī)器人來參加這個游戲。但是這個機(jī)器人有一個非常嚴(yán)重的缺陷，它每次向右彈跳的距離只能為固定的d。小R希望改進(jìn)他的機(jī)器人，如果他花g個金幣改進(jìn)他的機(jī)器人，那么他的機(jī)器人靈活性就能增加g，但是需要注意的是，每次彈跳的距離至少為1。具體而言，當(dāng)g<d時，他的機(jī)器人每次可以選擇向右彈跳的距離為d-g,d-g+1,d-g+2，…，d+g-2，d+g-1，d+g；否則（當(dāng)g≥d時），他的機(jī)器人每次可以選擇向右彈跳的距離為1，2，3，…，d+g-2，d+g-1，d+g?，F(xiàn)在小R希望獲得至少k分，請問他至少要花多少金幣來改造他的機(jī)器人。【輸入格式】輸入文件名為jump.in。第一行三個正整數(shù)n，d，k，分別表示格子的數(shù)目，改進(jìn)前機(jī)器人彈跳的固定距離，以及希望至少獲得的分?jǐn)?shù)。相鄰兩個數(shù)之間用一個空格隔開。接下來n行，每行兩個正整數(shù)????,????，分別表示起點(diǎn)到第i個格子的距離以及第i個格子的分?jǐn)?shù)。兩個數(shù)之間用一個空格隔開。保證????按遞增順序輸入。【輸出格式】輸出文件名為jump.out。共一行，一個整數(shù)，表示至少要花多少金幣來改造他的機(jī)器人。若無論如何他都無法獲得至少k分，輸出-1?！据斎胼敵鰳永?】jump.injump.out7410265-33-31311762022見選手目錄下的jump/jump1.in和jump/jump1.ans?！据斎胼敵鰳永?說明】花費(fèi)2個金幣改進(jìn)后，小R的機(jī)器人依次選擇的向右彈跳的距離分別為2，3，5，3，4，3，先后到達(dá)的位置分別為2，5，10，13，17，20，對應(yīng)1,2,3,5,6,7這6個格子。這些格子中的數(shù)字之和15即為小R獲得的分?jǐn)?shù)?！据斎胼敵鰳永?】jump.injump.out7420265-33-3131176202-1見選手目錄下的jump/jump2.in和jump/jump2.ans。【輸入輸出樣例2說明】由于樣例中7個格子組合的最大可能數(shù)字之和只有