1、 1 / 56NOI95 “同創(chuàng)杯同創(chuàng)杯”全國青少年信息學(xué)（計算機）奧林匹克競賽全國青少年信息學(xué)（計算機）奧林匹克競賽分區(qū)聯(lián)賽復(fù)賽試題（高中組）分區(qū)聯(lián)賽復(fù)賽試題（高中組） （上機編程，完成時間：（上機編程，完成時間：210 分鐘）分鐘） 編碼問題：編碼問題： 設(shè)有一個數(shù)組 A:ARRAY0.N-1 OF INTEGER； 數(shù)組中存放的元素為 0N-1 之間的整數(shù)，且 AiAj（當(dāng) ij 時） 。 例如：N=6 時，有： A=（4，3，0，5，1，2） 此時，數(shù)組 A 的編碼定義如下： A0的編碼為 0； Ai的編碼為：在 A0，A1，Ai-1中比 Ai的值小的個數(shù)（i=1，2，N-1） 上面數(shù)

2、組 A 的編碼為： B=（0，0，0，3，1，2） 程序要求解決以下問題：程序要求解決以下問題：給出數(shù)組 A 后，求出其編碼。給出數(shù)組 A 的編碼后，求出 A 中的原數(shù)據(jù)。 燈的排列問題：燈的排列問題： 設(shè)在一排上有 N 個格子（N20） ，若在格子中放置有不同顏色的燈，每種燈的個數(shù)記為 N1，N2，Nk（k 表示不同顏色燈的個數(shù)） 。 放燈時要遵守下列規(guī)則：放燈時要遵守下列規(guī)則：同一種顏色的燈不能分開；不同顏色的燈之間至少要有一個空位置。 例如：N=8（格子數(shù)） R=2（紅燈數(shù)） B=3（藍(lán)燈數(shù)） 放置的方法有： R-B 順序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB 2

3、/ 56 B-R 順序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR 放置的總數(shù)為 12 種。 數(shù)據(jù)輸入的方式為：NP1（顏色，為一個字母） N1（燈的數(shù)量）P2 N2 Q（結(jié)束標(biāo)記，Q 本身不是燈的顏色） 程序要求：求出一種順序的排列方案及排列總數(shù)。程序要求：求出一種順序的排列方案及排列總數(shù)。 設(shè)有一個四層的積木塊，14 層積木塊的數(shù)量依次為：5，6，7，8 如下圖所示放置：815851691423414326 其中，給出第三層與第四層所標(biāo)示的數(shù)字，并已知第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)計算出來的。 計算的方法是：第三層的某個數(shù)據(jù) A 是由第四層相鄰的兩個數(shù)據(jù) B，C 經(jīng)過某種計算

4、后產(chǎn)生的：ABC 計算所用到的計算符為：+，-，且無優(yōu)先級之分（自左向右計算） ，運算符最多為2 個。 如：3+45=35 54+3=23 可以看出，上圖中的第三層的數(shù)據(jù)是由第四層的數(shù)據(jù)用以下計算公式計算出來的：A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求：程序要求： 給出第四層與第三層的數(shù)據(jù)后，將第一、二層的每塊積木標(biāo)上相應(yīng)的數(shù)據(jù)，并輸出整個完整的積木圖及計算公式。 3 / 56 輸入數(shù)據(jù)不存在出錯的情況，同時也不會超過整數(shù)的范圍。 計算時可允許出現(xiàn)以下情況： A=B （即可理解為運算符的個數(shù)為零） A=BB+B （即全部由 B 產(chǎn)生）第二屆全國青少年信息學(xué)（

5、計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第二屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時）1比賽安排（20 分） 設(shè)有有 2 n（n=6）個球隊進(jìn)行單循環(huán)比賽，計劃在 2 n 1 天內(nèi)完成，每個隊每天進(jìn)行一場比賽。設(shè)計一個比賽的安排，使在 2 n 1 天內(nèi)每個隊都與不同的對手比賽。例如 n=2 時的比賽安排： 隊 1 23 4 比賽 1=23=4 一天 1=32=4 二天 1=4 2=3 三天2數(shù)制轉(zhuǎn)換（20 分） 設(shè)有一個字符串 A$的結(jié)構(gòu)為： A$=mp 其中 m 為數(shù)字串（長度=20） ，而 n,p 均為 1 或 2 位的數(shù)字串（其中

6、所表達(dá)的內(nèi)容在2-10 之間） 。 程序要求：從鍵盤上讀入 A$后（不用正確性檢查） ，將 A$中的數(shù)字串 m(n 進(jìn)制)，以p 進(jìn)制的形式輸出。 例如：A$=488 其意義為：將 10 進(jìn)制數(shù) 48，轉(zhuǎn)換成 8 進(jìn)制數(shù)輸出。 輸出結(jié)果為：48=604挖地雷（30 分） 在一個地圖上有 N 個地窖（N=20） ，每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接路徑。例如：題目要求當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后，某人可以從任一處開始挖地雷，然后可以沿著指出的連接往下挖（僅能選擇一條路徑） ，當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖地雷的方案，使某人能挖到最多的地雷。 輸入格式： N： （表示地窖

