1、NOI 95“同創(chuàng)杯”全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽分區(qū)聯(lián)賽復(fù)賽試題（高中組）（上機(jī)編程，完成時(shí)間：210 分鐘）<1>編碼問(wèn)題：設(shè)有一個(gè)數(shù)組A:ARRAY0.N-1 OF INTEGER；數(shù)組中存放的元素為0N-1 之間的整數(shù)，且Ai Aj（當(dāng)i j時(shí)）。例如： N=6 時(shí)，有：此時(shí)，數(shù)組A 的編碼定義如下：A0 的編碼為0；Ai 的編碼為：在A0 ，A1 上面數(shù)組A 的編碼為：A= （ 4，3， 0， 5，1， 2）， ， Ai-1 中比 Ai 的值小的個(gè)數(shù)（B= （0， 0，0，3，1， 2）i=1 ，2， ， N-1 ）程序要求解決以下問(wèn)題：給出數(shù)組 A 后，求出其

2、編碼。給出數(shù)組 A 的編碼后，求出A 中的原數(shù)據(jù)。<2> 燈的排列問(wèn)題：設(shè)在一排上有 N 個(gè)格子（ N 20），若在格子中放置有不同顏色的燈，每種燈的個(gè)數(shù)記為 N 1， N2， N k（ k 表示不同顏色燈的個(gè)數(shù)） 。放燈時(shí)要遵守下列規(guī)則：同一種顏色的燈不能分開(kāi)；不同顏色的燈之間至少要有一個(gè)空位置。例如： N=8 （格子數(shù)）R=2 （紅燈數(shù)）B=3 （藍(lán)燈數(shù)）放置的方法有：R-B 順序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBBB-R順序BBBBBBBBBBBBBBBBBRRRRBRRRRRRRR放置的總數(shù)為12 種。數(shù)據(jù)輸入的方式為：NP1（顏色，為一個(gè)字母）P2

3、N1（燈的數(shù)量）N2Q（結(jié)束標(biāo)記， Q 本身不是燈的顏色）程序要求：求出一種順序的排列方案及排列總數(shù)。<3> 設(shè)有一個(gè)四層的積木塊，1 4 層積木塊的數(shù)量依次為：5， 6，7， 8如下圖所示放置：815851691423414326其中，給出第三層與第四層所標(biāo)示的數(shù)字， 并已知第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)計(jì)算出來(lái)的。計(jì)算的方法是：第三層的某個(gè)數(shù)據(jù) A 是由第四層相鄰的兩個(gè)數(shù)據(jù) B， C 經(jīng)過(guò)某種計(jì)算后產(chǎn)生的：ABC計(jì)算所用到的計(jì)算符為：+，-，且無(wú)優(yōu)先級(jí)之分（自左向右計(jì)算），運(yùn)算符最多為2個(gè)。如： 3+45=3554+3=23可以看出，上圖中的第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)用以下計(jì)算

4、公式計(jì)算出來(lái)的：A=BC+B也就是： 8=23+2 ， 15=34+3， 14=26+2程序要求：給出第四層與第三層的數(shù)據(jù)后，將第一、 二層的每塊積木標(biāo)上相應(yīng)的數(shù)據(jù)，完整的積木圖及計(jì)算公式。并輸出整個(gè) 輸入數(shù)據(jù)不存在出錯(cuò)的情況，同時(shí)也不會(huì)超過(guò)整數(shù)的范圍。 計(jì)算時(shí)可允許出現(xiàn)以下情況：A=BA=BB+B（即可理解為運(yùn)算符的個(gè)數(shù)為零）（即全部由B 產(chǎn)生）第二屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題（高中組競(jìng)賽用時(shí)： 3 小時(shí)）1比賽安排（ 20 分）設(shè)有有 2 n（ n<=6）個(gè)球隊(duì)進(jìn)行單循環(huán)比賽，計(jì)劃在2 n 1 天內(nèi)完成，每個(gè)隊(duì)每天進(jìn)行一場(chǎng)比賽。設(shè)計(jì)一個(gè)比賽的安排，使在2 n

