全國信息學(xué)奧林匹克競賽NOIP試題

1、2002年全國青少年信息學(xué)（計算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題題一 級數(shù)求和（存盤名：NOIPC1）問題描述:已知：Sn= 112131n。顯然對于任意一個整數(shù)K，當(dāng)n足夠大的時候，Sn大于K。現(xiàn)給出一個整數(shù)K（1<=k<=15），要求計算出一個最小的n；使得SnK。輸入鍵盤輸入 k輸出屏幕輸出 n輸入輸出樣例輸人：1輸出：2題二 選數(shù)（存盤名：NOIPC2）問題描述:已知 n 個整數(shù) x1,x2,xn，以及一個整數(shù) k（kn）。從 n 個整數(shù)中任選 k 個整數(shù)相加，可分別得到一系列的和。例如當(dāng) n=4，k3，4 個整數(shù)分別為 3，7，12，19 時，可得全部的組合與它們的和為：37

2、12=22 371929 7121938 3121934。 現(xiàn)在，要求你計算出和為素數(shù)共有多少種。例如上例，只有一種的和為素數(shù)：371929）。輸入：鍵盤輸入，格式為：n , k （1<=n<=20，kn）x1,x2，,xn （1<=xi<=5000000）輸出：屏幕輸出，格式為：一個整數(shù)（滿足條件的種數(shù)）。輸入輸出樣例:輸入：4 33 7 12 19輸出：1題三 產(chǎn)生數(shù)（存盤名：NOIPC3）問題描述:給出一個整數(shù) n（n<1030) 和 k 個變換規(guī)則（k<=15）。 規(guī)則：一位數(shù)可變換成另一個一位數(shù)：規(guī)則的右部不能為零。例如：n=234。有規(guī)則（k2）

3、：2> 53> 6上面的整數(shù) 234 經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）: 234534264564共 4 種不同的產(chǎn)生數(shù)問題：給出一個整數(shù) n 和 k 個規(guī)則。求出：經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同整數(shù)。 僅要求輸出個數(shù)。輸入:鍵盤輸人，格式為：n kx1 y1x2 y2. .xn yn輸出:屏幕輸出，格式為：一個整數(shù)（滿足條件的個數(shù)）：輸入輸出樣例:輸入:234 22 53 6輸出：4題四 過河卒（存盤名：NOIPC4）問題描述:如圖，A 點有一個過河卒，需要走到目標(biāo) B 點。卒行走規(guī)則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如上圖的C

4、點），該馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點。例如上圖 C 點上的馬可以控制 9 個點（圖中的P1，P2 P8 和 C）。卒不能通過對方馬的控制點。棋盤用坐標(biāo)表示，A 點（0，0）、B 點（n,m）(n,m 為不超過 20 的整數(shù)，并由鍵盤輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定: C<>A，同時C<>B）?，F(xiàn)在要求你計算出卒從 A 點能夠到達(dá) B 點的路徑的條數(shù)。輸入:鍵盤輸入B點的坐標(biāo)（n,m）以及對方馬的坐標(biāo)（X,Y）不用盤錯輸出:屏幕輸出一個整數(shù)（路徑的條數(shù)）。輸入輸出樣例:輸入：6 6 3 2輸出：172005年第十一屆NOIP復(fù)賽試題（提高組

5、）發(fā)布日期: 2006-01-22 訪問總次數(shù): 11誰拿了最多獎學(xué)金(scholar.pas/c/cpp)【問題描述】某校的慣例是在每學(xué)期的期末考試之后發(fā)放獎學(xué)金。發(fā)放的獎學(xué)金共有五種，獲取的條件各自不同：1) 院士獎學(xué)金，每人8000元，期末平均成績高于80分（>80），并且在本學(xué)期內(nèi)發(fā)表1篇或1篇以上論文的學(xué)生均可獲得；2) 五四獎學(xué)金，每人4000元，期末平均成績高于85分（>85），并且班級評議成績高于80分（>80）的學(xué)生均可獲得；3) 成績優(yōu)秀獎，每人2000元，期末平均成績高于90分（>90）的學(xué)生均可獲得；4) 西部獎學(xué)金，每人1000元，期末平均成績