7、的個數(shù)）V1 V 2 V3 V4 V5 4 / 56 1，W2，W3，WN （表示每個地窖中埋藏的地雷數(shù)量） A12 . A1N A23.A2N . AN-1 N 輸出格式： K1-K2-.KV （挖地雷的順序） MAX （挖地雷的數(shù)量）例如： - -其輸入格式為： 輸出： 51 3 -4 -510，8，4，7，6max=27 1 1 1 0 0 0 0 1 1 14砝碼稱重（30 分）設(shè)有 1g、2g、3g、5g、10g、20g 的砝碼各若干枚（其總重=1000） ，要求： 輸入方式：a1 a2 a3 a4 a5 a6 （表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，20g 砝碼有

8、a6 個） 輸出方式：Total=N （N 表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況）如輸入：1_1_0_0_0_0 （注：下劃線表示空格） 輸出：TOTAL=3 表示可以稱出 1g，2g，3g 三種不同的重量。第三屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第三屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時）1在 N*N 的棋盤上（1N10） ，填入 1，2，N*N 共 N*N 個數(shù)，使得任意兩個相鄰的數(shù)之和為素數(shù)。 （30%） 例如：當(dāng) N=2 時，有：1243地窖之間連接路徑（其中ij=1 表示

9、地窖 i,j之間是否有通路：通 Aij=1,不通 Aij=0）其相鄰數(shù)的和為素數(shù)的有：1+2，1+4，4+3，2+3 5 / 56 當(dāng) N=4 時，一種可以填寫的方案如下： 12111216158513491467103 在這里我們約定：左上角的格子里必須填數(shù)字 1。 程序要求： 輸入：N； 輸出：如有多種解，則輸出第一行、第一列之和為最小的排列方案；若無解，則輸出“NO！” 。2代數(shù)表達(dá)式的定義如下： 例如，下面的式子是合法的代數(shù)表達(dá)式： a； a+b*(a+c); a*a/(b+c) 下面的式子是不合法的代數(shù)表達(dá)式：ab; a+a*/(b+c); 程序要求： 輸入：輸入一個字符串，以“；”

10、結(jié)束， “；”本身不是代數(shù)表達(dá)式中字符，僅作為結(jié)束） ； 輸出：若表達(dá)式正確，則輸出“OK” ；若表達(dá)式不正確，則輸出“ERROR” ，及錯誤類型。錯誤類型約定：1式了中出現(xiàn)不允許的字符；2括號不配對；3其它錯誤。acb字母 6 / 56 例如：輸入：a+(b); 輸出：OK 例如：輸入：a+(b+c*a; 輸出：ERROR 23騎士游歷： 設(shè)有一個 n*m 的棋盤（2n50，2m50） ，如下圖，在棋盤上左下角有一個中國象棋馬。 （n,m） (1,1)馬走的規(guī)則為：（1）馬走日字；（2）馬只能向右走即如下圖如示： 任務(wù) 1：當(dāng) n,m 輸入之后，找出一條從左下角到右上角的路徑。 例如，輸入：

11、n=4，m=4 輸出：路徑的格式：(1,1)(2,3)(4,4)。若不存在路徑，則輸出NO 任務(wù) 2：當(dāng) n，m 給出之后，同時給出馬起點的位置和終點的位置，試找出從起點到終點的所有路徑的數(shù)目。 例如：（n=10,m=10） ， （1，5） （起點） ， （3，5） （終點） 輸 出：2（即由（1，5）到（3，5）共有 2 條路徑） 輸入格式：n,m,x1,y1,x2,y2 (分別表示 n,m,起點坐標(biāo)，終點坐標(biāo))馬(4,4)(1,1)109876543211 2 3 4 5 6 7 8 9 10 7 / 56 輸出格式：路徑數(shù)目（若不存在從起點到終點的路徑，輸出 0）第四屆全國青少年信息學(xué)（

12、計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第四屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題 （高中組（高中組 競賽用時：競賽用時：3 小時）小時）1火車從始發(fā)站（稱為第 1 站）開出，在始發(fā)站上車的人數(shù)為 a，然后到達(dá)第 2 站，在第2 站有人上、下車，但上、下車的人數(shù)相同，因此在第 2 站開出時（即在到達(dá)第 3 站之前）車上的人數(shù)保持為 a 人。從第 3 站起（包括第 3 站）上、下車的人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點站的前一站（第 n-1 站） ，都滿足此規(guī)律?，F(xiàn)給出的條件是：共有 N 個車站，始發(fā)站上車的人數(shù)為 a，最后一站下車的人

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

14、L=K，K+K=V，K+V=E，K+E=KL E+E=KV 根據(jù)這些規(guī)則可推導(dǎo)出：L=0，K=1，V=2，E=3 同時可以確定該表表示的是 4 進(jìn)制加法程序輸入： n（n9）表示行數(shù)。以下 n 行，每行包括 n 個字符串，每個字串間用空格隔開。 （字串僅有一個為+號，+LKVELLKVEKKVEKLVVEKLKKEEKLKK KV 8 / 56其它都由大寫字母組成）程序輸出： 各個字母表示什么數(shù)，格式如：L=0，K=1， 加法運算是幾進(jìn)制的。 若不可能組成加法表，則應(yīng)輸出“ERROR！”第五屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽試題第五屆全國青少年信息學(xué)（計算機）奧林匹克分區(qū)聯(lián)賽復(fù)賽

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

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

17、例最少用了 4 步得到回文數(shù) 4884。 寫一個程序，給定一個 N（2=N=10 或 N=16）進(jìn)制數(shù) M，求最少經(jīng)過幾步可以得到回文數(shù)。 9 / 56 如果在 30 步以內(nèi)（包含 30 步）不可能得到回文數(shù)，則輸出“Impossible！” 樣例： INPUT OUTPUT N = 9 M= 87 STEP=6第三題第三題 旅行家的預(yù)算旅行家的預(yù)算(27(27 分分) ) 一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是空的） 。給定兩個城市之間的距離 D1、汽車油箱的容量 C（以升為單位） 、每升汽油能行駛的距離 D2、出發(fā)點每升汽油價格 P 和沿途油站數(shù) N（N

18、可以為零） ，油站 i 離出發(fā)點的距離Di、每升汽油價格 Pi（i=1，2，N） 。計算結(jié)果四舍五入至小數(shù)點后兩位。如果無法到達(dá)目的地，則輸出“No Solution” 。 樣例： INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站號 I離出發(fā)點的距離 Di每升汽油價格 Pi1102.02.92220.02.2 OUTPUT26.95（該數(shù)據(jù)表示最小費用）第四題第四題 郵票面值設(shè)計郵票面值設(shè)計(40(40 分分) )給定一個信封，最多只允許粘貼 N 張郵票，計算在給定 K（N+K40）種郵票的情況下（假定所有的郵票數(shù)量都足夠） ，如何設(shè)計郵票的面值，能得到最大值

19、 MAX，使在 1MAX之間的每一個郵資值都能得到。 例如，N=3，K=2，如果面值分別為 1 分、4 分，則在 1 分6 分之間的每一個郵資值都能得到（當(dāng)然還有 8 分、9 分和 12 分） ；如果面值分別為 1 分、3 分，則在 1 分7 分之間的每一個郵資值都能得到?？梢则炞C當(dāng) N=3，K=2 時，7 分就是可以得到的連續(xù)的郵資最大值，所以 MAX=7，面值分別為 1 分、3 分。 樣例： INPUT OUTPUT N=3 K=2 1 3 MAX=7 10 / 562000 年年 題一題一 進(jìn)制轉(zhuǎn)換進(jìn)制轉(zhuǎn)換 （18 分）分） 問題描述問題描述 我們可以用這樣的方式來表示一個十進(jìn)制數(shù)： 將

20、每個阿拉伯?dāng)?shù)字乘以一個以該數(shù)字所處位置的（值減）為指數(shù)，以為底數(shù)的冪之和的形式。例如：可表示為 這樣的形式。 與之相似的，對二進(jìn)制數(shù)來說，也可表示成每個二進(jìn)制數(shù)碼乘以一個以該數(shù)字所處位置的（值）為指數(shù)，以為底數(shù)的冪之和的形式。一般說來，任何一個正整數(shù)或一個負(fù)整數(shù)都可以被選來作為一個數(shù)制系統(tǒng)的基數(shù)。如果是以或為基數(shù)，則需要用到的數(shù)碼為 ， 。例如，當(dāng)時，所需用到的數(shù)碼是，和，這與其是或無關(guān)。如果作為基數(shù)的數(shù)絕對值超過，則為了表示這些數(shù)碼，通常使用英文字母來表示那些大于的數(shù)碼。例如對進(jìn)制數(shù)來說，用表示，用表示，用表示，用表示，用表示，用表示。在負(fù)進(jìn)制數(shù)中是用 作為基數(shù)，例如（十進(jìn)制）相當(dāng)于（進(jìn)制）