5、1 天內(nèi)每個(gè)隊(duì)都與不同的對(duì)手比賽。例如 n=2 時(shí)的比賽安排：隊(duì)1 23 4比賽1=23=4一天1=32=4二天1=42=3三天2數(shù)制轉(zhuǎn)換（20 分）設(shè)有一個(gè)字符串A$ 的結(jié)構(gòu)為：A$= m<n>p其中 m 為數(shù)字串（長(zhǎng)度 <=20），而 n,p 均為 1 或 2 位的數(shù)字串（其中所表達(dá)的內(nèi)容在2-10之間）。程序要求：從鍵盤(pán)上讀入A$ 后（不用正確性檢查） ，將 A$ 中的數(shù)字串m(n 進(jìn)制 )，以 p進(jìn)制的形式輸出。例如： A$= 48<10>8 其意義為：將10 進(jìn)制數(shù) 48，轉(zhuǎn)換成8 進(jìn)制數(shù)輸出。輸出結(jié)果為：48<10>=60<8>

6、4挖地雷（ 30 分）在一個(gè)地圖上有 N 個(gè)地窖（ N<=20 ），每個(gè)地窖中埋有一定數(shù)量的地雷。同時(shí)，給出地窖之間的連接路徑。例如：V1V2V3V4V 5題目要求 當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后， 某人可以從任一處開(kāi)始挖地雷， 然后可以沿著指出的連接往下挖（僅能選擇一條路徑） ，當(dāng)無(wú)連接時(shí)挖地雷工作結(jié)束。設(shè)計(jì)一個(gè)挖地雷的方案，使某人能挖到最多的地雷。輸入格式：N：（表示地窖的個(gè)數(shù)）1， W2，W3， WN（表示每個(gè)地窖中埋藏的地雷數(shù)量）A12.A1N地窖之間連接路徑（其中 ij =1表示地窖 i,jA 23.A 2N之間是否有通路：通Aij=1, 不通 Aij=0 ）.A N-1N輸出格

7、式：K 1-K 2-.K V（挖地雷的順序）MAX（挖地雷的數(shù)量）例如：- - -其輸入格式為：輸出：513-4-510， 8， 4，7， 6max=2711100001114砝碼稱重（ 30 分）設(shè)有 1g、 2g、 3g、 5g、 10g、 20g 的砝碼各若干枚（其總重<=1000），要求：輸入方式： a1a2a3a4a5a6（表示 1g 砝碼有 a1 個(gè)， 2g 砝碼有 a2 個(gè)， ， 20g 砝碼有 a6 個(gè)）輸出方式： Total=N（ N 表示用這些砝碼能稱出的不同重量的個(gè)數(shù)，但不包括一個(gè)砝碼也不用的情況）如輸入： 1_1_0_0_0_0（注：下劃線表示空格）輸出： TOT

8、AL=3表示可以稱出1g， 2g， 3g 三種不同的重量。第三屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題（高中組競(jìng)賽用時(shí)： 3 小時(shí)）1在 N*N 的棋盤(pán)上（ 1 N 10），填入 1， 2， ， N*N 共 N*N 個(gè)數(shù)，使得任意兩個(gè)相鄰的數(shù)之和為素?cái)?shù)。 （ 30%）例如：當(dāng)N=2 時(shí)，有：其相鄰數(shù)的和為素?cái)?shù)的有：121+2 ，1+4 ， 4+3， 2+343當(dāng) N=4 時(shí)，一種可以填寫(xiě)的方案如下：12111216158513491467103在這里我們約定：左上角的格子里必須填數(shù)字1。程序要求：輸入： N；輸出：如有多種解，則輸出第一行、第一列之和為最小的排列方案；若無(wú)解，則輸出

