NOIP2012復賽普及組精彩試題

1、CCF全國信息學奧林匹克聯(lián)賽（NOIP2012）復賽普及組（請選手務必仔細閱讀本頁內(nèi)容）一題目概況中文題目名稱質(zhì)因數(shù)分解尋寶擺花文化之旅英文題目與子目錄 名primetreasureflowerculture可執(zhí)行文件名primetreasureflowerculture輸入文件名prime.i ntreasure.i nflower.i nculture.i n輸出文件名prime.outtreasure.outflower.outculture.out每個測試點時限1秒1秒1秒1秒測試點數(shù)目10101010每個測試點分值10101010附加樣例文件有有有有結(jié)果比較方式全文比較（過濾行末空格

2、及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)提交源程序文件名對于C+語言prime.cpptreasure.cppflower.cppculture.cpp對于C語言prime.ctreasure.cflower.cculture.c對于pascal 語言_:言prime.pastreasure.pasflower.pasculture.pas三編譯命令（不包含任何優(yōu)化開關(guān)）對于C+語言g+ -o prime prime.cpp -lmg+ -o treasure treasure.cpp -lmg+ -o flower flower.cpp -lmg+ -o culture culture.cpp

3、-lm對于C語言gcc -o prime prime.c -lmgcc -o treasure treasure.c - lmgcc-o flower flower.c -lmgcc -o culture culture.c -lm對于pascal 語言_:言fpc prime.pasfpc treasure.pasfpc flower.pasfpc culture.pas四運行內(nèi)存限制內(nèi)存上限128M128M128M128M注意事項：1、文件名(程序名和輸入輸出文件名)必須使用英文小寫。2、 C/C+中函數(shù)main()的返回值類型必須是int，程序正常結(jié)束時的返回值必須是0。3、 全國統(tǒng)一評

4、測時采用的機器配置為：CPU In tel Core2 Quad Q8200 2.33GHz ，內(nèi)存2G， 上述時限以此配置為準。4、特別提醒：評測在 NOI Linux 下進行。1. 質(zhì)因數(shù)分解(prime.cpp/c/pas)【問題描述】已知正整數(shù)n是兩個不同的質(zhì)數(shù)的乘積，試求出較大的那個質(zhì)數(shù)?！据斎搿枯斎胛募麨閜rime.i n。輸入只有一行，包含一個正整數(shù)n。【輸出】輸出文件名為prime.out。輸出只有一行，包含一個正整數(shù)p,即較大的那個質(zhì)數(shù)?！据斎胼敵鰳永縫rime.i nprime.out217【數(shù)據(jù)范圍】對于60%的數(shù)據(jù)，6 n 1000。對于100%的數(shù)據(jù)，6 n w

5、2*10 9。2. 尋寶(treasure.cpp/c/pas)【問題描述】傳說很遙遠的藏寶樓頂層藏著誘人的寶藏。小明歷盡千辛萬苦終于找到傳說中的這個藏 寶樓，藏寶樓的門口豎著一個木板，上面寫有幾個大字：尋寶說明書。說明書的內(nèi)容如下：藏寶樓共有 N+1層，最上面一層是頂層，頂層有一個房間里面藏著寶藏。除了頂層外，藏寶樓另有N層，每層M個房間，這 M個房間圍成一圈并按逆時針方向依次編號為0,M-1。其中一些房間有通往上一層的樓梯，每層樓的樓梯設計可能不同。每個房間里有一個 指示牌，指示牌上有一個數(shù)字x，表示從這個房間開始按逆時針方向選擇第x個有樓梯的房間（假定該房間的編號為k ）,從該房間上樓，

6、上樓后到達上一層的k號房間。比如當前房間的指示牌上寫著 2，則按逆時針方向開始嘗試，找到第2個有樓梯的房間，從該房間上樓。如果當前房間本身就有樓梯通向上層，該房間作為第一個有樓梯的房間。尋寶說明書的最后用紅色大號字體寫著：“尋寶須知：幫助你找到每層上樓房間的指示牌上的數(shù)字（即每層第一個進入的房間內(nèi)指示牌上的數(shù)字）總和為打開寶箱的密鑰”。請幫助小明算出這個打開寶箱的密鑰?！据斎搿枯斎胛募閠reasure.。第一行2個整數(shù)N和M,之間用一個空格隔開。N表示除了頂層外藏寶樓共N層樓,M表示除頂層外每層樓有 M個房間。接下來N*M行，每行兩個整數(shù)，之間用一個空格隔開，每行描述一個房間內(nèi)的情況，其中第