21、，并且它可以被表示為的冪級數(shù)的和數(shù)： （）（）（）（） （） （） 問題求解問題求解 設(shè)計一個程序，讀入一個十進(jìn)制數(shù)和一個負(fù)進(jìn)制數(shù)的基數(shù), 并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)進(jìn)制下的數(shù)： ， ， 輸輸 入入 輸入的每行有兩個輸入數(shù)據(jù)。 第一個是十進(jìn)制數(shù)（3276832767） ； 第二個是負(fù)進(jìn)制數(shù)的基數(shù)。 輸輸 出出 結(jié)果顯示在屏幕上，相對于輸入，應(yīng)輸出此負(fù)進(jìn)制數(shù)及其基數(shù)，若此基數(shù)超過，則參照進(jìn)制的方式處理。 樣樣 例例 輸入 11 / 56輸出（）（）（）（） 提高組 題二題二 乘積最大乘積最大 （22 分）分） 問題描述問題描述 今年是國際數(shù)學(xué)聯(lián)盟確定的“2000世界數(shù)學(xué)年” ，又恰逢我國著名數(shù)學(xué)家

22、華羅庚先生誕辰 90 周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學(xué)智力競賽的活動，你的一個好朋友 XZ 也有幸得以參加?；顒又?，主持人給所有參加活動的選手出了這樣一道題目：設(shè)有一個長度為 N 的數(shù)字串，要求選手使用 K 個乘號將它分成 K+1 個部分，找出一種分法，使得這 K+1 個部分的乘積能夠為最大。同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：有一個數(shù)字串：312， 當(dāng) N=3，K=1 時會有以下兩種分法：1） 3*12=362） 31*2=62 這時，符合題目要求的結(jié)果是：31*2=62 現(xiàn)在，請你幫助你的好朋友 XZ 設(shè)計一個程序，求得正確的答案。 輸