9、“ NO！”。2代數(shù)表達(dá)式的定義如下：字母abc例如，下面的式子是合法的代數(shù)表達(dá)式：a；a+b*(a+c);a*a/(b+c)下面的式子是不合法的代數(shù)表達(dá)式：ab;a+a*/(b+c);程序要求：輸入：輸入一個(gè)字符串，以“； ”結(jié)束，“；”本身不是代數(shù)表達(dá)式中字符，僅作為結(jié)束）；輸出：若表達(dá)式正確，則輸出“ OK”；若表達(dá)式不正確，則輸出“ ERROR ”，及錯(cuò)誤類型。錯(cuò)誤類型約定：1式了中出現(xiàn)不允許的字符；2括號(hào)不配對(duì)；3其它錯(cuò)誤。例如：輸入：例如：輸入：a+(b);a+(b+c*a;輸出：輸出：OKERROR 23騎士游歷：設(shè)有一個(gè) n*m 的棋盤(pán)（ 2 n 50， 2m 50），如下圖，

10、在棋盤(pán)上左下角有一個(gè)中國(guó)象棋馬。（ n,m）馬(1,1)馬走的規(guī)則為：（ 1）馬走日字；（ 2）馬只能向右走即如下圖如示：任務(wù) 1：當(dāng) n,m 輸入之后，找出一條從左下角到右上角的路徑。例如，輸入：n=4， m=4(4,4)(1,1)輸出：路徑的格式：(1,1) (2,3) (4,4)。若不存在路徑，則輸出NO 任務(wù) 2：當(dāng) n， m 給出之后，同時(shí)給出馬起點(diǎn)的位置和終點(diǎn)的位置，試找出從起點(diǎn)到終點(diǎn)的所有路徑的數(shù)目。例如：（n=10,m=10 ），（1， 5）（起點(diǎn)），（3， 5）（終點(diǎn)）1098765432112345678910輸出： 2（即由（ 1，5）到（ 3， 5）共有 2 條路徑）輸

11、入格式： n,m,x1,y1,x2,y2 ( 分別表示n,m,起點(diǎn)坐標(biāo)，終點(diǎn)坐標(biāo)輸出格式：路徑數(shù)目（若不存在從起點(diǎn)到終點(diǎn)的路徑，輸出)0）第四屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題（高中組競(jìng)賽用時(shí)： 3 小時(shí)）1火車從始發(fā)站（稱為第1 站）開(kāi)出，在始發(fā)站上車的人數(shù)為a，然后到達(dá)第2 站，在第 2站有人上、下車，但上、下車的人數(shù)相同，因此在第2 站開(kāi)出時(shí)（即在到達(dá)第3 站之前）車上的人數(shù)保持為a 人。從第3 站起（包括第3 站）上、下車的人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點(diǎn)站的前一站（第n-1 站），都滿足此規(guī)律。現(xiàn)給出的條件是

12、：共有N 個(gè)車站，始發(fā)站上車的人數(shù)為 a，最后一站下車的人數(shù)是m（全部下車） 。試問(wèn) x 站開(kāi)出時(shí)車上的人數(shù)是多少？輸入： a， n， m 和 x輸出：從x 站開(kāi)出時(shí)車上的人數(shù)。20%2 設(shè)有 n 個(gè)正整數(shù)（ n 20），將它們聯(lián)接成一排，組成一個(gè)最大的多位整數(shù)。例如： n=3 時(shí)， 3個(gè)整數(shù) 13， 312， 343 聯(lián)接成的最大整數(shù)為：34331213又如： n=4 時(shí)， 4個(gè)整數(shù) 7， 13， 4，246 聯(lián)接成的最大整數(shù)為：7424613程序輸入： nn 個(gè)數(shù)程序輸出：聯(lián)接成的多位數(shù)40%3 著名科學(xué)家盧斯為了檢查學(xué)生對(duì)進(jìn)位制的理解，他給出了如下的一張加法表，表中的字母代表數(shù)字。例如：

13、40%其含義為：+LKVEL+L=L ， L+K=K ， L+V=V ， L+E=ELLKVEK+L=K ， K+K=V ， K+V=E ， K+E=KLKKVEKLE+E=KVVVEKLKKEEKLKKKV根據(jù)這些規(guī)則可推導(dǎo)出：L=0 ， K=1 ，V=2 ，E=3同時(shí)可以確定該表表示的是4 進(jìn)制加法程序輸入：n（ n 9）表示行數(shù)。以下 n 行，每行包括n 個(gè)字符串，每個(gè)字串間用空格隔開(kāi)。（字串僅有一個(gè)為+號(hào)，其它都由大寫(xiě)字母組成）程序輸出： 各個(gè)字母表示什么數(shù)，格式如：L=0 ，K=1 ， 加法運(yùn)算是幾進(jìn)制的。 若不可能組成加法表，則應(yīng)輸出“ERROR ！”第五屆全國(guó)青少年信息學(xué)（計(jì)算機(jī)

14、）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題（提高組競(jìng)賽用時(shí)： 3 小時(shí)）第一題攔截導(dǎo)彈 (28 分 )某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷： 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。 某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。 由于該系統(tǒng)還在試用階段， 所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000 的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。樣例：INPUTOUTPUT389 207 155 300 299 170 15

15、8 656（最多能攔截的導(dǎo)彈數(shù)）2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）第二題回文數(shù) (25 分 )若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。例如：給定一個(gè) 10 進(jìn)制數(shù) 56，將 56 加 65（即把 56 從右向左讀），得到 121 是一個(gè)回文數(shù)。又如：對(duì)于 10 進(jìn)制數(shù) 87：STEP1： 87+78 = 165STEP2： 165+561 = 726STEP3： 726+627 = 1353STEP4： 1353+3531 = 4884在這里的一步是指進(jìn)行了一次N 進(jìn)制的加法，上例最少用了4 步得到回文數(shù) 4884。寫(xiě)一個(gè)程序，給定一個(gè)N（ 2<=

16、N<=10或 N=16）進(jìn)制數(shù) M，求最少經(jīng)過(guò)幾步可以得到回文數(shù)。如果在 30 步以內(nèi)（包含30 步）不可能得到回文數(shù)，則輸出“Impossible！”樣例：INPUTOUTPUTN=9 M=87STEP=6第三題旅行家的預(yù)算(27分)一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位） 、每升汽油能行駛的距離 D2、出發(fā)點(diǎn)每升汽油價(jià)格 P 和沿途油站數(shù) N（ N 可以為零），油站 i 離出發(fā)點(diǎn)的距離 Di 、每升汽油價(jià)格 Pi （ i=1 ， 2， N）。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無(wú)法到達(dá)目

17、的地，則輸出“ No Solution ”。樣例：INPUTD1=275.6 C=11.9 D2=27.4P=2.8N=2油站號(hào) I離出發(fā)點(diǎn)的距離 Di每升汽油價(jià)格 Pi1102.02.92220.02.2OUTPUT26.95（該數(shù)據(jù)表示最小費(fèi)用）第四題郵票面值設(shè)計(jì)(40分)給定一個(gè)信封，最多只允許粘貼 N 張郵票，計(jì)算在給定 K（ N+K 40）種郵票的情況下（假定所有的郵票數(shù)量都足夠） ，如何設(shè)計(jì)郵票的面值，能得到最大值 MAX，使在 1 MAX之間的每一個(gè)郵資值都能得到。例如， N=3， K=2，如果面值分別為 1 分、 4 分，則在能得到（當(dāng)然還有 8 分、 9 分和 12 分）；如

18、果面值分別為的每一個(gè)郵資值都能得到?？梢则?yàn)證當(dāng) N=3，K=2 時(shí)， 7 值，所以 MAX=7，面值分別為 1 分、 3 分。1 分 6 分之間的每一個(gè)郵資值都1 分、3 分，則在1 分7 分之間分就是可以得到的連續(xù)的郵資最大樣例：INPUTOUTPUTN=3 K=21 3MAX=72000 年題一進(jìn)制轉(zhuǎn)換（ 18 分）問(wèn)題描述我們可以用這樣的方式來(lái)表示一個(gè)十進(jìn)制數(shù)：將每個(gè)阿拉伯?dāng)?shù)字乘以一個(gè)以該數(shù)字所處位置的（值減）為指數(shù)，以為底數(shù)的冪之和的形式。例如：可表示為這樣的形式。與之相似的，對(duì)二進(jìn)制數(shù)來(lái)說(shuō)，也可表示成每個(gè)二進(jìn)制數(shù)碼乘以一個(gè)以該數(shù)字所處位置的（值）為指數(shù)，以為底數(shù)的冪之和的形式。一般說(shuō)

