全國(guó)信息學(xué)奧林匹克競(jìng)賽NOIP試題

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

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

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

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

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

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

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

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

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

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

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

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

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

14、及小括號(hào)(，)。小括號(hào)的優(yōu)先級(jí)最高，其次是，然后是*，最后是+和-。+和-的優(yōu)先級(jí)是相同的。相同優(yōu)先級(jí)的運(yùn)算從左到右進(jìn)行。（注意：運(yùn)算符+，-，*，以及小括號(hào)(，)都是英文字符）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á)式。第二行是一個(gè)整數(shù)n（2 <= n <= 26），表示選項(xiàng)的個(gè)數(shù)。后面n行，每行包括一個(gè)選項(xiàng)中的表達(dá)式

15、。這n個(gè)選項(xiàng)的標(biāo)號(hào)分別是A，B，C，D輸入中的表達(dá)式的長(zhǎng)度都不超過(guò)50個(gè)字符，而且保證選項(xiàng)中總有表達(dá)式和題干中的表達(dá)式是等價(jià)的。【輸出文件】輸出文件equal.out包括一行，這一行包括一系列選項(xiàng)的標(biāo)號(hào)，表示哪些選項(xiàng)是和題干中的表達(dá)式等價(jià)的。選項(xiàng)的標(biāo)號(hào)按照字母順序排列，而且之間沒(méi)有空格?！緲永斎搿? a + 1) 23(a-1)2+4*aa + 1+ aa2 + 2 * a * 1 + 12 + 10 -10 +a -a【樣例輸出】AC【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，表達(dá)式中只可能出現(xiàn)兩種運(yùn)算符+和-；對(duì)于其它的數(shù)據(jù)，四種運(yùn)算符+，-，*，在表達(dá)式中都可能出現(xiàn)。對(duì)于全部的數(shù)據(jù)，表達(dá)式中都可能出

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

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

18、，馬路的一端在數(shù)軸0的位置，另一端在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ù)?！据斎胛募枯斎胛募ree.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ù)，

19、用一個(gè)空格隔開(kāi)，表示一個(gè)區(qū)域的起始點(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í)間，每一株也有它自身的價(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à)值?！据敵鑫募枯敵鑫募?/p>