北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 更多競賽真題免費(fèi)下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競賽 高考等資源 2005 年第十一屆 NOIP 復(fù)賽試題（普及組） 一、陶陶摘蘋果 ( apple.pas/c/cpp) 【問題描述】 陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會(huì)結(jié)出 10 個(gè)蘋果。蘋果成熟的時(shí)候，陶陶就會(huì)跑去摘蘋果。陶陶有個(gè) 30 厘米高的板凳，當(dāng)她不能直接用手摘到蘋果的時(shí)候，就會(huì)踩到板凳上再試試。 現(xiàn)在已知 10 個(gè)蘋果到地面的高度，以及陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會(huì)掉下來。 【輸入文件】 輸入文件 apple.in 包括兩行數(shù)據(jù)。第一行包含 10 個(gè) 100 到 200 之間（包括100 和 200）的整數(shù)（以厘米為單位）分別表示 10 個(gè)蘋果到地面的高度，兩個(gè)相鄰的整數(shù)之間用一個(gè)空格隔開。第二行只包括一個(gè) 100 到 120 之間（包含 100和 120）的整數(shù)（以厘米為單位），表示陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度。 【輸出文件】 輸出文件 apple.out 包括一行， 這一行只包含一個(gè)整數(shù)，表示陶陶能夠摘到的蘋果的數(shù)目。 【樣例輸入】 100 200 150 140 129 134 167 198 200 111 110 【樣例輸出】 5 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 二、校門外的樹 (tree.pas/c/cpp) 【問題描述】 某校大門外長度為 L 的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是 1米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸 0 的位置，另一端在 L的位置；數(shù)軸上的每個(gè)整數(shù)點(diǎn)，即 0， 1， 2， ， L，都種有一棵樹。 由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點(diǎn)和終止點(diǎn)表示。已知任一區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分。現(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點(diǎn)處的兩棵樹）移走。你的任務(wù)是計(jì)算將這些樹都移走后，馬路上還有多少棵樹。 【輸入文件】 輸入文件 tree.in 的第一行有兩個(gè)整數(shù) L（ 1 = L = 10000）和 M（ 1 = M = 100）， L 代表馬路的長度， M 代表區(qū)域的數(shù)目， L 和 M 之間用一個(gè)空格隔開。接下來的 M 行每行包含兩個(gè)不同的整數(shù)，用一個(gè)空格隔開，表示一個(gè)區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)。 【輸出文件】 輸出文件 tree.out 包括一行，這一行只包含一個(gè)整數(shù)，表示馬路上剩余的樹的數(shù)目。 【樣例輸入】 500 3 150 300 100 200 470 471 【樣例輸出】 298 【數(shù)據(jù)規(guī)?！?對于 20%的數(shù)據(jù)，區(qū)域之間沒有重合的部分； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 對于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 三、采藥 (medic.pas/c/cpp) 【問題描述】 辰辰是個(gè)天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對他說： “ 孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。 ” 如果你是辰辰，你能完成這個(gè)任務(wù)嗎？ 【輸入文件】 輸入文件 medic.in 的第一行有兩個(gè)整數(shù) T（ 1 = T = 1000）和 M（ 1 = M = 100），用一個(gè)空格隔開， T 代表總共能夠用來采藥的時(shí)間， M 代表山洞里的草藥的數(shù)目。接下來的 M 行每行包括兩個(gè)在 1 到 100 之間（包括 1 和 100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。 【輸出文件】 輸出文件 medic.out 包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。 【樣例輸入】 70 3 71 100 69 1 1 2 【樣例輸出】 3 【數(shù)據(jù)規(guī)?！?對于 30%的數(shù)據(jù)， M = 10； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 對于全部的數(shù)據(jù)， M = 100。 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 四、循環(huán) (circle.pas/c/cpp) 【問題描述】 樂樂是一個(gè)聰明而又勤奮好學(xué)的孩子。他總喜歡探求事物的規(guī)律。一天，他突然對數(shù)的正整數(shù)次冪產(chǎn)生了興趣。 眾所周知， 2 的正整數(shù)次冪最后一位數(shù)總是不斷的在重復(fù) 2， 4， 8， 6， 2， 4，8， 6 我們說 2 的正整數(shù)次冪最后一位的循環(huán)長度是 4（實(shí)際上 4 的倍數(shù)都可以說是循環(huán)長度，但我們只考慮最小的循環(huán)長度）。類似的，其余的數(shù)字的正整數(shù)次冪最后一位數(shù)也有類似的循環(huán)現(xiàn)象： 循環(huán) 循環(huán)長度 2 2、 4、 8、 6 4 3 3、 9、 7、 1 4 4 4、 6 2 5 5 1 6 6 1 7 7、 9、 3、 1 4 8 8、 4、 2、 6 4 9 9、 1 2 這時(shí)樂樂的問題就出來了：是不是只有最后一位才有這樣的循環(huán)呢？對于一個(gè)整數(shù) n 的正整數(shù)次冪來說，它的后 k 位是否會(huì)發(fā)生循環(huán)？如果循環(huán)的話，循環(huán)長度是多少呢？ 注意： 1 如果 n 的某個(gè)正整數(shù)次冪的位數(shù)不足 k，那么不足的高位看做是 0。 2 如果循環(huán)長度是 L，那么說明對于任意的正整數(shù) a， n 的 a 次冪和 a + L次冪的最后 k 位都相同。 【輸入文件】 輸入文件 circle.in 只有一行，包含兩個(gè)整數(shù) n（ 1 = n 10100）和 k（ 1 = k = 100）， n 和 k 之間用一個(gè)空格隔開，表示要求 n 的正整數(shù)次冪的最后 k 位的循環(huán)長度。 【輸出文件】 輸出文件 circle.out 包括一行，這一行只包含一個(gè)整數(shù)，表示循環(huán)長度。如果循環(huán)不存在，輸出 -1。 北