19、來(lái)，任何一個(gè)正整數(shù)或一個(gè)負(fù)整數(shù)都可以被選來(lái)作為一個(gè)數(shù)制系統(tǒng)的基數(shù)。如果是以或?yàn)榛鶖?shù)， 則需要用到的數(shù)碼為 ，。例如，當(dāng)時(shí)，所需用到的數(shù)碼是，和，這與其是或無(wú)關(guān)。如果作為基數(shù)的數(shù)絕對(duì)值超過(guò)，則為了表示這些數(shù)碼，通常使用英文字母來(lái)表示那些大于的數(shù)碼。例如對(duì)進(jìn)制數(shù)來(lái)說(shuō)， 用表示，用表示，用表示，用表示，用表示，用表示。在負(fù)進(jìn)制數(shù)中是用作為基數(shù)， 例如 （十進(jìn)制） 相當(dāng)于 （進(jìn)制），并且它可以被表示為的冪級(jí)數(shù)的和數(shù)：（）（）（）（）（）（）問(wèn)題求解設(shè)計(jì)一個(gè)程序，讀入一個(gè)十進(jìn)制數(shù)和一個(gè)負(fù)進(jìn)制數(shù)的基數(shù), 并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)：， ，輸入輸入的每行有兩個(gè)輸入數(shù)據(jù)。第一個(gè)是十進(jìn)制數(shù)（32768