23、輸 入入 程序的輸入共有兩行： 第一行共有 2 個自然數(shù) N，K（6N40，1K6） 第二行是一個長度為 N 的數(shù)字串。 輸輸 出出 結(jié)果顯示在屏幕上，相對于輸入，應(yīng)輸出所求得的最大乘積（一個自然數(shù)） 。 樣樣 例例 12 / 56輸入4 21231輸出62提高組 題三題三 單詞接龍單詞接龍 （27 分）分） 問題描述問題描述 單詞接龍是一個與我們經(jīng)常玩的成語接龍相類似的游戲，現(xiàn)在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍” （每個單詞都最多在“龍”中出現(xiàn)兩次） ，在兩個單詞相連時，其重合部分合為一部分，例如 beast 和 astonish，如果接成一條龍則變?yōu)?/p>

24、 beastonish，另外相鄰的兩部分不能存在包含關(guān)系，例如 at 和 atide 間不能相連。 輸輸 入入 輸入的第一行為一個單獨的整數(shù) n (n=20)表示單詞數(shù)，以下 n 行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在. 輸輸 出出 只需輸出以此字母開頭的最長的“龍”的長度 樣樣 例例 ： 輸入5attouchcheatchoosetacta輸出23 （連成的“龍”為 atoucheatactactouchoose） 13 / 56 14 / 56 提高組 題四題四 方格取數(shù)方格取數(shù) （33 分）分） 問題描述問題描述 設(shè)有

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

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

27、中。要求輸出最大的個數(shù)。輸入格式輸入格式去部輸入數(shù)據(jù)放在文本文件 input3.dat 中，其格式如下：第一行為一個正整數(shù)(0n=5)表示有 n 組測試數(shù)據(jù)每組的第一行有二個正整數(shù)(p，k)p 表示字串的行數(shù);k 表示分為 k 個部分。接下來的 p 行，每行均有 20 個字符。再接下來有一個正整數(shù) s，表示字典中單詞個數(shù)。(1=s=6)接下來的 s 行，每行均有一個單詞。輸出格式輸出格式結(jié)果輸出至屏幕，每行一個整數(shù)，分別對應(yīng)每組測試數(shù)據(jù)的相應(yīng)結(jié)果。樣例樣例輸入： 11 3thisisabookyouareaoh4isaoksab輸出： /說明：(不必輸出)7 / this/isabookyou

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

29、路線，出發(fā)和到達(dá)城市中的機場可以任意選取，要求總的花費最少。輸入文件：鍵盤輸入文件名輸 出：到屏幕(輸出最小費用，小數(shù)點后保留 1 位。)輸入格式輸入格式第一行為一個正整數(shù) n(0=n=10)，表示有 n 組測試數(shù)據(jù)。每組的第一行有四個正整數(shù) s，t，A，B。S(0S=100)表示城市的個數(shù)，t 表示飛機單位里程的價格，A，B 分別為城市 A，B 的序號，(1=A，B 從 取 3 張牌放到 （9 11 10 10）- 從 取 1 張牌放到（10 10 10 10） 。輸輸 入入：鍵盤輸入文件名。文件格式：N（N 堆紙牌，1 = N = 100）A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l

30、= Ai B1$A2$ - B2$規(guī)則的含義為：在 A中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ 。例如：A$abcdB$xyz變換規(guī)則為：abc-xuud-yy-yz則此時，A$ 可以經(jīng)過一系列的變換變?yōu)?B$，其變換的過程為：abcd-xud-xy-xyz共進(jìn)行了三次變換，使得 A$ 變換為 B$。 輸入輸入 :鍵盤輸人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 變換規(guī)則. . / 所有字符串長度的上限為 20。 輸出輸出 :輸出至屏幕。格式如下：若在 10 步（包含 10 步）以內(nèi)能將 A$ 變換為 B$ ，則輸出最少的變換步數(shù)；否則輸出N

31、O ANSWER!輸入輸出樣例輸入輸出樣例b.in:abcd wyzabc xuud yy yz屏幕顯示：3 題三 自由落體（存盤名:NOIPG3） 問題描述問題描述 :在高為 H 的天花板上有 n 個小球，體積不計，位置分別為 0，1，2，n-1。在地面上 20 / 56有一個小車（長為 L，高為 K，距原點距離為 S1）。已知小球下落距離計算公式為 d1/2*g*(t2)，其中 g=10，t 為下落時間。地面上的小車以速度 V 前進(jìn)。如下圖：小車與所有小球同時開始運動，當(dāng)小球距小車的距離 = 0.00001 時，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。請你計算出小車能接受到多少個

32、小球。 輸入輸入 ：鍵盤輸人：H，S1，V，L，K，n （l=H，S1，V，L，K，n =100000） 輸出輸出 ：屏幕輸出：小車能接受到的小球個數(shù)。輸入輸出樣例輸入輸出樣例輸入:5.0 9.0 5.0 2.5 1.8 5輸出:1題四 矩形覆蓋（存盤名 NOIPG4） 問題描述問題描述 :在平面上有 n 個點（n = 50），每個點用一對整數(shù)坐標(biāo)表示。例如：當(dāng) n4 時，4 個點的坐標(biāo)分另為：p1（1，1），p2（2，2），p3（3，6），P4（0，7），見圖一。 21 / 56這些點可以用 k 個矩形（1=k=4）全部覆蓋，矩形的邊平行于坐標(biāo)軸。當(dāng) k=2 時，可用如圖二的兩個矩形 sl，

