“訊飛杯”合肥市第二十八屆青少年信息學(xué)奧林匹克競賽(小學(xué)組)解題報(bào)告

1、“訊飛杯”合肥市第二十八屆信息學(xué)奧林匹克競賽小學(xué)組“訊飛杯”合肥市第二十八屆青少年信息學(xué)奧林匹克競賽（小學(xué)組）解題報(bào)告 胡周國2011年11月26日 14:00-16:30（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）中文題目名稱聰聰買書魅力鏡片好勝的明明禮尚往來源程序名bookmagicprevailgift輸入文件名book.inmagic.inprevail.ingift.in輸出文件名book.outmagic.outprevail.outgift.out滿分100100100100測試點(diǎn)數(shù)目10101010是否有部分分否否否否內(nèi)存限制128M128M128M128M每個測試點(diǎn)時限1秒1秒1秒1秒一、

2、題目概況二、注意事項(xiàng)1. 考試時間為150分鐘。2. 務(wù)必看清題目，嚴(yán)格按照所要求的格式輸入、輸出。3. 在調(diào)試程序時請先使用題目中的示例數(shù)據(jù)，然后再自行設(shè)計(jì)多組測試數(shù)據(jù)進(jìn)行調(diào)試。4. 每題一般有10個測試點(diǎn)，測試有嚴(yán)格的時間限制，請盡可能優(yōu)化算法。5. 命名規(guī)則：(1)每題都規(guī)定了該題的英文名稱。(2)程序文件和數(shù)據(jù)文件的主文件名都是該題的英文名字。(3)程序文件擴(kuò)展名采用語言環(huán)境的默認(rèn)擴(kuò)展名。(4)數(shù)據(jù)文件都是文本文件，輸入和輸出文件的擴(kuò)展名分別是.in和.out。6. 程序應(yīng)從輸入文件讀取數(shù)據(jù)，并嚴(yán)格地按照規(guī)定的輸出格式將結(jié)果輸出到輸出文件中。輸入數(shù)據(jù)文件和輸出數(shù)據(jù)文件都與程序在同一個目

3、錄中，由于程序所在目錄是不確定的，因此不允許在文件名中含有盤符信息和任何形式的路徑信息。7. 選手在競賽結(jié)束時應(yīng)在D盤的根目錄下建立以準(zhǔn)考證號命名的文件夾，并將所完成各題的源程序文件和可執(zhí)行文件拷貝到該文件夾中。1.聰聰買書（book.bas/book.pas/book.c）【問題描述】圣誕節(jié)快到了，聰聰準(zhǔn)備給他的好朋友們買些小禮物。當(dāng)然，聰聰知道這些好朋友們都非常喜歡看漫畫書，所以，聰聰就決定買些好看的漫畫書送給他們。經(jīng)過一段時間的調(diào)查，聰聰發(fā)現(xiàn)有3種買書的方式：1 .書店現(xiàn)場購買：10元/本，超過5本以外的，8元/本，超過10本以外的，則6.5元/本；2.網(wǎng)上購買：9元/本，超過10本，全

4、部打8折，超過50本，則全部打六折；3.團(tuán)購：10本起團(tuán)購，7元/本，達(dá)到或超過30本，則6元/本，達(dá)到或超過50本，則5元/本。聰聰想用其中一種方式購n本書，請你幫他計(jì)算應(yīng)付多少元錢？【輸入文件】輸入文件只有1行為兩個數(shù)k和n，中間以一個空格隔開其中k表示選擇的購買方式（k=1表示書店現(xiàn)場購買，k=2表示網(wǎng)上購買，k=3表示團(tuán)購），n表示購買的本數(shù)(n<=200)?！据敵鑫募繎?yīng)付錢數(shù)（結(jié)果四舍五入保留到個位）【輸入輸出樣例】book.inbook.out1 1197【數(shù)據(jù)說明】保證輸入數(shù)據(jù)符合題目要求。這題就是考我們對for循環(huán)的掌握和題目的理解能力。還要考慮到是這個編程軟件是四舍五

5、入，還是五舍六入。程序如下：var k,n,i,j:longint; s:real;begin assign(input,'book.in'); assign(output,'book.out'); reset(input); rewrite(output); readln(k,n); if k=1 then begin if n<=5 then s:=n*10 else if n<=10 then s:=(n-5)*8+50 else s:=(n-10)*6.5+90; end; if k=2 then begin s:=n*9; if n>