20、32767）；第二個(gè)是負(fù)進(jìn)制數(shù)的基數(shù)。輸出結(jié)果顯示在屏幕上， 相對(duì)于輸入，應(yīng)輸出此負(fù)進(jìn)制數(shù)及其基數(shù)，若此基數(shù)超過(guò)，則參照進(jìn)制的方式處理。樣例輸入輸出（）（）（）（）提高組題二乘積最大（ 22 分）問(wèn)題描述今年是國(guó)際數(shù)學(xué)聯(lián)盟確定的“ 2000世界數(shù)學(xué)年” ，又恰逢我國(guó)著名數(shù)學(xué)家華羅庚先生誕辰 90 周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場(chǎng)別開(kāi)生面的數(shù)學(xué)智力競(jìng)賽的活動(dòng)，你的一個(gè)好朋友 XZ 也有幸得以參加?；顒?dòng)中，主持人給所有參加活動(dòng)的選手出了這樣一道題目：設(shè)有一個(gè)長(zhǎng)度為 N 的數(shù)字串， 要求選手使用 K 個(gè)乘號(hào)將它分成 K+1 個(gè)部分， 找出一種分法，使得這 K+1 個(gè)部分的乘積能夠?yàn)樽畲蟆?/p>

21、同時(shí)，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個(gè)例子：有一個(gè)數(shù)字串：312， 當(dāng) N=3 ， K=1 時(shí)會(huì)有以下兩種分法：1） 3*12=362） 31*2=62這時(shí)，符合題目要求的結(jié)果是：31*2=62現(xiàn)在，請(qǐng)你幫助你的好朋友XZ 設(shè)計(jì)一個(gè)程序，求得正確的答案。輸入程序的輸入共有兩行：第一行共有2 個(gè)自然數(shù)N， K （ 6 N 40，1 K 6）第二行是一個(gè)長(zhǎng)度為N 的數(shù)字串。輸出結(jié)果顯示在屏幕上，相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)）。樣例輸入421231輸出62提高組問(wèn)題描述題三 單詞接龍（27 分）單詞接龍是一個(gè)與我們經(jīng)常玩的成語(yǔ)接龍相類似的游戲，現(xiàn)在我們已知一組單

22、詞， 且給定一個(gè)開(kāi)頭的字母，要求出以這個(gè)字母開(kāi)頭的最長(zhǎng)的“龍”（每個(gè)單詞都最多在“龍”中出現(xiàn)兩次），在兩個(gè)單詞相連時(shí)，其重合部分合為一部分，例如beast 和 astonish，如果接成一條龍則變?yōu)?beastonish，另外相鄰的兩部分不能存在包含關(guān)系，例如 at 和 atide 間不能相連。輸入輸入的第一行為一個(gè)單獨(dú)的整數(shù) n (n<=20) 表示單詞數(shù)， 以下 n 行每行有一個(gè)單詞， 輸入的最后一行為一個(gè)單個(gè)字符，表示“龍”開(kāi)頭的字母。你可以假定以此字母開(kāi)頭的“龍”一定存在 .輸出只需輸出以此字母開(kāi)頭的最長(zhǎng)的“龍”的長(zhǎng)度樣例：輸入5attouchcheatchoosetacta輸出