33、s2 覆蓋，s1，s2 面積和為 4。問題是當(dāng) n 個點坐標(biāo)和 k 給出后，怎樣才能使得覆蓋所有點的 k 個矩形的面積之和為最小呢。約定：覆蓋一個點的矩形面積為 0；覆蓋平行于坐標(biāo)軸直線上點的矩形面積也為 0。各個矩形必須完全分開（邊線與頂點也都不能重合）。 輸入輸入 :鍵盤輸人文件名。文件格式為n kxl y1x2 y2. .xn yn （0=xi,yi=500) 輸出輸出 :輸出至屏幕。格式為：一個整數(shù)，即滿足條件的最小的矩形面積之和。 輸入輸出樣例輸入輸出樣例d.in :4 21 12 23 60 7屏幕顯示：42003 年 22 / 56第九第九屆屆全全國青國青少年信息少年信息學(xué)奧學(xué)奧

34、林匹克林匹克聯(lián)賽聯(lián)賽（N0IP2003N0IP2003）2003 年 11 月 29 日 提高組試題 三小時完成試題輸入：蘇州高斌大榕樹 http:/題一題一 神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)【問題背景】 人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network）是一種新興的具有自我學(xué)習(xí)能力的計算系統(tǒng)，在模式識別、函數(shù)逼近及貸款風(fēng)險評估等諸多領(lǐng)域有廣泛的應(yīng)用。對神經(jīng)網(wǎng)絡(luò)的研究一直是當(dāng)今的熱門方向，蘭蘭同學(xué)在自學(xué)了一本神經(jīng)網(wǎng)絡(luò)的入門書籍后，提出了一個簡化模型，他希望你能幫助他用程序檢驗這個神經(jīng)網(wǎng)絡(luò)模型的實用性。【問題描述】 在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點稱為神經(jīng)元，而且兩個神經(jīng)元之間

35、至多有一條邊相連，下圖是一個神經(jīng)元的例子： 神經(jīng)元編號為 1） 圖中，X1X3 是信息輸入渠道，Y1Y2 是信息輸出渠道，C1 表示神經(jīng)元目前的狀態(tài)，Ui 是閾值，可視為神經(jīng)元的一個內(nèi)在參數(shù)。 神經(jīng)元按一定的順序排列，構(gòu)成整個神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。下圖是一個簡單的三層神經(jīng)網(wǎng)絡(luò)的例子。蘭蘭規(guī)定，Ci服從公式：（其中 n 是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目） 23 / 56 公式中的 Wji（可能為負(fù)值）表示連接 j 號神經(jīng)元和 i 號神經(jīng)元的邊的權(quán)值。當(dāng) Ci 大于 0 時

36、，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時，下一秒它會向其他神經(jīng)元傳送信號，信號的強度為 Ci。 如此在輸入層神經(jīng)元被激發(fā)之后，整個網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿酉逻M(jìn)行運作?，F(xiàn)在，給定一個神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（Ci） ，要求你的程序運算出最后網(wǎng)絡(luò)輸出層的狀態(tài)?！据斎敫袷健枯斎胛募谝恍惺莾蓚€整數(shù) n（1n20）和 p。接下來 n 行，每行兩個整數(shù)，第 i1行是神經(jīng)元 i 最初狀態(tài)和其閾值（Ui） ，非輸入層的神經(jīng)元開始時狀態(tài)必然為 0。再下面 P行，每行由兩個整數(shù) i，j 及一個整數(shù) Wij，表示連接神經(jīng)元 i、j 的邊權(quán)值為 Wij?！据敵龈袷健?輸出文件包

37、含若干行，每行有兩個整數(shù)，分別對應(yīng)一個神經(jīng)元的編號，及其最后的狀態(tài)，兩個整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號由小到大順序輸出！ 若輸出層的神經(jīng)元最后狀態(tài)均為 0，則輸出 NULL?！据斎霕永? 61 01 00 10 10 11 3 11 4 11 5 12 3 12 4 12 5 1【輸出樣例】3 14 15 1題二題二 偵探推理偵探推理【問題描述】E) i , j (ijjiiUCWC 24 / 56明明同學(xué)最近迷上了偵探漫畫柯南并沉醉于推理游戲之中，于是他召集了一群同學(xué)玩推理游戲。游戲的內(nèi)容是這樣的，明明的同學(xué)們先商量好由其中的一個人充當(dāng)罪犯（在明明不知

38、情的情況下） ，明明的任務(wù)就是找出這個罪犯。接著，明明逐個詢問每一個同學(xué)，被詢問者可能會說：證詞中出現(xiàn)的其他話，都不列入邏輯推理的內(nèi)容。明明所知道的是，他的同學(xué)中有 N 個人始終說假話，其余的人始終說真?，F(xiàn)在，明明需要你幫助他從他同學(xué)的話中推斷出誰是真正的兇手，請記住，兇手只有一個！【輸入格式】 輸入由若干行組成，第一行有二個整數(shù)，M（1M20） 、N（1NM）和P（1P100） ；M 是參加游戲的明明的同學(xué)數(shù)，N 是其中始終說謊的人數(shù)，P 是證言的總數(shù)。接下來 M 行，每行是明明的一個同學(xué)的名字（英文字母組成，沒有主格，全部大寫） 。往后有 P 行，每行開始是某個同學(xué)的名宇，緊跟著一個冒號和

39、一個空格，后面是一句證詞，符合前表中所列格式。證詞每行不會超過 250 個字符。 輸入中不會出現(xiàn)連續(xù)的兩個空格，而且每行開頭和結(jié)尾也沒有空格?！据敵龈袷健?如果你的程序能確定誰是罪犯，則輸出他的名字；如果程序判斷出不止一個人可能是罪犯，則輸出 Cannot Determine；如果程序判斷出沒有人可能成為罪犯，則輸出 Impossible?！据斎霕永? 1 5MIKECHARLESKATEMIKE:I am guilty.MIKE:Today is Sunday.CHARLES:MIKE is guiltyKATE:I am guilty.KATE:How are you?【輸出樣例】MIK

40、E 25 / 56題三題三 加分二叉樹加分二叉樹【問題描述】 設(shè)一個 n 個節(jié)點的二叉樹 tree 的中序遍歷為（l,2,3,n） ，其中數(shù)字 1,2,3,n 為節(jié)點編號。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)） ，記第 j 個節(jié)點的分?jǐn)?shù)為 di，tree 及它的每個子樹都有一個加分，任一棵子樹 subtree（也包含 tree 本身）的加分計算方法如下： subtree 的左子樹的加分 subtree 的右子樹的加分subtree 的根的分?jǐn)?shù) 若某個子樹為主，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹 tree。