6、高于85分（>85）的西部省份學(xué)生均可獲得；5) 班級貢獻(xiàn)獎，每人850元，班級評議成績高于80分（>80）的學(xué)生干部均可獲得；只要符合條件就可以得獎，每項獎學(xué)金的獲獎人數(shù)沒有限制，每名學(xué)生也可以同時獲得多項獎學(xué)金。例如姚林的期末平均成績是87分，班級評議成績82分，同時他還是一位學(xué)生干部，那么他可以同時獲得五四獎學(xué)金和班級貢獻(xiàn)獎，獎金總數(shù)是4850元。現(xiàn)在給出若干學(xué)生的相關(guān)數(shù)據(jù)，請計算哪些同學(xué)獲得的獎金總數(shù)最高（假設(shè)總有同學(xué)能滿足獲得獎學(xué)金的條件）?！据斎胛募枯斎胛募cholar.in的第一行是一個整數(shù)N（1 <= N <= 100），表示學(xué)生的總數(shù)。接下來的N行

7、每行是一位學(xué)生的數(shù)據(jù)，從左向右依次是姓名，期末平均成績，班級評議成績，是否是學(xué)生干部，是否是西部省份學(xué)生，以及發(fā)表的論文數(shù)。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級評議成績都是0到100之間的整數(shù)（包括0和100）；是否是學(xué)生干部和是否是西部省份學(xué)生分別用一個字符表示，Y表示是，N表示不是；發(fā)表的論文數(shù)是0到10的整數(shù)（包括0和10）。每兩個相鄰數(shù)據(jù)項之間用一個空格分隔?！据敵鑫募枯敵鑫募cholar.out包括三行，第一行是獲得最多獎金的學(xué)生的姓名，第二行是這名學(xué)生獲得的獎金總數(shù)。如果有兩位或兩位以上的學(xué)生獲得的獎金最多，輸出他們之中在輸入文件中

8、出現(xiàn)最早的學(xué)生的姓名。第三行是這N個學(xué)生獲得的獎學(xué)金的總數(shù)。【樣例輸入】4YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1【樣例輸出】ChenRuiyi900028700過河(river.pas/c/cpp)【問題描述】在河上有一座獨木橋，一只青蛙想沿著獨木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨木橋上青蛙可能到達(dá)的點看成數(shù)軸上的一串整點：0，1，L（其中L是橋的長度）。坐標(biāo)為0的點表示橋的起點，坐標(biāo)為L的點

9、表示橋的終點。青蛙從橋的起點開始，不停的向終點方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐標(biāo)為L的點時，就算青蛙已經(jīng)跳出了獨木橋。題目給出獨木橋的長度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。【輸入文件】輸入文件river.in的第一行有一個正整數(shù)L（1 <= L <= 109），表示獨木橋的長度。第二行有三個正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個數(shù)，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有

10、M個不同的正整數(shù)分別表示這M個石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點和終點處沒有石子）。所有相鄰的整數(shù)之間用一個空格隔開。【輸出文件】輸出文件river.out只包括一個整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)?！緲永斎搿?02 3 52 3 5 6 7【樣例輸出】2【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，L <= 10000；對于全部的數(shù)據(jù)，L <= 109。篝火晚會(fire.pas/c/cpp)【問題描述】佳佳剛進(jìn)高中，在軍訓(xùn)的時候，由于佳佳吃苦耐勞，很快得到了教官的賞識，成為了“小教官”。在軍訓(xùn)結(jié)束的那天晚上，佳佳被命令組織同學(xué)們進(jìn)行篝火晚會。一共有n個同學(xué)，編號從1到n。一開始，同學(xué)

11、們按照1，2，n的順序坐成一圈，而實際上每個人都有兩個最希望相鄰的同學(xué)。如何下命令調(diào)整同學(xué)的次序，形成新的一個圈，使之符合同學(xué)們的意愿，成為擺在佳佳面前的一大難題。佳佳可向同學(xué)們下達(dá)命令，每一個命令的形式如下：(b1, b2,. bm -1, bm)這里m的值是由佳佳決定的，每次命令m的值都可以不同。這個命令的作用是移動編號是b1，b2， bm 1，bm的這m個同學(xué)的位置。要求b1換到b2的位置上，b2換到b3的位置上，要求bm換到b1的位置上。執(zhí)行每個命令都需要一些代價。我們假定如果一個命令要移動m個人的位置，那么這個命令的代價就是m。我們需要佳佳用最少的總代價實現(xiàn)同學(xué)們的意愿，你能幫助佳佳

12、嗎？【輸入文件】輸入文件fire.in的第一行是一個整數(shù)n（3 <= n <= 50000），表示一共有n個同學(xué)。其后n行每行包括兩個不同的正整數(shù)，以一個空格隔開，分別表示編號是1的同學(xué)最希望相鄰的兩個同學(xué)的編號，編號是2的同學(xué)最希望相鄰的兩個同學(xué)的編號，編號是n的同學(xué)最希望相鄰的兩個同學(xué)的編號?！据敵鑫募枯敵鑫募ire.out包括一行，這一行只包含一個整數(shù)，為最小的總代價。如果無論怎么調(diào)整都不能符合每個同學(xué)的愿望，則輸出-1?！緲永斎搿?3 44 31 21 2【樣例輸出】2【數(shù)據(jù)規(guī)模】對于30%的數(shù)據(jù)，n <= 1000；對于全部的數(shù)據(jù)，n <= 50000。