23、23（連成的“龍”為atoucheatactactouchoose）提高組題四方格取數(shù)（ 33 分）問(wèn)題描述設(shè)有 N*N 的方格圖 (N<=10, 我們將其中的某些方格中填入正整數(shù) ,而其他的方格中則放入數(shù)字 0。如下圖所示（見(jiàn)樣例） ：向右A 1234567810000000020013006003000070004000140000向5021000400下60015000007014000000800000000B某人從圖的左上角的A點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B點(diǎn)。在走過(guò)的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字0）。此人從 A 點(diǎn)到 B 點(diǎn)共走

24、兩次，試找出2 條這樣的路徑，使得取得的數(shù)之和為最大。輸入輸入的第一行為一個(gè)整數(shù)N（表示 N*N 的方格圖），接下來(lái)的每行有三個(gè)整數(shù)，前兩個(gè)表示位置，第三個(gè)數(shù)為該位置上所放的數(shù)。一行單獨(dú)的0 表示輸入結(jié)束。輸出只需輸出一個(gè)整數(shù)，表示2 條路徑上取得的最大的和。樣例：輸 入823132663574414522156463157214000輸出672001 年題一一元三次方程求解（ 20 分）問(wèn)題描述有形如：ax3 +bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d 均為實(shí)數(shù) )，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在 -100 至 100 之間 )，且根與根

25、之差的絕對(duì)值 >=1 。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格) ，并精確到小數(shù)點(diǎn)后 2 位。提示：記方程f(x)=0 ，若存在 2 個(gè)數(shù) x1和 x2，且 x1<x2 ， f(x1)*f(x2)<0 ，則在 (x1 ，x2)之間一定有一個(gè)根。樣例輸入： 1 -5-420輸出： -2.002.005.00題二數(shù)的劃分 (20 分 )問(wèn)題描述將整數(shù) n 分成 k 份，且每份不能為空，任意兩份不能相同( 不考慮順序) 。例如： n=7， k=3 ，下面三種分法被認(rèn)為是相同的。1，1，5; 1 ，5，1; 5 ，1，1;問(wèn)有多少種不同的分法。輸入： n， k (

26、6<n<=200 ， 2<=k<=6)輸出：一個(gè)整數(shù)，即不同的分法。樣例輸入：73輸出： 4 四種分法為：1，1， 5;1， 2， 4;1，3， 3;2， 2， 3;題三統(tǒng)計(jì)單詞個(gè)數(shù)(30分 )問(wèn)題描述給出一個(gè)長(zhǎng)度不超過(guò)200 的由小寫(xiě)英文字母組成的字母串( 約定 ; 該字串以每行20 個(gè)字母的方式輸入，且保證每行一定為20 個(gè) ) 。要求將此字母串分成k 份 (1<k<=40) ，且每份中包含的單詞個(gè)數(shù)加起來(lái)總數(shù)最大( 每份中包含的單詞可以部分重疊。當(dāng)選用一個(gè)單詞之后，其第一個(gè)字母不能再用。例如字符串this中可包含this和 is，選用this之后就不能

27、包含th)。單詞在給出的一個(gè)不超過(guò)6 個(gè)單詞的字典中。要求輸出最大的個(gè)數(shù)。輸入格式去部輸入數(shù)據(jù)放在文本文件input3.dat中，其格式如下：第一行為一個(gè)正整數(shù)(0<n<=5) 表示有 n 組測(cè)試數(shù)據(jù)每組的第一行有二個(gè)正整數(shù)(p ， k)p 表示字串的行數(shù);k 表示分為k 個(gè)部分。接下來(lái)的p 行，每行均有20 個(gè)字符。再接下來(lái)有一個(gè)正整數(shù)s ，表示字典中單詞個(gè)數(shù)。(1<=s<=6)接下來(lái)的s 行，每行均有一個(gè)單詞。輸出格式結(jié)果輸出至屏幕，每行一個(gè)整數(shù)，分別對(duì)應(yīng)每組測(cè)試數(shù)據(jù)的相應(yīng)結(jié)果。樣例輸入：11 3 thisisabookyouareaoh4is a oksab輸出：

28、/說(shuō)明： (不必輸出 )7 / this/isabookyoua/reaoh題四Car的旅行路線(30分 )問(wèn)題描述又到暑假了，住在城市A 的 Car分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，市中高速鐵路了的單位里程價(jià)格為里程的價(jià)格均為t 。圖例想和朋友一起去城市B 旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場(chǎng)，同一個(gè)城市中兩個(gè)機(jī)場(chǎng)之間有一條筆直的高速鐵路，第I個(gè)城Ti ，任意兩個(gè)不同城市的機(jī)場(chǎng)之間均有航線，所有航線單位機(jī)場(chǎng)高速鐵路飛機(jī)航線注意：圖中并沒(méi)有標(biāo)出所有的鐵路與航線。那么 Car 應(yīng)如何安排到城市B 的路線才能盡可能的節(jié)省花費(fèi)呢?她發(fā)現(xiàn)這并不是一個(gè)簡(jiǎn)單的問(wèn)題，于是她來(lái)向你請(qǐng)教。任務(wù)找出一條從城市 A 到