7、（i-1）*M+j行表示第i層j-1 號房間的情況（i=1,2,N ; j=1,2,，M ）。第一個整數(shù)表示該房間是否有樓梯通往上一層（0表示沒有，1表示有），第二個整數(shù)表示指示牌上的數(shù)字。注意，從j號房間的樓梯爬到上一層到達的房間一定也是j號房間。最后一行，一個整數(shù)，表示小明從藏寶樓底層的幾號房間進入開始尋寶（注：房間編號從0開始）?！据敵觥枯敵鑫募麨?treasure.out 。20123輸出只有一行，一個整數(shù)，表示打開寶箱的密鑰，這個數(shù)可能會很大，請輸出對取模的結(jié)果即可?！据斎胼敵鰳永縯reasure.i ntreasure.out2351203140115121【輸入輸出樣例說明】

8、第一層:0號房間，有樓梯通往上層，指示牌上的數(shù)字是2 ；1號房間，無樓梯通往上層，指示牌上的數(shù)字是3 ；2號房間，有樓梯通往上層，指示牌上的數(shù)字是4 ;第二層0號房間，無樓梯通往上層，指示牌上的數(shù)字是 1 ;1號房間，有樓梯通往上層，指示牌上的數(shù)字是 5 ； 2號房間，有樓 梯通往上層，指示牌上的數(shù)字是 2 ；小明首先進入第一層(底層)的 1號房間，記下指示牌上的數(shù)字為3，然后從這個房間開始，沿逆時針方向選擇第3個有樓梯的房間2號房間進入，上樓后到達第二層的2號房間，記下指示牌上的數(shù)字為2，由于當前房間本身有樓梯通向上層，該房間作為第一個有樓梯的房間。因此，此時沿逆時針方向選擇第2個有樓梯的房

9、間即為1號房間，進入后上樓梯到達頂層。這時把上述記下的指示牌上的數(shù)字加起來，即3+2=5，所以打開寶箱的密鑰就是5?！緮?shù)據(jù)范圍】對于 50%數(shù)據(jù)，有 0N 1000, 0x w 10000;對于 100%數(shù)據(jù)，有 0Nw 10000, 0MK 100, 0xW 1,000,000。3. 擺花(flower.cpp/c/pas)【問題描述】小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共m盆。通過調(diào)查顧客的喜好，小明列出了顧客最喜歡的n種花，從1到n標號。為了在門口展出更多種花，規(guī)定第i種花不能超過a i盆，擺花時同一種花放在一起，且不同種類的花需按標 號的從小到大的順序依次擺列。

10、試編程計算，一共有多少種不同的擺花方案。【輸入】輸入文件flower.in ，共2行。第一行包含兩個正整數(shù) n和m,中間用一個空格隔開。第二行有n個整數(shù)，每兩個整數(shù)之間用一個空格隔開，依次表示a 1、a2、an。【輸出】輸出文件名為flower.out 。輸出只有一行，一個整數(shù)，表示有多少種方案。注意：因為方案數(shù)可能很多，請輸出方 案數(shù)對1000007取模的結(jié)果?！据斎胼敵鰳永?】flower.inflower.out2 423 2【輸入輸出樣例說明】有 2 種擺花的方案，分別是 （1 ，1， 1， 2） ， （1 ，1，2，2）。括號里的 1 和 2 表示兩 種花，比如第一個方案是前三個位置擺第一種花，第四個位置擺第二種花?！緮?shù)據(jù)范圍】對于 20%數(shù)據(jù)，有 0n 8, 0mrc 8, 0 aw 8;對于 50%數(shù)據(jù)，有 0n 20, 0mC 20, 0 a w 20;對于 100%數(shù)據(jù)，有 0n w 100, 0 2?！緮?shù)據(jù)范圍】 對于20%的數(shù)據(jù)，有2 N 8, KW 5