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

2、.cpp對于C語百carpet.chotel.cmayan.c對于pascal語百carpet.pashotel. pasmayan. pas三.編譯命令（不包含任何優化開關）對于C+語言g+ - o carpet carpet.cpp -lmg+ - o hotel hotel.cpp -lmg+ - o mayan mayan.cpp -lm對于C語百gcc - o carpetgcc - o hotel hotel.cgcc - o mayancarpet.c -lm-lmmayan.c -lm對于pascal語百fpc carpet.pasfpc hotel.pasfpc mayan.

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

4、的地毯覆蓋在前面已經鋪好的地毯之上。地毯鋪設完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆蓋。【輸入】輸入文件名為carpet.in。輸入共n+2行。第一行，一個整數 n,表示總共有n張地毯。接下來的n行中，第i+1行表示編號i的地毯的信息，包含四個正整數 a, b, g, k,每 兩個整數之間用一個空格隔開，分別表示鋪設地毯的左下角的坐標（a, b）以及地毯在 x軸和y軸方向的長度。第n+2行包含兩個正整數 x和y,表示所求的地面的點的坐標（ x, y）。【輸出】輸出文件名為 carpet.out。輸出共1行，一個整數，表示所求的

5、地毯的編號；若此處沒有被地毯覆蓋則輸出-1。【輸入輸出樣例1】carpet.incarpet.out331 0 2 30 2 3 32 1 3 32 2【輸入輸出樣例說明】如下圖，1號地毯用實線表示，2號地毯用虛線表示，3號用雙實線表示，覆蓋點（2,2）的最上面一張地毯是 3號地毯。【輸入輸出樣例2】carpet.incarpet.out3-11 0 2 30 2 3 32 1 3 34 5【輸入輸出樣例說明】如上圖，1號地毯用實線表示，2號地毯用虛線表示，3號用雙實線表示，點（4,5） 沒有被地毯覆蓋，所以輸出 -1。【數據范圍】對于30%的數據，有nW 2;對于 50%的數據，0Wa, b

6、, g, kwi00；對于 100% 的數據，有 0w n< 10,000, 0<a, b, g, kw 100,000。2 .選擇客棧（hotel.cpp/c/pas）【問題描述】麗江河邊有n家很有特色的客棧，客棧按照其位置順序從 1到n編號。每家客棧都按照 某一種色調進行裝飾（總共 k種，用整數0 k-1表示），且每家客棧都設有一家咖啡店，每 家咖啡店均有各自的最低消費。兩位游客一起去麗江旅游， 他們喜歡相同的色調， 又想嘗試兩個不同的客棧， 因此決定 分別住在色調相同的兩家客棧中。晚上，他們打算選擇一家咖啡店喝咖啡， 要求咖啡店位于兩人住的兩家客棧之間（包括他們住的客棧），且

7、咖啡店的最低消費不超過 p。他們想知道總共有多少種選擇住宿的方案，保證晚上可以找到一家最低消費不超過p元的咖啡店小聚。【輸入】輸入文件hotel.in ,共n+1行。第一行三個整數 n, k, p,每兩個整數之間用一個空格隔開，分別表示客棧的個數，色 調的數目和能接受的最低消費的最高值；接下來的n行，第i+1行兩個整數，之間用一個空格隔開，分別表示i號客棧的裝飾色調和i號客棧的咖啡店的最低消費。輸出只有一行，一個整數，表示可選的住宿方案的總數。【輸入輸出樣例1】hotel.inhotel.out5 2 330 51 30 21 41 5【輸入輸出樣例說明】客棧編號色調01011最低消費5324

8、52人要住同樣色調的客棧， 所有可選的住宿方案包括： 住客棧，, 但是若選擇住4、5號客棧白話，4、5號客棧之間的咖啡店的最低消費是 4,而兩人能承受 的最低消費是3元，所以不滿足要求。因此只有前 3種方案可選。【數據范圍】對于30%的數據，有 nW 100；對于50%的數據，有 nW 1,000；對于 100%的數據，有 2W nw200,000, 0<k<50, 0<p<100, 0W最低消費w 100。3 . Mayan 游戲（mayan.cpp/c/pas）【問題描述】Mayan puzzle是最近流行起來的一個游戲。游戲界面是一個 7行5列的棋盤，上面堆放著一

9、些方塊，方塊不能懸空堆放，即方塊必須放在最下面一行，或者放在其他方塊之上。游 戲通關是指在規定的步數內消除所有的方塊，消除方塊的規則如下：1、每步移動可以且僅可以沿橫向（即向左或向右） 拖動某一方塊一格： 當拖動這一方塊時，如果拖動后到達的位置（以下稱目標位置）也有方塊，那么這兩個方塊將交換位置（參 見輸入輸出樣例說明中的圖6到圖7）;如果目標位置上沒有方塊，那么被拖動的方塊將從原來的豎列中抽出，并從目標位置上掉落（直到不懸空，參見下面圖1和圖2）;圖1圖2圖32、任一時刻，如果在一橫行或者豎列上有連續三個或者三個以上相同顏色的方塊，則它們將立即被消除（參見圖 1到圖3）。注意：a）如果同時有

10、多組方塊滿足消除條件，幾組方塊會同時被消除 （例如下面圖4,三個顏色為1的方塊和三個顏色為 2的方塊會同時被消除，最后剩下一個顏色為2的方塊）。b）當出現行和列都滿足消除條件且行列共享某個方塊時，行和列上滿足消除條件的所 有方塊會被同時消除（例如下面圖5所示的情形，5個方塊會同時被消除）。3、方塊消除之后，消除位置之上的方塊將掉落，掉落后可能會引起新的方塊消除。注意：掉落的過程中將不會有方塊的消除。上面圖1到圖3給出了在棋盤上移動一塊方塊之后棋盤的變化。棋盤的左下角方塊的坐標為（0, 0）,將位于（3, 3）的方塊向左移動之后，游戲界面從圖1變成圖2所示的狀態，此時在一豎列上有連續三塊顏色為4

11、的方塊，滿足消除條件，消除連續3塊顏色為4的方塊后，上方的顏色為 3的方塊掉落，形成圖 3所示的局面。【輸入】輸入文件 mayan.in ,共6行。第一行為一個正整數 n,表示要求游戲通關的步數。接下來的5行，描述7*5的游戲界面。每行若干個整數，每兩個整數之間用一個空格隔 開，每行以一個 0結束，自下向上表示每豎列方塊的顏色編號（顏色不多于10種，從1開始順序編號，相同數字表示相同顏色）。輸入數據保證初始棋盤中沒有可以消除的方塊。【輸出】輸出文件名為 mayan.out。如果有解決方案，輸出 n行，每行包含3個整數x, y, g,表示一次移動，每兩個整數 之間用一個空格隔開，其中（x, y）表示要移動的方塊的坐標，g表示移動的方向，1表示向右移動，-1表示向左移動。注意：多組解時，按照x為第一關健字，y為第二關健字，1優先于-1,給出一組字典序最小的解。游戲界面左下角的坐標為（0, 0）。411二圖64411.金I2圖7圖11111144圖10（2, 1）處的方格向樣例輸入的游戲局面如上面第一個圖片所示，依次移動的三步是:如果沒有解決方案，輸出一行，包含一個整數-1。【輸入輸出樣例1】mayan.inmayan.out32 1 11