41、要求輸出； （1）tree 的最高加分 （2）tree 的前序遍歷【輸入格式】 第 1 行：一個整數(shù) n（n30） ，為節(jié)點個數(shù)。 第 2 行：n 個用空格隔開的整數(shù)，為每個節(jié)點的分?jǐn)?shù)（分?jǐn)?shù)100） ?！据敵龈袷健?第 1 行：一個整數(shù)，為最高加分（結(jié)果不會超過 4,000,000,000） 。 第 2 行：n 個用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?5 5 7 1 2 10【輸出樣例】 145 3 1 2 4 5題四題四 傳染病控制傳染病控制 【問題背景】 近來，一種新的傳染病肆虐全球。蓬萊國也發(fā)現(xiàn)了零星感染者，為防止該病在蓬萊國大范圍流行，該國政府決定不惜一切代價控制傳染病的蔓

42、延。不幸的是，由于人們尚未完全認(rèn)識這種傳染病，難以準(zhǔn)確判別病毒攜帶者，更沒有研制出疫苗以保護(hù)易感人群。于是，蓬萊國的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播。經(jīng)過 WHO（世界衛(wèi)生組織）以及全球各國科研部門的努力，這種新興傳染病的傳播途徑和控制方法已經(jīng)研究消楚，剩下的任務(wù)就是由你協(xié)助蓬萊國疾控中心制定一個有效的控制辦法。 26 / 56 【問題描述】 研究表明，這種傳染病的傳播具有兩種很特殊的性質(zhì)； 第一是它的傳播途徑是樹型的，一個人 X 只可能被某個特定的人 Y 感染，只要 Y 不得病，或者是 XY 之間的傳播途徑被切斷，則 X 就不會得病。 第二是，這種疾病的傳播有周期性，在一個

43、疾病傳播周期之內(nèi)，傳染病將只會感染一代患者，而不會再傳播給下一代。 這些性質(zhì)大大減輕了蓬萊國疾病防控的壓力，并且他們已經(jīng)得到了國內(nèi)部分易感人群的潛在傳播途徑圖（一棵樹） 。但是，麻煩還沒有結(jié)束。由于蓬萊國疾控中心人手不夠，同時也缺乏強大的技術(shù)，以致他們在一個疾病傳播周期內(nèi)，只能設(shè)法切斷一條傳播途徑，而沒有被控制的傳播途徑就會引起更多的易感人群被感染（也就是與當(dāng)前已經(jīng)被感染的人有傳播途徑相連，且連接途徑?jīng)]有被切斷的人群） 。當(dāng)不可能有健康人被感染時，疾病就中止傳播。所以，蓬萊國疾控中心要制定出一個切斷傳播途徑的順序，以使盡量少的人被感染。你的程序要針對給定的樹，找出合適的切斷順序。【輸入格式】

44、輸入格式的第一行是兩個整數(shù) n（1n300）和 p。接下來 p 行，每一行有兩個整數(shù) i和 j，表示節(jié)點 i 和 j 間有邊相連（意即，第 i 人和第 j 人之間有傳播途徑相連） 。其中節(jié)點1 是已經(jīng)被感染的患者。【輸出格式】 只有一行，輸出總共被感染的人數(shù)?！据斎霕永?7 6 1 2 1 3 2 4 2 5 3 6 3 7【輸出樣例】 32004 年第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題第十屆全國青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題 ( (提高組提高組 3 3 小時完成小時完成) ) http:/ 27 / 56一、津津的儲蓄計劃一、津津的儲蓄計劃 (Save.pasdprccpp) 【問

