NOIP提高組 第一天 Day試題

1、全國信息學奧林匹克聯(lián)賽（NOIP2011）復賽提高組day1（請選手務必仔細閱讀本頁內容）一題目概況中文題目名稱鋪地毯選擇客棧mayan 游戲英文題目與子目錄名carpethotelmayan可執(zhí)行文件名carpethotelmayan輸入文件名carpet.inhotel.inmayan.in輸出文件名carpet.outhotel.outmayan.out每個測試點時限1 秒1 秒3 秒測試點數(shù)目101010每個測試點分值101010附加樣例文件有有有結果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)二提交源程序文件名對于 C+語言carpet.cpphotel.cppma

2、yan.cpp對于 C 語言carpet.chotel.cmayan.c對于 pascal 語言carpet.pashotel. pasmayan. pas三編譯命令（不包含任何優(yōu)化開關）對于 C+語言g+ -o carpet carpet.cpp -lmg+ -o hotel hotel.cpp -lmg+ -o mayan mayan.cpp -lm對于 C 語言gcc -o carpet carpet.c -lmgcc -o hotel hotel.c-lmgcc -o mayan mayan.c -lm對于 pascal 語言fpc carpet.pasfpc hotel.pasfpc

3、 mayan.pas四運行內存限制內存上限128M128M128M注意事項：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結束時的返回值必須是 0。3、全國統(tǒng)一評測時采用的機器配置為：CPU P4 3.0GHz，內存 1G，上述時限以此配置為準。4、特別提醒：評測在 NOI Linux 下進行?！締栴}描述】1鋪地毯(carpet.cpp/c/pas)為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區(qū)域（可看做是平面直角坐標 系的第一象限）鋪上一些矩形地毯。一共有 n 張地毯，編號從 1 到 n。現(xiàn)在將這些地毯按照 編

4、號從小到大的順序平行于坐標軸先后鋪設，后鋪的地毯覆蓋在前面已經鋪好的地毯之上。 地毯鋪設完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號。注意：在矩形 地毯邊界和四個頂點上的點也算被地毯覆蓋?！据斎搿枯斎胛募麨?carpet.in。 輸入共 n+2 行。第一行，一個整數(shù) n，表示總共有 n 張地毯。接下來的 n 行中，第 i+1 行表示編號 i 的地毯的信息，包含四個正整數(shù) a，b，g，k，每 兩個整數(shù)之間用一個空格隔開，分別表示鋪設地毯的左下角的坐標（a，b）以及地毯在 x 軸和 y 軸方向的長度。第 n+2 行包含兩個正整數(shù) x 和 y，表示所求的地面的點的坐標（x，y）?！据?/p>

5、出】輸出文件名為 carpet.out。輸出共 1 行，一個整數(shù)，表示所求的地毯的編號；若此處沒有被地毯覆蓋則輸出-1?！据斎胼敵鰳永?1】carpet.incarpet.out31 0 2 30 2 3 32 1 3 32 23【輸入輸出樣例說明】如下圖，1 號地毯用實線表示，2 號地毯用虛線表示，3 號用雙實線表示，覆蓋點（2，2）的最上面一張地毯是 3 號地毯。yx【輸入輸出樣例 2】carpet.incarpet.out31 0 2 30 2 3 32 1 3 34 5-1【輸入輸出樣例說明】如上圖，1 號地毯用實線表示，2 號地毯用虛線表示，3 號用雙實線表示，點（4，5） 沒有被地

6、毯覆蓋，所以輸出-1?！緮?shù)據(jù)范圍】對于 30%的數(shù)據(jù)，有 n2；對于 50%的數(shù)據(jù)，0a, b, g, k100；對于 100%的數(shù)據(jù)，有 0n10,000，0a, b, g, k100,000?！締栴}描述】2選擇客棧(hotel.cpp/c/pas)麗江河邊有 n 家很有特色的客棧，客棧按照其位置順序從 1 到 n 編號。每家客棧都按照 某一種色調進行裝飾（總共 k 種，用整數(shù) 0 k-1 表示），且每家客棧都設有一家咖啡店，每 家咖啡店均有各自的最低消費。兩位游客一起去麗江旅游，他們喜歡相同的色調，又想嘗試兩個不同的客棧，因此決定 分別住在色調相同的兩家客棧中。晚上，他們打算選擇一家咖啡店

7、喝咖啡，要求咖啡店位于 兩人住的兩家客棧之間（包括他們住的客棧），且咖啡店的最低消費不超過 p。他們想知道總共有多少種選擇住宿的方案，保證晚上可以找到一家最低消費不超過 p元的咖啡店小聚。【輸入】輸入文件 hotel.in，共 n+1 行。第一行三個整數(shù) n，k，p，每兩個整數(shù)之間用一個空格隔開，分別表示客棧的個數(shù)，色 調的數(shù)目和能接受的最低消費的最高值；接下來的 n 行，第 i+1 行兩個整數(shù)，之間用一個空格隔開，分別表示 i 號客棧的裝飾色 調和 i 號客棧的咖啡店的最低消費?！据敵觥枯敵鑫募麨?hotel.out。輸出只有一行，一個整數(shù)，表示可選的住宿方案的總數(shù)。【輸入輸出樣例 1】h

