資源描述:
《noip歷年復(fù)賽提高組試題-(2004-2013~)》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、
2、第十屆全國(guó)信息學(xué)奧林匹克分區(qū)聯(lián)賽(NOIP2004)復(fù)賽試題(提高組競(jìng)賽用時(shí):3小時(shí))1、津津的儲(chǔ)蓄計(jì)劃(Save.pas/dpr/c/cpp)【問(wèn)題描述】津津的零花錢(qián)一直都是自己管理。每個(gè)月的月初媽媽給津津300元錢(qián),津津會(huì)預(yù)算這個(gè)月的花銷(xiāo),并且總能做到實(shí)際花銷(xiāo)和預(yù)算的相同。為了讓津津?qū)W習(xí)如何儲(chǔ)蓄,媽媽提出,津津可以隨時(shí)把整百的錢(qián)存在她那里,到了年末她會(huì)加上20%還給津津。因此津津制定了一個(gè)儲(chǔ)蓄計(jì)劃:每個(gè)月的月初,在得到媽媽給的零花錢(qián)后,如果她預(yù)計(jì)到這個(gè)月的月末手中還會(huì)有多于100元或恰好100元,她就會(huì)把整百的錢(qián)存在媽媽那里,剩余的錢(qián)留在自己手中。例如11月初津津手中還有8
3、3元,媽媽給了津津300元。津津預(yù)計(jì)11月的花銷(xiāo)是180元,那么她就會(huì)在媽媽那里存200元,自己留下183元。到了11月月末,津津手中會(huì)剩下3元錢(qián)。津津發(fā)現(xiàn)這個(gè)儲(chǔ)蓄計(jì)劃的主要風(fēng)險(xiǎn)是,存在媽媽那里的錢(qián)在年末之前不能取出。有可能在某個(gè)月的月初,津津手中的錢(qián)加上這個(gè)月媽媽給的錢(qián),不夠這個(gè)月的原定預(yù)算。如果出現(xiàn)這種情況,津津?qū)⒉坏貌辉谶@個(gè)月省吃儉用,壓縮預(yù)算?,F(xiàn)在請(qǐng)你根據(jù)2004年1月到12月每個(gè)月津津的預(yù)算,判斷會(huì)不會(huì)出現(xiàn)這種情況。如果不會(huì),計(jì)算到2004年年末,媽媽將津津平常存的錢(qián)加上20%還給津津之后,津津手中會(huì)有多少錢(qián)。【輸入文件】輸入文件save.in包括12行數(shù)據(jù),每行包含一
4、個(gè)小于350的非負(fù)整數(shù),分別表示1月到12月津津的預(yù)算。【輸出文件】輸出文件save.out包括一行,這一行只包含一個(gè)整數(shù)。如果儲(chǔ)蓄計(jì)劃實(shí)施過(guò)程中出現(xiàn)某個(gè)月錢(qián)不夠用的情況,輸出-X,X表示出現(xiàn)這種情況的第一個(gè)月;否則輸出到2004年年末津津手中會(huì)有多少錢(qián)。
5、【樣例輸入1】29023028020030017034050908020060
6、【樣例輸出1】-7【樣例輸入2】290230280200300170330509080
7、20060【樣例輸出2】1580
8、2、合并果子(fruit.pas/dpr/c/cpp)【問(wèn)題描述】在一個(gè)果園里,多多已經(jīng)將所有的果子打了下來(lái),而且按果子的不同
9、種類(lèi)分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并,多多可以把兩堆果子合并到一起,消耗的體力等于兩堆果子的重量之和。可以看出,所有的果子經(jīng)過(guò)n-1次合并之后,就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。因?yàn)檫€要花大力氣把這些果子搬回家,所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1,并且已知果子的種類(lèi)數(shù)和每種果子的數(shù)目,你的任務(wù)是設(shè)計(jì)出合并的次序方案,使多多耗費(fèi)的體力最少,并輸出這個(gè)最小的體力耗費(fèi)值。例如有3種果子,數(shù)目依次為1,2,9。可以先將1、2堆合并,新堆數(shù)目為3,耗費(fèi)體力為3。接著,將新堆與原先的第三堆合并,又得到新
10、的堆,數(shù)目為12,耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15??梢宰C明15為最小的體力耗費(fèi)值?!据斎胛募枯斎胛募ruit.in包括兩行,第一行是一個(gè)整數(shù)n(1<=n<=10000),表示果子的種類(lèi)數(shù)。第二行包含n個(gè)整數(shù),用空格分隔,第i個(gè)整數(shù)ai(1<=ai<=20000)是第i種果子的數(shù)目?!据敵鑫募枯敵鑫募ruit.out包括一行,這一行只包含一個(gè)整數(shù),也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于231?!緲永斎搿?129【樣例輸出】15【數(shù)據(jù)規(guī)?!繉?duì)于30%的數(shù)據(jù),保證有n<=1000:對(duì)于50%的數(shù)據(jù),保證有n<=5000;對(duì)于全部的數(shù)據(jù),保證有n<
11、=10000。
12、3、合唱隊(duì)形(chorus.pas/dpr/c/cpp)【問(wèn)題描述】N位同學(xué)站成一排,音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列,使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形:設(shè)K位同學(xué)從左到右依次編號(hào)為1,2…,K,他們的身高分別為T(mén)1,T2,…,TK,則他們的身高滿足T1<...Ti+1>…>TK(1<=i<=K)。你的任務(wù)是,已知所有N位同學(xué)的身高,計(jì)算最少需要幾位同學(xué)出列,可以使得剩下的同學(xué)排成合唱隊(duì)形。【輸入文件】輸入文件chorus.in的第一行是一個(gè)整數(shù)N(2<=N<=100),表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù),用空格分隔,第i個(gè)整
13、數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高(厘米)?!据敵鑫募枯敵鑫募horus.out包括一行,這一行只包含一個(gè)整數(shù),就是最少需要幾位同學(xué)出列。【樣例輸入】8186186150200160130197220【樣例輸出】4【數(shù)據(jù)規(guī)?!繉?duì)于50%的數(shù)據(jù),保證有n<=20;對(duì)于全部的數(shù)據(jù),保證有n<=100。
14、4、蟲(chóng)食算(alpha.pas/dpr/c/cpp)【問(wèn)題描述】所謂蟲(chóng)食算,就是原先的算式中有一部分被蟲(chóng)子啃掉了,需要我們根據(jù)剩下的數(shù)字來(lái)判定被啃掉的字母。來(lái)看一