6、50 then s:=s*0.6 else if n>10 then s:=s*0.8; end; if k=3 then begin if n>=50 then s:=n*5 else if n>=30 then s:=n*6 else if n>=10 then s:=n*7; end; write(s+0.1:0:0); close(input); close(output);end.但這次是四舍五入的軟件，所以只得了90分，后來聽老師講了一不管他是五舍六入還是四舍五入。那就是trunc（s+0.5)。程序如下：var k,n,i,j:longint; s:rea

7、l;begin assign(input,'book.in'); assign(output,'book.out'); reset(input); rewrite(output); readln(k,n); if k=1 then begin if n<=5 then s:=n*10 else if n<=10 then s:=(n-5)*8+50 else s:=(n-10)*6.5+90; end; if k=2 then begin s:=n*9; if n>50 then s:=s*0.6 else if n>10 then s:

8、=s*0.8; end; if k=3 then begin if n>=50 then s:=n*5 else if n>=30 then s:=n*6 else if n>=10 then s:=n*7; end; write(trunc(s+0.5); close(input); close(output);end.2.魅力鏡片（magic.bas/magic.pas/magic.c）【問題描述】由于聰聰一次性購買的書比較多，所以客氣的書店老板免費(fèi)贈送一塊好玩的鏡片給聰聰玩。一段時間以后，聰聰發(fā)現(xiàn)這塊鏡片真的不簡單：只要我們隨便在紙上寫一個整數(shù)，經(jīng)過這個鏡片一照，組成這

9、個整數(shù)的各位數(shù)字順序就會反轉(zhuǎn)，得到一個新數(shù)，當(dāng)然，神奇的不僅是這些，鏡片產(chǎn)生的新數(shù)依然符合整數(shù)的常見情形，即除非給定的整數(shù)為零，否則反轉(zhuǎn)得到的新數(shù)最高位數(shù)字不能為0。好奇的聰聰大膽猜測這個鏡片中肯定有些智能化的東西。但是，這個東西到底是怎么實(shí)現(xiàn)的呢？聰聰想用計(jì)算機(jī)程序來模擬這一功能，于是，他就找到了擅長編程的你，請你幫助聰聰來解決這一問題。【輸入文件】輸入共一行，一個整數(shù)?！据敵鑫募枯敵龉惨恍?，表示經(jīng)鏡片反轉(zhuǎn)后得到的新數(shù)?！据斎胼敵鰳永?】magic.inmagic.out123321【輸入輸出樣例2】magic.inmagic.out-120-21【數(shù)據(jù)范圍】-1,000,000,000N

10、1,000,000,000。這題就是要把他用字符串判-，預(yù)處理末尾的0，然后反過來輸出。程序如下：var i,j,k:longint; a:string;begin assign(input,'magic.in'); assign(output,'magic.out'); reset(input); rewrite(output); readln(i); str(i,a); k:=length(a); if a1='-' then begin write('-'); delete(a,1,1); k:=k-1; end; whil

11、e (ak='0')and(k<>1) do k:=k-1; for i:=k downto 1 do write(ai); close(input); close(output);end.得了100分。這題還可以用一個著名的算法叫什么酒什麼的，哪天問個老師。程序如下:var i,j,k,a:longint;begin assign(input,'magic.in'); assign(output,'magic.out'); reset(input); rewrite(output); readln(a); while a<&g

12、t;0 do begin k:=k*10+a mod 10; writeln(a div 10); a:=a div 10; end; write(k); close(input); close(output);end.3. 好勝的明明（prevail.bas/prevail.pas/prevail.c）【問題描述】明明和聰聰是好朋友，看著聰聰整天在他面前擺弄著那塊神奇的鏡片，明明有點(diǎn)生氣，總想找個機(jī)會挫挫他的銳氣，但是為了不破壞他們之間的友誼，明明給聰聰出了一道難題，題目是這樣的：明明在學(xué)習(xí)英語的時候發(fā)現(xiàn)記單詞是一件很痛苦的事，因?yàn)檫@些單詞都雜亂無章，于是明明決定對單詞進(jìn)行分類。兩個單詞可以

