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

北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 更多競賽真題免費下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競賽 高考等資源 第十二屆全國青少年信息學(xué)奧林匹克 聯(lián)賽復(fù)賽試題 （ NOIP2006 普及組） 競賽時間： 2006 年 11 月 18 日 下午 1:30-4:30 試題名稱 random happy count sequence 目錄 random happy count sequence 輸入文件名 random.in happy.in count.in sequence.in 輸出文件名 random.out happy.out count.out sequence.out 試題類型 非交互式程序題 非交互式程序題 非交 互式程序題 非交互式程序題 附加文件 無 無 無 無 時限 1 秒 1 秒 1 秒 1 秒 關(guān)于競賽中不同語言使用限制的說明 一 關(guān)于使用 Pascal 語言 與 編譯結(jié)果的說明 1 對于 Pascal 語言的程序，當使用 IDE 和 fpc 編譯結(jié)果不一致時，以 fpc 的編譯結(jié)果為準。 2允許 使用數(shù)學(xué)庫 (uses math 子句 )，以及 ansistring。 但不允許使用編譯開關(guān)（ 最后測試時 pascal的范圍檢查開關(guān)默認關(guān)閉： $R-,Q-,S-），也不支持與優(yōu)化相 關(guān)的選項 。 二 關(guān)于 C+語言中模板使用的限制說明 1 允許使用 的部分 ： 標準容器中的布爾集合，迭代器，串，流。 相關(guān)的頭文件： 2 禁止使用的部分 ： 序列： vector， list， deque 序列適配器： stack, queue, priority_queue 關(guān)聯(lián)容器： map, multimap, set, multiset 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 擬容器： valarray 散列容器： hash_map, hash_set, hash_multimap, hash_multiset 所有的標準庫算法 相關(guān)頭文件： 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 1.明明的隨機數(shù) （ random.pas/c/cpp） 【問題描述】 明明想在學(xué)校中請一些同學(xué)一起做一項問卷調(diào)查，為了實驗的客觀性，他先用計算機生成了 N個 1 到 1000 之間的隨機整數(shù)（ N 100），對于其中重復(fù)的數(shù)字，只保留一個，把其余相同的數(shù)去掉，不同的數(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 20 32 40 67 89 300 400 2.開心的金明 (happy.pas/c/cpp) 【問題描述】 金明今天很開心，家里購置的新房就要領(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*wj2+ +vjk*wjk。（其中 *為乘號） 請你幫助金明設(shè)計一個滿足要求的購物單。 【輸入文件】 輸入文件 happy.in 的第 1 行，為兩個正整數(shù)，用一個空格隔開： N m 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 （其中 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）。 【輸入樣例】 1000 5 800 2 400 5 300 5 400 3 200 2 【輸出樣例】 3900 3.Jam 的計數(shù)法 （ count.pas/c/cpp） 【問題描述】 Jam 是個喜歡標新立異的科學(xué)怪人。他不使用阿拉伯數(shù)字計數(shù)，而是使用小寫英文字母計數(shù)，他覺得這樣做，會使世界更加豐富多彩。在他的計數(shù)法中，每個數(shù)字的位數(shù)都是相同的（使用相同個數(shù)的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數(shù)字”稱為 Jam 數(shù)字。在 Jam 數(shù)字中，每個字母互不相同，而且從左到右是嚴格遞增的。每次， Jam還指定使用字母的范圍，例如，從 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”，則 UV，且不存在 Jam 數(shù)字 P，使 UPV）。你的任務(wù)是：對于從文件讀入的一個 Jam 數(shù)字，按順序輸出緊接在后面的 5 個 Jam 數(shù)字，如果后面沒有那么多 Jam 數(shù)字，那么有幾個就輸出幾個。 【輸入文件】 輸入文件 counting.in 有 2 行，第 1 行為 3個正整數(shù)，用一個空格隔開： s t w （其中 s 為所使用的最小的字母的序號， t 為所使用的最大的字母的序號。 w 為數(shù)字的位數(shù)，這3 個數(shù)滿足： 1 st 26, 2 w t-s ） 第 2 行為具有 w 個小寫字母的字符串，為一個符合要求的 Jam 數(shù)字。 所給的數(shù)據(jù)都是正確的，不必驗證。 【輸出文件】 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報名咨詢熱線： 400-699-3290 輸出文件 counting.out 最多為 5 行，為緊接在輸入的 Jam 數(shù)字后面的 5 個 Jam數(shù)字，如果后面沒有那么多 Jam 數(shù)字，那么有幾個就輸出幾個。每行只輸出一個 Jam 數(shù)字，是由 w 個小寫字母組成的字符串，不要有多余的空格。 【輸入樣例】 2 10 5 bdfij 【輸出樣例】 bdghi bdghj bdgij bdhij befgh 4.數(shù)列 （ sequence.pas/c/cpp） 【問題描述】 給定一個正整數(shù) k(3 k 15),把所有 k 的方冪及所有有限個互不相等的 k 的方冪之和構(gòu)成一個遞增的序列，例如，當 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。 【輸入文件】 輸入文件