NOIP2012復(fù)賽普及組精彩試題

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

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

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

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

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

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

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

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

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

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