29、B 的旅游路線， 出發(fā)和到達(dá)城市中的機(jī)場(chǎng)可以任意選取，要求總的花費(fèi)最少。輸入文件：鍵盤(pán)輸入文件名輸 出：到屏幕 ( 輸出最小費(fèi)用，小數(shù)點(diǎn)后保留1 位。)輸入格式第一行為一個(gè)正整數(shù)n(0<=n<=10) ，表示有 n 組測(cè)試數(shù)據(jù)。每組的第一行有四個(gè)正整數(shù)s， t ， A， B。S(0<S<=100) 表示城市的個(gè)數(shù)， t表示飛機(jī)單位里程的價(jià)格，A，B 分別為城市A，B 的序號(hào)， (1<=A ，B<=S)。接下來(lái)有 S 行，其中第 I行均有7 個(gè)正整數(shù) xi1，yi1 ，xi2，yi2 ，xi3 ，yi3，Ti ，這當(dāng)中的 (xi1，yi1) ， (xi2 ，

30、yi2)， (xi3， yi3)分別是第 I 個(gè)城市中任意三個(gè)機(jī)場(chǎng)的坐標(biāo)，TI 為第 I 個(gè)城市高速鐵路單位里程的價(jià)格。輸出格式共有 n 行，每行一個(gè)數(shù)據(jù)對(duì)應(yīng)測(cè)試數(shù)據(jù)。樣例輸入11101311133130257452186881163輸出：47.552002 年題一均分紙牌 （存盤(pán)名NOIPG1 ）問(wèn)題描述 有 N 堆紙牌，編號(hào)分別為1， 2，, N。每堆上有若干張，但紙牌總數(shù)必為N 的倍數(shù)?？梢栽谌我欢焉先∪粲趶埣埮?，然后移動(dòng)。移牌規(guī)則為：在編號(hào)為1 堆上取的紙牌，只能移到編號(hào)為2 的堆上；在編號(hào)為N 的堆上取的紙牌，只能移到編號(hào)為N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆

31、上。現(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。例如 N=4 ，4 堆紙牌數(shù)分別為：98176移動(dòng) 3 次可達(dá)到目的：從 取 4 張牌放到 （981310）-> 從 取 3 張牌放到 （9111010）-> 從 取 1 張牌放到（ 10 10 10 10）。輸 入：鍵盤(pán)輸入文件名。文件格式：N（N 堆紙牌， 1 <= N <= 100 ）A1 A2An（N 堆紙牌，每堆紙牌初始數(shù)，l<= Ai <=10000 ）輸 出：輸出至屏幕。格式為：所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。輸入輸出樣例a.in：498176屏慕顯示：3題二字串變換問(wèn)題描

32、述 :（存盤(pán)名: NOIPG2）已知有兩個(gè)字串A$, B$及一組字串變換的規(guī)則（至多6 個(gè)規(guī)則）:A1$ -> B1$A2$ -> B2$規(guī)則的含義為：在A 中的子串A1$可以變換為B1$ 、 A2$例如： A$ 'abcd'B$ 'xyz'變換規(guī)則為： abc -> xu ud -> y y -> yz 可以變換為B2$ 。則此時(shí)， A$ 可以經(jīng)過(guò)一系列的變換變?yōu)锽$ ，其變換的過(guò)程為： abcd -> xud -> xy -> xyz 共進(jìn)行了三次變換，使得A$變換為B$。輸入:鍵盤(pán)輸人文件名。文件格式如下：A

33、$ B$A1$ B1$ A2$ B2$|->變換規(guī)則. . /所有字符串長(zhǎng)度的上限為20 。輸出:輸出至屏幕。格式如下：若在 10步（包含 10 步）以內(nèi)能將A$變換為B$，則輸出最少的變換步數(shù)；否則輸出"NOANSWER!"輸入輸出樣例b.in:abcd wyzabc xuud yy yz屏幕顯示：3題三自由落體 （存盤(pán)名 :NOIPG3）問(wèn)題描述 :在高為H 的天花板上有n個(gè)小球，體積不計(jì)，位置分別為0 ， 1， 2， n-1 。在地面上有一個(gè)小車（長(zhǎng)為1/2*g*(t2)，其中L ，高為g=10 ， tK ，距原點(diǎn)距離為 S1 ）。已知小球下落距離計(jì)算公式為為下