13、等價表達(dá)式(equal.pas/c/cpp)【問題描述】明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個很麻煩的選擇題。這個題目的題干中首先給出了一個代數(shù)表達(dá)式，然后列出了若干選項，每個選項也是一個代數(shù)表達(dá)式，題目的要求是判斷選項中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價的。這個題目手算很麻煩，因為明明對計算機(jī)編程很感興趣，所以他想是不是可以用計算機(jī)來解決這個問題。假設(shè)你是明明，能完成這個任務(wù)嗎？這個選擇題中的每個表達(dá)式都滿足下面的性質(zhì)：1 表達(dá)式只可能包含一個變量a。2 表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000。3 表達(dá)式中可以包括四種運(yùn)算+（加），-（減），*（乘），（乘冪），以

14、及小括號(，)。小括號的優(yōu)先級最高，其次是，然后是*，最后是+和-。+和-的優(yōu)先級是相同的。相同優(yōu)先級的運(yùn)算從左到右進(jìn)行。（注意：運(yùn)算符+，-，*，以及小括號(，)都是英文字符）4 冪指數(shù)只可能是1到10之間的正整數(shù)（包括1和10）。5 表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。下面是一些合理的表達(dá)式的例子：(a1) 2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1 + (a -1)3，1109【輸入文件】輸入文件equal.in的第一行給出的是題干中的表達(dá)式。第二行是一個整數(shù)n（2 <= n <= 26），表示選項的個數(shù)。后面n行，每行包括一個選項中的表達(dá)式

15、。這n個選項的標(biāo)號分別是A，B，C，D輸入中的表達(dá)式的長度都不超過50個字符，而且保證選項中總有表達(dá)式和題干中的表達(dá)式是等價的?！据敵鑫募枯敵鑫募qual.out包括一行，這一行包括一系列選項的標(biāo)號，表示哪些選項是和題干中的表達(dá)式等價的。選項的標(biāo)號按照字母順序排列，而且之間沒有空格。【樣例輸入】( a + 1) 23(a-1)2+4*aa + 1+ aa2 + 2 * a * 1 + 12 + 10 -10 +a -a【樣例輸出】AC【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，表達(dá)式中只可能出現(xiàn)兩種運(yùn)算符+和-；對于其它的數(shù)據(jù)，四種運(yùn)算符+，-，*，在表達(dá)式中都可能出現(xiàn)。對于全部的數(shù)據(jù)，表達(dá)式中都可能出

16、現(xiàn)小括號(和)。【推薦給朋友】關(guān)閉窗口】 【2005年第十一屆NOIP復(fù)賽試題（普及組）發(fā)布日期: 2006-01-22 訪問總次數(shù): 12一、陶陶摘蘋果(apple.pas/c/cpp)【問題描述】陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結(jié)出10個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有個30厘米高的板凳，當(dāng)她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試?，F(xiàn)在已知10個蘋果到地面的高度，以及陶陶把手伸直的時候能夠達(dá)到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會掉下來。【輸入文件】輸入文件apple.in包括兩行數(shù)據(jù)。第一行包含10個100到200

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

18、，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個整數(shù)點，即0，1，2，L，都種有一棵樹。由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點和終止點表示。已知任一區(qū)域的起始點和終止點的坐標(biāo)都是整數(shù)，區(qū)域之間可能有重合的部分?，F(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點處的兩棵樹）移走。你的任務(wù)是計算將這些樹都移走后，馬路上還有多少棵樹?！据斎胛募枯斎胛募ree.in的第一行有兩個整數(shù)L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區(qū)域的數(shù)目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數(shù)，

19、用一個空格隔開，表示一個區(qū)域的起始點和終止點的坐標(biāo)。【輸出文件】輸出文件tree.out包括一行，這一行只包含一個整數(shù)，表示馬路上剩余的樹的數(shù)目?！緲永斎搿?00 3150 300100 200470 471【樣例輸出】298【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，區(qū)域之間沒有重合的部分；對于其它的數(shù)據(jù)，區(qū)域之間有重合的情況。三、采藥(medic.pas/c/cpp)【問題描述】辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大。”如果你是辰辰，你能完成這個任務(wù)嗎？【輸入文件】輸入文件medic.in的第一行有兩個整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值?！据敵鑫募枯敵鑫募?/p>