第十一屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽普及組復(fù)賽試題

1、NOIP2005復(fù)賽普及組試題第十一屆全國(guó)青少年奧林匹克信息學(xué)聯(lián)賽復(fù)賽普及組試題 （普及組 三小時(shí)完成）一、陶陶摘蘋(píng)果(apple.pas/c/cpp)【問(wèn)題描述】 陶陶家的院子里有一棵蘋(píng)果樹(shù)，每到秋天樹(shù)上就會(huì)結(jié)出10個(gè)蘋(píng)果。蘋(píng)果成熟的時(shí)候，陶陶就會(huì)跑去摘蘋(píng)果。陶陶有個(gè)30厘米高的板凳，當(dāng)她不能直接用手摘到蘋(píng)果的時(shí)候，就會(huì)踩到板凳上再試試。 現(xiàn)在已知10個(gè)蘋(píng)果到地面的高度，以及陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度，請(qǐng)幫陶陶算一下她能夠摘到的蘋(píng)果的數(shù)目。假設(shè)她碰到蘋(píng)果，蘋(píng)果就會(huì)掉下來(lái)?！据斎胛募枯斎胛募pple.in包括兩行數(shù)據(jù)。第一行包含10個(gè)100到200之間（包括100和200）的整數(shù)

2、（以厘米為單位）分別表示10個(gè)蘋(píng)果到地面的高度，兩個(gè)相鄰的整數(shù)之間用一個(gè)空格隔開(kāi)。第二行只包括一個(gè)100到120之間（包含100和120）的整數(shù)（以厘米為單位），表示陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度?！据敵鑫募枯敵鑫募pple.out包括一行，這一行只包含一個(gè)整數(shù)，表示陶陶能夠摘到的蘋(píng)果的數(shù)目?！緲永斎搿?00 200 150 140 129 134 167 198 200 111110【樣例輸出】5二、校門(mén)外的樹(shù) (tree.pas/c/cpp)【問(wèn)題描述】某校大門(mén)外長(zhǎng)度為L(zhǎng)的馬路上有一排樹(shù)，每?jī)煽孟噜彽臉?shù)之間的間隔都是1米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸0的位置，另

3、一端在L的位置；數(shù)軸上的每個(gè)整數(shù)點(diǎn)，即0，1，2，L，都種有一棵樹(shù)。由于馬路上有一些區(qū)域要用來(lái)建地鐵。這些區(qū)域用它們?cè)跀?shù)軸上的起始點(diǎn)和終止點(diǎn)表示。已知任一區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分?，F(xiàn)在要把這些區(qū)域中的樹(shù)（包括區(qū)域端點(diǎn)處的兩棵樹(shù)）移走。你的任務(wù)是計(jì)算將這些樹(shù)都移走后，馬路上還有多少棵樹(shù)。【輸入文件】輸入文件tree.in的第一行有兩個(gè)整數(shù)L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長(zhǎng)度，M代表區(qū)域的數(shù)目，L和M之間用一個(gè)空格隔開(kāi)。接下來(lái)的M行每行包含兩個(gè)不同的整數(shù)，用一個(gè)空格隔開(kāi)，表示一個(gè)區(qū)域的

4、起始點(diǎn)和終止點(diǎn)的坐標(biāo)?！据敵鑫募枯敵鑫募ree.out包括一行，這一行只包含一個(gè)整數(shù)，表示馬路上剩余的樹(shù)的數(shù)目?！緲永斎搿?00 3150 300100 200470 471【樣例輸出】298【數(shù)據(jù)規(guī)?！繉?duì)于20%的數(shù)據(jù)，區(qū)域之間沒(méi)有重合的部分；對(duì)于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。三、采藥(medic.pas/c/cpp)【問(wèn)題描述】辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的

5、價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?如果你是辰辰，你能完成這個(gè)任務(wù)嗎？【輸入文件】輸入文件medic.in的第一行有兩個(gè)整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100），用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值?！据敵鑫募枯敵鑫募edic.out包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)

6、值。【樣例輸入】70 371 10069 11 2【樣例輸出】3【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，M <= 10；對(duì)于全部的數(shù)據(jù)，M <= 100。四、循環(huán)(circle.pas/c/cpp)【問(wèn)題描述】樂(lè)樂(lè)是一個(gè)聰明而又勤奮好學(xué)的孩子。他總喜歡探求事物的規(guī)律。一天，他突然對(duì)數(shù)的正整數(shù)次冪產(chǎn)生了興趣。眾所周知，2的正整數(shù)次冪最后一位數(shù)總是不斷的在重復(fù)2，4，8，6，2，4，8，6我們說(shuō)2的正整數(shù)次冪最后一位的循環(huán)長(zhǎng)度是4（實(shí)際上4的倍數(shù)都可以說(shuō)是循環(huán)長(zhǎng)度，但我們只考慮最小的循環(huán)長(zhǎng)度）。類(lèi)似的，其余的數(shù)字的正整數(shù)次冪最后一位數(shù)也有類(lèi)似的循環(huán)現(xiàn)象：循環(huán)循環(huán)長(zhǎng)度22、4、8、6433、9、7

7、、1444、6255166177、9、3、1488、4、2、6499、12這時(shí)樂(lè)樂(lè)的問(wèn)題就出來(lái)了：是不是只有最后一位才有這樣的循環(huán)呢？對(duì)于一個(gè)整數(shù)n的正整數(shù)次冪來(lái)說(shuō)，它的后k位是否會(huì)發(fā)生循環(huán)？如果循環(huán)的話(huà)，循環(huán)長(zhǎng)度是多少呢？注意：1 如果n的某個(gè)正整數(shù)次冪的位數(shù)不足k，那么不足的高位看做是0。2 如果循環(huán)長(zhǎng)度是L，那么說(shuō)明對(duì)于任意的正整數(shù)a，n的a次冪和a + L次冪的最后k位都相同。【輸入文件】輸入文件circle.in只有一行，包含兩個(gè)整數(shù)n（1 <= n < 10100）和k（1 <= k <= 100），n和k之間用一個(gè)空格隔開(kāi)，表示要求n的正整數(shù)次冪的最后k位的循環(huán)長(zhǎng)度。【輸出文件】輸