34、落時(shí)間。地面上的小車以速度 V 前進(jìn)。d 如下圖：小車與所有小球同時(shí)開(kāi)始運(yùn)動(dòng)，當(dāng)小球距小車的距離<= 0.00001時(shí)，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。請(qǐng)你計(jì)算出小車能接受到多少個(gè)小球。輸入：鍵盤(pán)輸人：H， S1， V，L， K， n （ l<=H ， S1， V， L， K， n <=100000 ）輸出：屏幕輸出：小車能接受到的小球個(gè)數(shù)。輸入輸出樣例輸入:5.0 9.0 5.0 2.5 1.8 5輸出:1題四矩形覆蓋 （存盤(pán)名NOIPG4）問(wèn)題描述 :在平面上有n個(gè)點(diǎn)（ n <= 50 ），每個(gè)點(diǎn)用一對(duì)整數(shù)坐標(biāo)表示。例如：當(dāng)n 4 時(shí)， 4 個(gè)點(diǎn)的

35、坐標(biāo)分另為：p1（ 1， 1）， p2（ 2， 2）， p3（ 3， 6）， P4（ 0， 7），見(jiàn)圖一。這些點(diǎn)可以用k個(gè)矩形（ 1<=k<=4 ）全部覆蓋，矩形的邊平行于坐標(biāo)軸。當(dāng)k=2時(shí)，可用如圖二的兩個(gè)矩形sl， s2 覆蓋， s1， s2 面積和為4 。問(wèn)題是當(dāng)n個(gè)點(diǎn)坐標(biāo)和k給出后，怎樣才能使得覆蓋所有點(diǎn)的k個(gè)矩形的面積之和為最小呢。約定：覆蓋一個(gè)點(diǎn)的矩形面積為0 ；覆蓋平行于坐標(biāo)軸直線上點(diǎn)的矩形面積也為0。各個(gè)矩形必須完全分開(kāi)（邊線與頂點(diǎn)也都不能重合）。輸入:鍵盤(pán)輸人文件名。文件格式為n kxl y1x2 y2. .xn yn （ 0<=xi,yi<=500)

36、輸出:輸出至屏幕。格式為：一個(gè)整數(shù)，即滿足條件的最小的矩形面積之和。輸入輸出樣例d.in :4 21 12 23 60 7屏幕顯示：42003 年第九屆全國(guó)青少年信息 學(xué)奧 林匹克 聯(lián)賽（ N0IP2003）2003 年 11 月 29 日提高組試題三小時(shí)完成試題輸入：蘇州高斌大榕樹(shù)題一神經(jīng)網(wǎng)絡(luò)【問(wèn)題背景】人工神經(jīng)網(wǎng)絡(luò) （ Artificial Neural Network）是一種新興的具有自我學(xué)習(xí)能力的計(jì)算系統(tǒng)，在模式識(shí)別、 函數(shù)逼近及貸款風(fēng)險(xiǎn)評(píng)估等諸多領(lǐng)域有廣泛的應(yīng)用。對(duì)神經(jīng)網(wǎng)絡(luò)的研究一直是當(dāng)今的熱門(mén)方向， 蘭蘭同學(xué)在自學(xué)了一本神經(jīng)網(wǎng)絡(luò)的入門(mén)書(shū)籍后， 提出了一個(gè)簡(jiǎn)化模型， 他希望你能幫助他

37、用程序檢驗(yàn)這個(gè)神經(jīng)網(wǎng)絡(luò)模型的實(shí)用性?！締?wèn)題描述】在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下圖是一個(gè)神經(jīng)元的例子：神經(jīng)元編號(hào)為1）圖中，X1 X3 是信息輸入渠道， Y1 Y2 是信息輸出渠道， C1 表示神經(jīng)元目前的狀態(tài)， Ui 是閾值，可視為神經(jīng)元的一個(gè)內(nèi)在參數(shù)。神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無(wú)分為幾層；稱為輸入層、輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。下圖是一個(gè)簡(jiǎn)單的三層神經(jīng)網(wǎng)絡(luò)的例子。蘭蘭規(guī)定， Ci 服從公式：（其中 n 是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）CiW ji C j