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

1、第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題（NOIP2006普及組）競賽時間：2006年11月18日 下午1:30-4:30試題名稱randomHappycountsequence目錄randomHappycountsequence輸入文件名random.inhappy.incount.insequence.in輸出文件名random.outhappy.outcount.outsequence.out試題類型非交互式程序題非交互式程序題非交互式程序題非交互式程序題附加文件無無無無時限1秒1秒1秒1秒關(guān)于競賽中不同語言使用限制的說明一關(guān)于使用Pascal語言與編譯結(jié)果的說明1對于Pascal語

2、言的程序，當(dāng)使用IDE和fpc編譯結(jié)果不一致時，以fpc的編譯結(jié)果為準(zhǔn)。2允許使用數(shù)學(xué)庫(uses math子句)，以及ansistring。但不允許使用編譯開關(guān)（最后測試時pascal的范圍檢查開關(guān)默認(rèn)關(guān)閉：$R-,Q-,S-），也不支持與優(yōu)化相關(guān)的選項。 1.明明的隨機數(shù)（random.pas/c/cpp）【問題描述】明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數(shù)（N100），對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉，不同的數(shù)對應(yīng)著不同的學(xué)生的學(xué)號。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請你協(xié)助明

3、明完成“去重”與“排序”的工作?！据斎胛募枯斎胛募andom.in 有2行，第1行為1個正整數(shù)，表示所生成的隨機數(shù)的個數(shù)：N第2行有N個用空格隔開的正整數(shù)，為所產(chǎn)生的隨機數(shù)?！据敵鑫募枯敵鑫募andom.out 也是2行，第1行為1個正整數(shù)M，表示不相同的隨機數(shù)的個數(shù)。第2行為M個用空格隔開的正整數(shù)，為從小到大排好序的不相同的隨機數(shù)?！据斎霕永?#160; 10  20 40 32 67 40 20 89 300 400 15【輸出樣例】  8  15 20 32 40 67 89 300 4002.開心的金明(happy.pas/c/cpp)【問題描述

4、】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j件物品的價格為vj，重要度為wj，共選中了k件物品，編號依次為j1，j2，jk，則所求的總和為：vj1*wj1+vj2

5、*wj2+ +vjk*wjk。（其中*為乘號）請你幫助金明設(shè)計一個滿足要求的購物單?！据斎胛募枯斎胛募appy.in 的第1行，為兩個正整數(shù)，用一個空格隔開：N m（其中N（<30000）表示總錢數(shù)，m（<25）為希望購買物品的個數(shù)。）從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有2個非負整數(shù)v p（其中v表示該物品的價格(v<=10000)，p表示該物品的重要度(15)）【輸出文件】輸出文件happy.out只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（<100000000）?！据斎霕永?000 5800 2400

6、 5300 5400 3200 2【輸出樣例】3900                  3.Jam的計數(shù)法（count.pas/c/cpp）【問題描述】Jam是個喜歡標(biāo)新立異的科學(xué)怪人。他不使用阿拉伯?dāng)?shù)字計數(shù)，而是使用小寫英文字母計數(shù)，他覺得這樣做，會使世界更加豐富多彩。在他的計數(shù)法中，每個數(shù)字的位數(shù)都是相同的（使用相同個數(shù)的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為Jam數(shù)字。在Jam數(shù)字中，每個字母互不相同，而且從左到右是嚴(yán)格遞增的。每次，Jam還指定

7、使用字母的范圍，例如，從2到10，表示只能使用b,c,d,e,f,g,h,i,j這些字母。如果再規(guī)定位數(shù)為5，那么，緊接在Jam數(shù)字“bdfij”之后的數(shù)字應(yīng)該是“bdghi”。（如果我們用U、V依次表示Jam數(shù)字“bdfij”與“bdghi”，則U<V< span>，且不存在Jam數(shù)字P，使U<P<V< span>）。你的任務(wù)是：對于從文件讀入的一個Jam數(shù)字，按順序輸出緊接在后面的5個Jam數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個就輸出幾個?！据斎胛募枯斎胛募ounting.in 有2行，第1行為3個正整數(shù)，用一個空格隔開：s t w（其

8、中s為所使用的最小的字母的序號，t為所使用的最大的字母的序號。w為數(shù)字的位數(shù)，這3個數(shù)滿足：1s<T< span>26, 2wt-s ） 第2行為具有w個小寫字母的字符串，為一個符合要求的Jam數(shù)字。所給的數(shù)據(jù)都是正確的，不必驗證?！据敵鑫募枯敵鑫募ounting.out 最多為5行，為緊接在輸入的Jam數(shù)字后面的5個Jam數(shù)字，如果后面沒有那么多Jam數(shù)字，那么有幾個就輸出幾個。每行只輸出一個Jam數(shù)字，是由w個小寫字母組成的字符串，不要有多余的空格。【輸入樣例】  2 10 5  bdfij【輸出樣例】bdghibdghjbdgijbdhijbefgh4.數(shù)列 （sequence.pas/c/cpp）【問題描述】給定一個正整數(shù)k(3k15),把所有k的方冪及所有有限個互不相等的k的方冪之和構(gòu)成一個遞增的序列，例如，當(dāng)k=3時，這個序列是：1，3，4，9，10，12，13，（該序列實際上就是：30，31，30+31，32，30+32，31+32，30+31+32，）請你求出這個序列的第N項的值（用10進制數(shù)表示）。例如，對于k=3，N=100，正確答案應(yīng)該是981。【輸入文件】輸入文件sequence.in 只有1行，為2個正整數(shù)，用一個空格隔開：k