8、otel.inhotel.out5 2 30 51 30 21 41 53【輸入輸出樣例說明】客棧編號色調01011最低消費532452 人要住同樣色調的客棧，所有可選的住宿方案包括：住客棧，但是若選擇住 4、5 號客棧的話，4、5 號客棧之間的咖啡店的最低消費是 4，而兩人能承受 的最低消費是 3 元，所以不滿足要求。因此只有前 3 種方案可選?！緮?shù)據(jù)范圍】對于 30%的數(shù)據(jù)，有 n100； 對于 50%的數(shù)據(jù)，有 n1,000；對于 100%的數(shù)據(jù)，有 2n200,000，0<k50，0p100， 0最低消費100?！締栴}描述】3Mayan 游戲(mayan.cpp/c/pas)Ma

9、yan puzzle 是最近流行起來的一個游戲。游戲界面是一個 7 行 5 列的棋盤，上面堆放 著一些方塊，方塊不能懸空堆放，即方塊必須放在最下面一行，或者放在其他方塊之上。游 戲通關是指在規(guī)定的步數(shù)內消除所有的方塊，消除方塊的規(guī)則如下：1、 每步移動可以且僅可以沿橫向（即向左或向右）拖動某一方塊一格：當拖動這一方 塊時，如果拖動后到達的位置（以下稱目標位置）也有方塊，那么這兩個方塊將交換位置（參 見輸入輸出樣例說明中的圖 6 到圖 7）；如果目標位置上沒有方塊，那么被拖動的方塊將從 原來的豎列中抽出，并從目標位置上掉落（直到不懸空，參見下面圖 1 和圖 2）；圖 1圖 2圖 32、 任一時刻

10、，如果在一橫行或者豎列上有連續(xù)三個或者三個以上相同顏色的方塊，則 它們將立即被消除（參見圖 1 到圖 3）。注意：a) 如果同時有多組方塊滿足消除條件，幾組方塊會同時被消除（例如下面圖 4，三個顏 色為 1 的方塊和三個顏色為 2 的方塊會同時被消除，最后剩下一個顏色為 2 的方塊）。11111b) 當出現(xiàn)行和列都滿足消除條件且行列共享某個方塊時，行和列上滿足消除條件的所 有方塊會被同時消除（例如下面圖 5 所示的情形，5 個方塊會同時被消除）。2111222圖 4圖 53、 方塊消除之后，消除位置之上的方塊將掉落，掉落后可能會引起新的方塊消除。注 意：掉落的過程中將不會有方塊的消除。上面圖

11、1 到圖 3 給出了在棋盤上移動一塊方塊之后棋盤的變化。棋盤的左下角方塊的坐 標為（0, 0），將位于（3, 3）的方塊向左移動之后，游戲界面從圖 1 變成圖 2 所示的狀態(tài)， 此時在一豎列上有連續(xù)三塊顏色為 4 的方塊，滿足消除條件，消除連續(xù) 3 塊顏色為 4 的方塊 后，上方的顏色為 3 的方塊掉落，形成圖 3 所示的局面。【輸入】輸入文件 mayan.in，共 6 行。第一行為一個正整數(shù) n，表示要求游戲通關的步數(shù)。接下來的 5 行，描述 7*5 的游戲界面。每行若干個整數(shù)，每兩個整數(shù)之間用一個空格隔 開，每行以一個 0 結束，自下向上表示每豎列方塊的顏色編號（顏色不多于 10 種，從

12、1 開 始順序編號，相同數(shù)字表示相同顏色）。輸入數(shù)據(jù)保證初始棋盤中沒有可以消除的方塊?！据敵觥枯敵鑫募麨?mayan.out。如果有解決方案，輸出 n 行，每行包含 3 個整數(shù) x，y，g，表示一次移動，每兩個整數(shù)之間用一個空格隔開，其中（x，y）表示要移動的方塊的坐標，g 表示移動的方向，1 表示 向右移動，-1 表示向左移動。注意：多組解時，按照 x 為第一關健字，y 為第二關健字，1 優(yōu)先于-1，給出一組字典序最小的解。游戲界面左下角的坐標為（0，0）。如果沒有解決方案，輸出一行，包含一個整數(shù)-1。【輸入輸出樣例 1】mayan.inmayan.out31 02 1 02 3 4 03 1 02 4 3 4 02 1 13 1 13 0 1【輸入輸出樣例說明】按箭頭方向的