13、分為一類當(dāng)且僅當(dāng)組成這兩個單詞的各個字母的數(shù)量均相等，例如“AABAC”，它和“CBAAA”就可以歸為一類，而和“AAABB”就不是一類?，F(xiàn)在有N個單詞，所有單詞均由大寫字母組成，每個單詞的長度不超過100。請你告訴明明這些單詞會被分成幾類?！据斎胛募枯斎胛募牡谝恍袨閱卧~個數(shù)N，以下N行每行一個單詞?！据敵鑫募枯敵鑫募H包含一個數(shù)，表示這N個單詞分成的類數(shù)。【樣例輸入輸出】prevail.inprevail.out3AABACCBAAAAAABB2【數(shù)據(jù)范圍】對于70%的數(shù)據(jù)滿足N100；對于100%的數(shù)據(jù)滿足N550。這題有很多的做法，我把它每個排個序，然后拍個大序，如果在一起是一樣的

14、再找，直到不一樣的時，個數(shù)加1；程序如下：var b:array1.550of string; n,i,k,j:integer; d:string;procedure q(x,y:integer;var e:string);var i,j:integer; k,t:char;begin i:=x;j:=y;k:=e(x+y)div 2; repeat while ei<k do i:=i+1; while ej>k do j:=j-1; if i<=j then begin t:=ei; ei:=ej; ej:=t; i:=i+1; j:=j-1; end; until(i&

15、gt;j); if x<j then q(x,j,e); if i<y then q(i,y,e);end;begin assign(input,'prevail.in'); assign(output,'prevail.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do begin readln(bi); q(1,length(bi),bi); end; for i:=1 to n-1 do for j:=i to n do if bi<bj then begin

16、 d:=bi; bi:=bj; bj:=d; end; d:=b1; k:=1; for i:=2 to n do if d<>bi then begin d:=bi; k:=k+1; end; if n<>0 then write(k) else write('0'); close(input); close(output);end.4. 禮尚往來（gift.bas/gift.pas/gift.c）【問題描述】聰聰可被明明出的題目難倒了好一會，不過，經(jīng)過一番思考，聰聰還是把它解決了。作為回報(bào)，聰聰也給明明出了一個問題：平方數(shù)，或稱完全平方數(shù)，是指可以寫

17、成某個整數(shù)的平方的數(shù)，即其平方根為整數(shù)的數(shù)。例如，9 = 3 × 3，它是一個平方數(shù)。聰聰很早就發(fā)現(xiàn)4=2×2,9=3×3。而2不可能分解為兩個整數(shù)的乘積，但可以分解為1×1+1×1。聰聰曾經(jīng)遇到過對于任意給定的正整數(shù)n把它分解成幾個自然數(shù)的和的問題，在了解了平方數(shù)的知識后，聰聰想知道在所有拆分方案中，滿足所有加數(shù)都是平方數(shù)的方案有多少？【輸入文件】一個正整數(shù)n?！据敵鑫募繚M足條件的方案數(shù)?！据斎胼敵鰳永?】gift.ingift.out52【輸入輸出樣例2】gift.ingift.out136【樣例說明】5有2種分解方案，它們是：5=1&#

18、215;1+1×1+1×1+1×1+1×1=1×1+2×213有6種分解方案，它們是：13=1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1 =1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+2×2=1×1+1×

19、1+1×1+1×1+1×1+2×2+2×2=1×1+1×1+1×1+1×1+3×3=1×1+2×2+2×2+2×2=2×2+3×3【數(shù)據(jù)范圍】20%的數(shù)據(jù)，1n10;50%的數(shù)據(jù)，1n50;80%的數(shù)據(jù)，1n800;100%的數(shù)據(jù)，1n2000。這題正確做法是動態(tài)規(guī)劃，但現(xiàn)在我們沒有學(xué)習(xí)過，但可以用深搜來做，可以得80分，我也不知為什么連800都能過，最多只能過250，都夠嗆。這替深搜就是對平方數(shù)的對數(shù)深搜窮舉，如果他等于這個n就把得數(shù)加1；程序如下：var i,j,k,p,n,t:longint; ans:qword;procedure dfs(s,k:lo