45、題描述】 津津的零花錢一直都是自己管理。每個月的月初媽媽給津津 300 元錢，津津會預(yù)算這個月的花銷，并且總能做到實際花銷和預(yù)算的相同。 為了讓津津?qū)W習(xí)如何儲蓄，媽媽提出，津津可以隨時把整百的錢存在她那里，到了年末她會加上 20還給津津。因此津津制定了一個儲蓄計劃：每個月的月初，在得到媽媽給的零花錢后，如果她預(yù)計到這個月的月末手中還會有多于 100 元或恰好 100 元，她就會把整百的錢存在媽媽那里，剩余的錢留在自己手中。 例如 11 月初津津手中還有 83 元，媽媽給了津津 300 元。津津預(yù)計 11 月的花銷是 180 元，那么她就會在媽媽那里存 200 元，自己留下 183 元。到了 1

46、1 月月末，津津手中會剩下 3 元錢。 津津發(fā)現(xiàn)這個儲蓄計劃的主要風(fēng)險是，存在媽媽那里的錢在年末之前不能取出。有可能在某個月的月初，津津手中的錢加上這個月媽媽給的錢，不夠這個月的原定預(yù)算。如果出現(xiàn)這種情況，津津?qū)⒉坏貌辉谶@個月省吃儉用，壓縮預(yù)算。 現(xiàn)在請你根據(jù) 2004 年 1 月到 12 月每個月津津的預(yù)算，判斷會不會出現(xiàn)這種情況。如果不會，計算到 2004 年年末，媽媽將津津平常存的錢加上 20還給津津之后，津津手中會有多少錢。 【輸入文件】 輸入文件 save.in 包括 12 行數(shù)據(jù)，每行包含一個小于 350 的非負(fù)整數(shù)，分別表示 1 月到 12 月津津的預(yù)算。 【輸出文件】 輸出文件

47、 save.out 包括一行，這一行只包含一個整數(shù)。如果儲蓄計劃實施過程中出現(xiàn)某個月錢不夠用的情況，輸出-X，X 表示出現(xiàn)這種情況的第一個月；否則輸出到 2004 年年末津津手中會有多少錢。 【樣例輸入 1】 290230 28 / 5628020030017034050 90 80 20060 【樣例輸出 1】 -7 【樣例輸入 2】 290 230 280 200 300 170 330 50 90 80 200 60 【樣例輸出 2】 1580 二、合并果子二、合并果子 (fruit.pasdprccpp) 【問題描述】 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分

48、成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子 29 / 56的重量之和?？梢钥闯觯械墓咏?jīng)過 n-1 次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為 1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。 例如有 3 種果子，數(shù)目依次為 1，2，9?？梢韵葘?1、2 堆合并，新堆數(shù)目為 3，耗費體力為 3。接著，將新堆與原先

49、的第三堆合并，又得到新的堆，數(shù)目為 12，耗費體力為 12。所以多多總共耗費體力=3+12=15?？梢宰C明 15 為最小的體力耗費值。 【輸入文件】 輸入文件 fruit.in 包括兩行，第一行是一個整數(shù) n(1n=10000)，表示果子的種類數(shù)。第二行包含 n 個整數(shù)，用空格分隔，第 i 個整數(shù)ai(1ai=20000)是第 i 種果子的數(shù)目。 【輸出文件】 輸出文件 fruit.out 包括一行，這一行只包含一個整數(shù)，也就是最小的體力耗費值。輸入數(shù)據(jù)保證這個值小于 231。 【樣例輸入】 3 1 2 9 【樣例輸出】 15 【數(shù)據(jù)規(guī)?！?對于 30的數(shù)據(jù)，保證有 n=1000： 對于 50

50、的數(shù)據(jù)，保證有 n=5000； 對于全部的數(shù)據(jù)，保證有 n=10000。 三、合唱隊形三、合唱隊形(chorus.pasdprccpp) 30 / 56【問題描述】 N 位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的 K位同學(xué)排成合唱隊形。 合唱隊形是指這樣的一種隊形：設(shè) K 位同學(xué)從左到右依次編號為1，2，K，他們的身高分別為 T1，T2，TK， 則他們的身高滿足T1.Ti+1TK(1=i=K)。 你的任務(wù)是，已知所有 N 位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形?！据斎胛募?輸入文件 chorus.in 的第一行是一個整數(shù) N(2=N=1

51、00)，表示同學(xué)的總數(shù)。第一行有 n 個整數(shù)，用空格分隔，第 i 個整數(shù) Ti(130=Ti=230)是第 i 位同學(xué)的身高(厘米)?！据敵鑫募?輸出文件 chorus.out 包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186 186 150 200 160 130 197 220【樣例輸出】4【數(shù)據(jù)規(guī)?！繉τ?50的數(shù)據(jù)，保證有 n=20；對于全部的數(shù)據(jù)，保證有 n=100。四、蟲食算四、蟲食算(alpha.pas/dpr/c/cpp)【問題描述】 31 / 56 所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據(jù)剩下的數(shù)字來判定被啃掉的字母。來看

52、一個簡單的例子： 43#9865#045 + 8468#6633 44445506978 其中#號代表被蟲子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：第一行的兩個數(shù)字分別是 5 和 3，第二行的數(shù)字是 5。 現(xiàn)在，我們對問題做兩個限制： 首先，我們只考慮加法的蟲食算。這里的加法是 N 進(jìn)制加法，算式中三個數(shù)都有 N 位，允許有前導(dǎo)的 0。 其次，蟲子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的，我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。如果這個算式是 N 進(jìn)制的，我們就取英文字母表午的前 N 個大寫字母來表示這個算式中的 0到 N-1 這 N 個不同的數(shù)字：但是這 N 個字母

53、并不一定順序地代表 0 到 N-1)。輸入數(shù)據(jù)保證 N 個字母分別至少出現(xiàn)一次。 BADC + CRDA DCCC 上面的算式是一個 4 進(jìn)制的算式。很顯然，我們只要讓 ABCD 分別代表0123，便可以讓這個式子成立了。你的任務(wù)是，對于給定的 N 進(jìn)制加法算式，求出 N 個不同的字母分別代表的數(shù)字，使得該加法算式成立。輸入數(shù)據(jù)保證有且僅有一組解，【輸入文件】 輸入文件 alpha.in 包含 4 行。第一行有一個正整數(shù) N(N=26)，后面的 3行每行有一個由大寫字母組成的字符串，分別代表兩個加數(shù)以及和。這 3 個字符串左右兩端都沒有空格，從高位到低位，并且恰好有 N 位。【輸出文件】 輸出

54、文件 alpha.out 包含一行。在這一行中，應(yīng)當(dāng)包含唯一的那組解。解是這樣表示的：輸出 N 個數(shù)字，分別表示 A，B，C所代表的數(shù)字，相鄰的兩個數(shù)字用一個空格隔開，不能有多余的空格。 32 / 56【樣例輸入】5ABCEDBDACEEBBAA【樣例輸出】1 0 3 4 2【數(shù)據(jù)規(guī)?！繉τ?30的數(shù)據(jù)，保證有 N10；對于 50的數(shù)據(jù)，保證有 N15；對于全部的數(shù)據(jù)，保證有 N26。2005 年第十二屆全國青少年信息學(xué)奧林匹克第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題聯(lián)賽復(fù)賽試題（NOIP2006NOIP2006 普及組）普及組）競賽時間：競賽時間：20062006 年年 1111 月月

55、1818 日日 下午下午 1:30-4:301:30-4:30試題名稱試題名稱randomrandomHappyHappycountcountsequencesequence目錄目錄randomrandomHappyHappycountcountsequencesequence輸入文件名輸入文件名random.inrandom.inhappy.inhappy.incount.incount.insequence.insequence.in輸出文件名輸出文件名random.outrandom.outhappy.outhappy.outcount.outcount.outsequence.outs

56、equence.out試題類型試題類型非交互式程序非交互式程序題題非交互式程序題非交互式程序題非交互式程序非交互式程序題題非交互式程序非交互式程序題題附加文件附加文件無無無無無無無無時限時限1 1 秒秒1 1 秒秒1 1 秒秒1 1 秒秒 33 / 56關(guān)于競賽中不同語言使用限制的說明關(guān)于競賽中不同語言使用限制的說明一關(guān)于使用一關(guān)于使用 PascalPascal 語言與編譯結(jié)果的說明語言與編譯結(jié)果的說明1 1對于對于 PascalPascal 語言的程序，當(dāng)使用語言的程序，當(dāng)使用 IDEIDE 和和 fpcfpc 編譯結(jié)果不一致時，以編譯結(jié)果不一致時，以 fpcfpc 的的編譯結(jié)果為準(zhǔn)。編譯結(jié)

57、果為準(zhǔn)。2 2允許使用數(shù)學(xué)庫允許使用數(shù)學(xué)庫(uses(uses mathmath 子句子句) )，以及，以及 ansistringansistring。但不允許使用編譯開。但不允許使用編譯開關(guān)（最后測試時關(guān)（最后測試時 pascalpascal 的范圍檢查開關(guān)默認(rèn)關(guān)閉：的范圍檢查開關(guān)默認(rèn)關(guān)閉：$R-,Q-,S-$R-,Q-,S-），也不支），也不支持與優(yōu)化相關(guān)的選項。持與優(yōu)化相關(guān)的選項。二關(guān)于二關(guān)于 C+C+語言中模板使用的限制說明語言中模板使用的限制說明1 1允許使用的部分允許使用的部分：標(biāo)準(zhǔn)容器中的布爾集合，迭代器，串，流。相關(guān)的頭文件： 2 2禁止使用的部分禁止使用的部分：序列：vect

58、or，list，deque序列適配器：stack, queue, priority_queue關(guān)聯(lián)容器：map, multimap, set, multiset擬容器：valarray 散列容器：hash_map, hash_set, hash_multimap, hash_multiset所有的標(biāo)準(zhǔn)庫算法相關(guān)頭文件： 34 / 56 1.明明的隨機數(shù)明明的隨機數(shù)（random.pas/c/cpp）【問題描述】明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機生成了 N 個 1 到 1000 之間的隨機整數(shù)（N100），對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉

59、，不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明明完成“去重”與“排序”的工作?！据斎胛募枯斎胛募?random.in 有 2 行，第 1 行為 1 個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)：N第 2 行有 N 個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)?！据敵鑫募枯敵鑫募?random.out 也是 2 行，第 1 行為 1 個正整數(shù) M，表示不相同的隨機數(shù)的個數(shù)。第 2 行為 M 個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)。【輸入樣例】 10 20 40 32 67 40 20 89 300 400 15【輸出樣例】 8 15 2

60、0 32 40 67 89 300 400 35 / 562.開心的金明開心的金明(happy.pas/c/cpp)【問題描述】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過 N 元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的 N 元。于是，他把每件物品規(guī)定了一個重要度，分為 5 等：用整數(shù) 15 表示，第 5 等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過 N元（可以等于 N 元）的前提下，使每件物品的價