程序設(shè)計(jì)比賽試題

程序設(shè)計(jì)比賽試題

最少錢(qián)幣數(shù)：

【問(wèn)題描述】

這是一個(gè)古老而又經(jīng)典的問(wèn)題。用給定的幾種錢(qián)幣湊成某個(gè)錢(qián)數(shù)，一般而言有多種方式。例

如：給定了6種錢(qián)幣面值為2、5、10、20、50、100,用來(lái)湊15元，可以用5個(gè)2元、1

個(gè)5元，或者3個(gè)5元，或者1個(gè)5元、1個(gè)10元，等等。顯然，最少需要2個(gè)錢(qián)幣才能

湊成15元。

你的任務(wù)就是，給定若干個(gè)互不相同的錢(qián)幣面值，編程計(jì)算，最少需要多少個(gè)錢(qián)幣才能湊成

某個(gè)給出的錢(qián)數(shù)。

【要求】

【數(shù)據(jù)輸入】輸入可以有多個(gè)測(cè)試用例。每個(gè)測(cè)試用例的第一行是待湊的錢(qián)數(shù)值M

(l<=M<=2000,整數(shù))，接著的一行中，第一個(gè)整數(shù)K(l<=K<=10)表示幣種個(gè)數(shù)，隨后

是K個(gè)互不相同的錢(qián)幣面值Ki(l<=Ki<=1000),輸入M=0時(shí)結(jié)束。

【數(shù)據(jù)輸出】每個(gè)測(cè)試用例輸出一行，即湊成錢(qián)數(shù)值M最少需要的錢(qián)幣個(gè)數(shù)。如果湊錢(qián)失

敗，輸出“Impossible"。你可以假設(shè)，每種待湊錢(qián)幣的數(shù)量是無(wú)限多的。

【樣例輸入】

15

625102050100

1

I2

0

【樣例輸出】

2

Impossible

Feli的生日禮物

【問(wèn)題描述】

Felicia的生日是11月1日（和Kitty是同一天生的哦）。于是Feli請(qǐng)來(lái)Kitty一起過(guò)生日。

Kitty帶來(lái)了最新款的“Kitty貓”玩具準(zhǔn)備送給Feli,不過(guò)她說(shuō)，這份禮物可不是白送的。

Feli要幫她一個(gè)忙，才能夠得到心儀已久的玩具。Kitty說(shuō)，“Kitty貓”玩具已經(jīng)賣(mài)出了n!

個(gè)，n<=10700*_*,Kitty想知道確切的數(shù)字，而不是無(wú)聊的“一個(gè)數(shù)加個(gè)感嘆號(hào)”。Feli聽(tīng)

了大吃一驚。要知道，算出n!是一個(gè)無(wú)比艱巨的任務(wù)。Feli告訴Kitty,就算Feli算出n!,

Kitty也看不下去，因?yàn)楫?dāng)n=20時(shí)，計(jì)算機(jī)的長(zhǎng)整型已經(jīng)存不下了（Kitty只能接受1-9之間

的數(shù)字）。于是Kitty說(shuō)，你只要告訴我n!最后一位非0的數(shù)就可以了。Feli想了想，立刻動(dòng)

手寫(xiě)了個(gè)程序算出了正確的答案?，F(xiàn)在，請(qǐng)你也試試看！注意哦，AC的男生將會(huì)得到一個(gè)

“HelloKitty”計(jì)算器（可編程，CPUITHz,Mem1TMB）,AC的女生將會(huì)得到一個(gè)仿真

“HelloKitty”寵物（善解人意，無(wú)須喂養(yǎng)，智商1101,附帶寫(xiě)情書(shū)功能）。

【要求】

【數(shù)據(jù)輸入】每行一個(gè)n,直到輸入數(shù)據(jù)結(jié)束

【數(shù)據(jù)輸出】對(duì)應(yīng)輸入的n,每行輸出一個(gè)答案

【樣例輸入】

1101

【樣例輸出】

8

蛇行矩陣

【問(wèn)題描述】

蛇形矩陣是由1開(kāi)始的自然數(shù)依次排列成的一個(gè)矩陣上三角形。

【要求】

【數(shù)據(jù)輸入】本題有多組數(shù)據(jù)，每組數(shù)據(jù)由一個(gè)正整數(shù)N緘g。（N不大于100）

【數(shù)據(jù)輸出】對(duì)于每一組數(shù)據(jù)，輸出一個(gè)N行的蛇形矩陣。兩組輸出之間不要額外的空行。

矩陣三角中同一行的數(shù)字用一個(gè)空格分開(kāi)。行尾不要多余的空格。

【樣例輸入】

5

【樣例輸出】

1361015

25914

4813

712

II

青蛙的約會(huì)

【問(wèn)題描述】

兩只青蛙在網(wǎng)上相識(shí)了，它們聊得很開(kāi)心，于是覺(jué)得很有必要見(jiàn)一面。它們很高興地發(fā)現(xiàn)它

們住在同一條緯度線(xiàn)上，于是它們約定各自朝西跳，直到碰面為止?？墒撬鼈兂霭l(fā)之前忘記

了一?件很重要的事情，既沒(méi)有問(wèn)清楚對(duì)方的特征，也沒(méi)有約定見(jiàn)面的具體位置。不過(guò)青蛙們

都是很樂(lè)觀的，它們覺(jué)得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只

青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂(lè)觀的青蛙，

你被要求寫(xiě)一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。

我們把這兩只青蛙分別叫做青蛙A和青蛙B,并且規(guī)定緯度線(xiàn)上東經(jīng)0度處為原點(diǎn)，由東

往西為正方向，單位長(zhǎng)度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)

點(diǎn)坐標(biāo)是x,青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩

只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線(xiàn)總長(zhǎng)L米。現(xiàn)在要你求出它們跳了幾次以后才會(huì)

碰面。

【要求】

【數(shù)據(jù)輸入】輸入只包括一行5個(gè)整數(shù)x,y,m,n>L,其中xWy<2000000000,0cm、

n<2000000000,0<L<2100000000o

【數(shù)據(jù)輸出】輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible”

【樣例輸入】

12345

【樣例輸出】

4

敲七

【問(wèn)題描述】

輸出7和7的倍數(shù)，還有包含7的數(shù)字例如(17,27,37...70,71,72,73...)

【要求】

【數(shù)據(jù)輸入】一個(gè)整數(shù)N。(N不大于30000)

【數(shù)據(jù)輸出】從小到大排列的不大于N的與7有關(guān)的數(shù)字，每行一個(gè)。

【樣例輸入】

20

【樣例輸出】

7

14

17

連續(xù)郵資問(wèn)題

【問(wèn)題描述】

G國(guó)發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資

問(wèn)題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)、使得可在1張信封上貼出從

郵資1開(kāi)始，增量為1的最大連續(xù)郵資區(qū)間。例如,當(dāng)n=5和m=4時(shí),面值為(1,3,11,15,32)

的5種郵票可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。編程任務(wù):對(duì)于給定的正整數(shù)m和

n,計(jì)算出郵票面值的最佳設(shè)計(jì)。

【要求】

【數(shù)據(jù)輸入】輸入數(shù)據(jù)每一行給出2個(gè)正整數(shù)m和n的值(l<=n,m<=9),最后以00表

示文件結(jié)束。

【數(shù)據(jù)輸出】對(duì)于輸以假定(ai,aj)=l.

輸出包含一個(gè)正整數(shù)，即為Andy家至少養(yǎng)豬的數(shù)目。

【樣例輸入】

3

31

51

72

【樣例輸出】

16

kitty貓的基因編碼

【問(wèn)題描述】

kitty的基因編碼如下定義：kitty的基因由一串長(zhǎng)度2"(k<=8)的01序列構(gòu)成，為了方便

研究，需要把,01序列轉(zhuǎn)換為ABC編碼。用T(s)來(lái)表示01序列s的ABC編碼T(s)='N

(當(dāng)S全由O組成)T(s)='BY當(dāng)s全由T組成)T(s)='C+T(sl)+T(s2)sl,s2為把s等

分為2個(gè)長(zhǎng)度相等的子串比如T('00')='A'T('0000111l')='CAB'

【要求】

【數(shù)據(jù)輸入】一行，長(zhǎng)度為2”，為kitty貓的01基因編碼，有多個(gè)數(shù)據(jù)

【數(shù)據(jù)輸出】一行，由ABC構(gòu)成的ABC編碼

【樣例輸出】

01001011

【樣例輸出】

CCCABACCBAB

取石子游戲

【問(wèn)題描述】

有兩堆石子，數(shù)量任意，可以不同。游戲開(kāi)始由兩個(gè)人輪流取石子。游戲規(guī)定，每次有兩種

不同的取法，一是可以在任意的一堆中取走任意多的石子：二是可以在兩堆中同時(shí)取走相同

數(shù)量的石子。最后把石子全部取完者為勝者。現(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你

先取，假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者。

【要求】

【數(shù)據(jù)輸入】輸入包含若干行，表示若干種石子的初始情況，其中每一行包含兩個(gè)非負(fù)整數(shù)

a和b,表示兩堆石子的數(shù)目，a和b都不大于1,000,000,000。

【數(shù)據(jù)輸出】輸出對(duì)應(yīng)也有若干行，每行包含一個(gè)數(shù)字1或0,如果最后你是勝者，則為1,

反之，則為0o

【樣例輸入】

21

84

47

【樣例輸出】

0

1

0

勇氣的挑戰(zhàn)

【問(wèn)題描述】

給定n個(gè)點(diǎn)的坐標(biāo)(x,y,z),且n<=50,從點(diǎn)1出發(fā)，怎么樣才能走一條路徑,訪(fǎng)問(wèn)每個(gè)點(diǎn)一次口僅

一次，使走過(guò)的距離和最小？

【要求】

【數(shù)據(jù)輸入】多組數(shù)據(jù).第1行n,然后n行3個(gè)整數(shù)坐標(biāo)

【數(shù)據(jù)輸出】每組一行,代表最小權(quán)和

【樣例輸入】

3

000

I10

1-10

【樣例輸出】

3.4

統(tǒng)計(jì)同成績(jī)學(xué)生人數(shù)

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):1608AcceptedSubmission(s):877

【問(wèn)題描述】

讀入N名學(xué)生的成績(jī)，將獲得某一給定分?jǐn)?shù)的學(xué)生人數(shù)輸出。

【要求】

【數(shù)據(jù)輸入】測(cè)試輸入包含若干測(cè)試用例，每個(gè)測(cè)試用例的格式為

第1行：N

第2行：N名學(xué)生的成績(jī)，相鄰兩數(shù)字用一個(gè)空格間隔。

第3行：給定分?jǐn)?shù)

當(dāng)讀到N=0時(shí)輸入結(jié)束。其中N不超過(guò)1000,成績(jī)分?jǐn)?shù)為(包含)0到100之間的一個(gè)整

數(shù)。

【數(shù)據(jù)輸出】對(duì)每個(gè)測(cè)試用例，將獲得給定分?jǐn)?shù)的學(xué)生人數(shù)輸出。

【樣例輸出】

3

806090

60

2

8566

0

5

6075905575

75

0

【樣例輸出】

1

0

2

錢(qián)幣兌換問(wèn)題

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):494AcceptedSubmission(s):247

【問(wèn)題描述】

在一個(gè)國(guó)家僅有1分，2分，3分硬幣，將錢(qián)N兌換成硬幣有很多種兌法。請(qǐng)你編程序計(jì)算

出共有多少種兌法。

【要求】

【數(shù)據(jù)輸入】每行只有一個(gè)正整數(shù)N,N小于32768o

【數(shù)據(jù)輸出】對(duì)應(yīng)每個(gè)輸入，輸出兌換方法數(shù)。

【樣例輸入】

2934

12553

【樣例輸出】

718831

13137761

字串?dāng)?shù)

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):405AcceptedSubmission(s):90

【問(wèn)題描述】

一個(gè)A和兩個(gè)B一共可以組成三種字符串:"ABB","BAB",“BBA".

給定若趕字母和它們相應(yīng)的個(gè)數(shù),計(jì)算一共可以組成多少個(gè)不同的字符串.

【要求】

【數(shù)據(jù)輸入】每組測(cè)試數(shù)據(jù)分兩行，第一行為n(l<=n<=26),表示不同字母的個(gè)數(shù)，第二行為n

個(gè)數(shù)Al,A2,...,An(k=Ai<=12),表示每種字母的個(gè)數(shù).測(cè)試數(shù)據(jù)以n=0為結(jié)束.

【數(shù)據(jù)輸出】對(duì)于每一組測(cè)試數(shù)據(jù)，輸出一個(gè)m,表示一共有多少種字符串.

【樣例輸入】

2

12

3

222

0

【樣例輸出】

3

90

小希的數(shù)表

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):201AcceptedSubmission(s):48

【問(wèn)題描述】

Gardon昨天給小希布置了一道作業(yè)，即根據(jù)一張由不超過(guò)5000的N(3<=N<=100)個(gè)正整數(shù)

組成的數(shù)表兩兩相加得到N*(N-l)/2個(gè)和，然后再將它們排序。例如，如果數(shù)表里含有四個(gè)

數(shù)1,3,4,9,那么正確答案是4,5,7,10,12,13。小希做完作業(yè)以后出去玩了一陣，

可是下午回家時(shí)發(fā)現(xiàn)原來(lái)的那張數(shù)表不見(jiàn)了，好在她做出的答案還在，你能幫助她根據(jù)她的

答案計(jì)算出原來(lái)的數(shù)表么？

【要求】

【數(shù)據(jù)輸入】包含多組數(shù)據(jù)，每組數(shù)據(jù)以一個(gè)N開(kāi)頭，接下來(lái)的一行有按照大小順序排列

的N*(N-l)/2個(gè)數(shù)，是小希完成的答案。文件最后以一個(gè)0結(jié)束。

假設(shè)輸入保證解的存在性和唯一性。

【數(shù)據(jù)輸出】對(duì)于每組數(shù)據(jù)，輸鋁原來(lái)的數(shù)表。它們也應(yīng)當(dāng)是按照順序排列的。

【樣例輸入】

4

457101213

4

5678910

0

【樣例輸出】

1349

2346

士兵隊(duì)列訓(xùn)練問(wèn)題

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):462AcceptedSubmission(s):185

【問(wèn)題描述】

某部隊(duì)進(jìn)行新兵隊(duì)列訓(xùn)練，將新兵從一開(kāi)始按順序依次編號(hào)，并排成一行橫隊(duì)，訓(xùn)練的規(guī)則

如下：從頭開(kāi)始一至二報(bào)數(shù)，凡報(bào)到二的出列，剩下的向小序號(hào)方向靠攏，再?gòu)念^開(kāi)始進(jìn)行

一至三報(bào)數(shù)，凡報(bào)到三的出列,剩下的向小序號(hào)方向靠攏,繼續(xù)從頭開(kāi)始進(jìn)行一至二報(bào)數(shù)。。。，

以后從頭開(kāi)始輪流進(jìn)行一至二報(bào)數(shù)、一至三報(bào)數(shù)直到剩下的人數(shù)不超過(guò)三人為止。

【要求】

【數(shù)據(jù)輸入】本題有多個(gè)測(cè)試數(shù)據(jù)組，第一行為組數(shù)N,接著為N行新兵人數(shù)，新兵人數(shù)

不超過(guò)5000。

【數(shù)據(jù)輸出】共有N行，分別對(duì)應(yīng)輸入的新兵人數(shù)，每行輸出剩下的新兵最初的編號(hào)，編

號(hào)之間有一個(gè)空格。

【樣例輸入】

2

20

40

【樣例輸出】

1719

11937

最簡(jiǎn)單的計(jì)算機(jī)

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):287AcceptedSubmission(s):192

【問(wèn)題描述】

一個(gè)名叫是PigHeadThree的研究組織設(shè)計(jì)了一臺(tái)實(shí)驗(yàn)用的計(jì)算機(jī)，命名為PpMm。PpMm

只能執(zhí)行簡(jiǎn)單的六種命令A(yù),B,C,D,E,F；只有二個(gè)內(nèi)存MLM2；三個(gè)寄存器R1,

R2,R3o六種命令的含義如下：

命令A(yù)：將內(nèi)存Ml的數(shù)據(jù)裝到寄存器R1中；

命令B：將內(nèi)存M2的數(shù)據(jù)裝到寄存器R2中；

命令C：將寄存器R3的數(shù)據(jù)裝到內(nèi)存Ml中；

命令D：將寄存器R3的數(shù)據(jù)裝到內(nèi)存M2中；

命令E：將寄存器R1中的數(shù)據(jù)和寄存器R2中的數(shù)據(jù)相加，結(jié)果放到寄存器R3中；

命令F：將寄存器R1中的數(shù)據(jù)和寄存器R2中的數(shù)據(jù)相減，結(jié)果放到寄存器R3中。

你的任務(wù)是：設(shè)計(jì)一個(gè)程序模擬PpMm的運(yùn)行。

【要求】

【數(shù)據(jù)輸入】有若干組，每組有2行，第一行是2個(gè)整數(shù)，分別表示Ml和M2中的初始內(nèi)

容；第二行是一串長(zhǎng)度不超過(guò)200的由大寫(xiě)字母A到F組成的命令串，命令串的含義如上

所述。

【數(shù)據(jù)輸出】對(duì)應(yīng)每一組的輸入，輸出只有一行，二個(gè)整數(shù)，分別表示Ml,M2的內(nèi)容；

其中Ml和M2之間用逗號(hào)隔開(kāi)。

其他說(shuō)明:RI,R2,R3的初始值為0,所有中間結(jié)果都在-2八31和2人31之間。

【樣例輸入】

100288

ABECED

876356321456

ABECAEDBECAF

【數(shù)據(jù)輸出】

388,388

2717080,1519268

愚人節(jié)的禮物

TimeLimit:5000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)

TotalSubmission(s):241AcceptedSubmission(s):168

【問(wèn)題描述】

四月一日快到了，Vayko想了個(gè)愚人的好辦法——送禮物。嘿嘿，不要想的太好，這禮物可

沒(méi)那么簡(jiǎn)單，Vayko為了愚人，準(zhǔn)備了一堆盒子，其中有一個(gè)盒子里面裝了禮物。盒子里面

可以再放零個(gè)或者多個(gè)盒子。假設(shè)放禮物的盒子里不再放其他盒子。用()表示一個(gè)盒子，B

表示禮物，Vayko想讓你幫她算出愚人指數(shù)，即最少需要拆多少個(gè)盒子才能拿到禮物。

【要求】

【數(shù)據(jù)輸入】本題目包含多組測(cè)試，請(qǐng)?zhí)幚淼轿募Y(jié)束。每組測(cè)試包含一個(gè)長(zhǎng)度不大于1000,

只包含和E三種字符的字符串，代表Vayko設(shè)計(jì)的禮物透視圖。

你可以假設(shè)，每個(gè)透視圖畫(huà)的都是合法的。

【數(shù)據(jù)輸出】對(duì)于每組測(cè)試，請(qǐng)?jiān)谝恍欣锩孑敵鲇奕酥笖?shù)。

【樣例輸入】

((((B)()))())

(B)

【樣例輸出】

4

1

整數(shù)對(duì)

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):111AcceptedSubmission⑸：29

【問(wèn)題描述】

Gardon和小希玩了一個(gè)游戲，Gardon隨便想了一個(gè)數(shù)A(首位不能為0),把它去掉一個(gè)數(shù)

字以后得到另外一個(gè)數(shù)B,他把A和B的和N告訴了小希，讓小希猜想他原來(lái)想的數(shù)字。

不過(guò)為了公平起見(jiàn)，如果小希回答的數(shù)雖然不是A,但同樣能達(dá)到那個(gè)條件(去掉其中的一

個(gè)數(shù)字得到B,A和B之和是N),一樣算小希勝利。而且小希如果能答出多個(gè)符合條件的

數(shù)字，就可以得到額外的糖果。

所以現(xiàn)在小希希望你編寫(xiě)一-個(gè)程序，來(lái)幫助她找到盡可能多的解。

例如，Gardon想的是A=31,B=3告訴小希N=34,

小希除了回答31以外還可以回答27(27+7=34)所以小?？梢砸虼硕玫揭粋€(gè)額外的糖果。

【要求】

【數(shù)據(jù)輸入】輸入包含多組數(shù)據(jù)，每組數(shù)據(jù)一行，包含一個(gè)數(shù)N(l<=N<=10A9),文件以0

結(jié)尾。

【數(shù)據(jù)輸出】對(duì)于每個(gè)輸入的N,輸出所有符合要求的解(按照大小順序排列)如果沒(méi)有這

樣的解，輸出"Nosolution."

【樣例輸入】

34

152

21

0

【樣例輸出】

273132

126136139141

Nosolution.

寒冰王座

TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):875AcceptedSubmission(s):358

【問(wèn)題描述】

不死族的巫妖王發(fā)工資拉，死亡騎士拿到一張N元的鈔票(記住，只有一張鈔票),為了防止自己

在戰(zhàn)斗中頻繁的死掉，他決定給自己買(mǎi)一些道具，于是他來(lái)到了地精商店前.死亡騎士：“我

要買(mǎi)道具！”地精商人：“我們這里有三種道具，血瓶150塊一個(gè)，魔法藥200塊一個(gè)，無(wú)敵

藥水350塊一個(gè)?！彼劳鲵T士：“好的，給我一個(gè)血瓶。”說(shuō)完他掏出那張N元的大鈔遞給地精

商人?地精商人：“我忘了提醒你了，我們這里沒(méi)有找客人錢(qián)的習(xí)慣的，多的錢(qián)我們都當(dāng)小費(fèi)

收了的，嘿嘿死亡騎士：“……”死亡騎士想，與其把錢(qián)當(dāng)小費(fèi)送個(gè)他還不如自己多買(mǎi)一

點(diǎn)道具，反正以后都要買(mǎi)的，早點(diǎn)買(mǎi)了放在家里也好，但是要盡量少讓他賺小費(fèi)?，F(xiàn)在死亡

騎士希望你能幫他計(jì)算一下，最少他要給地精商人多少小費(fèi)。

【要求】

【數(shù)據(jù)輸入】輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)T(l<=T<=100),代表測(cè)試數(shù)據(jù)的數(shù)量.然后是T

行測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)只包含一個(gè)正整數(shù)N(l<=N<=10000),N代表死亡騎士手中鈔票的

面值.

注意:地精商店只有題中描述的三種道具.

【數(shù)據(jù)輸出】對(duì)于每組測(cè)試數(shù)據(jù)，請(qǐng)你輸出死亡騎士最少要浪費(fèi)多少錢(qián)給地精商人作為小費(fèi).

【樣例輸入】

2

900

250

【樣例輸出】

0

50

覆蓋的面積

TimeLimit:10000/5000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)

TotalSubmission(s):170AcceptedSubmission(s):60

【問(wèn)題描述】

給定平面上若干矩形，求出被這些矩形覆蓋過(guò)至少兩次的區(qū)域的面積.

【要求】

【數(shù)據(jù)輸入】輸入數(shù)據(jù)的第一行是一個(gè)正整數(shù)T(k=T<=100),代表測(cè)試數(shù)據(jù)的數(shù)量.每個(gè)測(cè)試

數(shù)據(jù)的第一行是一個(gè)正整數(shù)N(k=N<=1000),代表矩形的數(shù)量,然后是N行數(shù)據(jù)，每?行包含

四個(gè)浮點(diǎn)數(shù)，代表平面上的一個(gè)矩形的左上角坐標(biāo)和右下角坐標(biāo)，矩形的上下邊和X軸平行,

左右邊和Y軸平行.坐標(biāo)的范圍從0到100000.注意:本題的輸入數(shù)據(jù)較多，推薦使用scanf讀

入數(shù)據(jù).

【數(shù)據(jù)輸出】對(duì)于每組測(cè)試數(shù)據(jù)，請(qǐng)計(jì)算出被這些矩形覆蓋過(guò)至少兩次的區(qū)域的面積.結(jié)果保

留兩位小數(shù).

【樣例輸入】

2

5

1142

1337

21.554.5

3.51.257.54

63107

3

0011

1021

2031

【樣例輸出】

7.63

0.00

積木分發(fā)

Timelimit:10sMemorylimit:32768K

TotalSubmit:1125AcceptedSubmit:365

【問(wèn)題描述】

歌手ThePancakes到幼兒園跟小朋友玩耍，她到達(dá)的時(shí)候小朋友們已經(jīng)爭(zhēng)著積木玩了。小朋

友都想要更多的積木砌一個(gè)自己喜歡的圖形，砌完就可以和ThePancakes合照。同時(shí)，The

Pancakes手上還有一些積木，她可以把手上的這些積木全部給一個(gè)小朋友，然后等該小朋友

砌完后就可以收回所發(fā)的積木和該小朋友原先手上的積木。但她不知道能否讓所有的小朋友

都和她合照，聰明的你可以幫助她嗎？

【要求】

【數(shù)據(jù)輸入】輸入包含多個(gè)數(shù)據(jù)。每個(gè)數(shù)據(jù)的第一行是兩個(gè)正整數(shù)n和s,iWnWlOOOO,1

WsWlOOOOOO,表示一共有n位小朋友，ThePancakes手上有s塊積木。以下有n行，每行

有兩個(gè)正整數(shù)，a和b,IWa,b^lOA9,表示第i個(gè)小朋友手上有a塊積木，還需要b塊積

木才能夠砌完。有多少種可能的決斗過(guò)程。

例如N=3,有6種不同的過(guò)程：12->13,12->23,13->12,13->32,23->21,23->31。

注意:文件里只有一個(gè)整數(shù)N(2WNW1000)。

【數(shù)據(jù)輸出】輸出一個(gè)整數(shù)，為可能的過(guò)程的總數(shù)除以1(X)07的余數(shù)。

【樣例輸入】

4

【樣例輸出】

96

猴子的爭(zhēng)斗

Timelimit:IsMemorylimit:32768K

TotalSubmit:184AcceptedSubmit:75

【問(wèn)題描述】

從前在一個(gè)森林里，有N只好斗的猴子。?開(kāi)始，他們互不認(rèn)識(shí)。互不認(rèn)識(shí)的猴子間是無(wú)

法避免爭(zhēng)斗的，而且爭(zhēng)斗只會(huì)發(fā)生在兩只互不認(rèn)識(shí)的猴子間。決斗結(jié)束后，這兩只猴子和他

們各自的朋友們通過(guò)這場(chǎng)決斗相互間都認(rèn)識(shí)了，爭(zhēng)斗便不會(huì)再發(fā)生在這一?大群猴子中的任兩

只。由于爭(zhēng)斗是比較激烈的，所以同一時(shí)間內(nèi)不會(huì)有兩場(chǎng)決斗一起發(fā)生。經(jīng)過(guò)N-1次決斗

后，這N只猴子間相互都認(rèn)識(shí)了，現(xiàn)在問(wèn)有多少種可能的決斗過(guò)程。例如N=3,有6種不

同的過(guò)程：12->13,12->23,13->12,13->32,23->21,23->31。

【要求】

【數(shù)據(jù)輸入】文件里只有一個(gè)整數(shù)N(2WNW1000)。

【數(shù)據(jù)輸出】輸出個(gè)整數(shù)，為可能的過(guò)程的總數(shù)除以10007的余數(shù)。

【樣例輸入】

4

【樣例輸出】

96

排序

Timelimit:10sMemorylimit:32768K

TotalSubmit:70AcceptedSubmit:2

【問(wèn)題描述】

通常我們對(duì)一個(gè)長(zhǎng)度為n(nW24)的整數(shù)數(shù)列進(jìn)行排序操作，其實(shí)就是講他們按照從小到大的

順序重整。一般情況下我們可以比較任意兩個(gè)數(shù)之間的大小并交換他們的位置，但這里我們

限制只能數(shù)列的某一個(gè)前綴序列翻轉(zhuǎn)，除此之外的任何操作都是不允許的。更精確地說(shuō)，假

設(shè)數(shù)列al,a2,,an,一個(gè)合法的操作是把數(shù)列變?yōu)閍k,ak-1,;a2,al,ak+1,ak+2,,

an,其中kkWn。例如：數(shù)列3214,可能的操作有三種,分別是2314、1234、4123。

你任務(wù)是求出一個(gè)序列用上面的方法排序至少需要多少步。

【要求】

【數(shù)據(jù)輸入】輸入文件有兩行：第一行是一個(gè)整數(shù)n,表示數(shù)列的長(zhǎng)度。第二行有n個(gè)整數(shù),

表示待排序的數(shù)列，每個(gè)整數(shù)的絕對(duì)值不大于32767。

【數(shù)據(jù)輸出】輸出文件有一行是一個(gè)整數(shù)s,表示完成排序所需的最少步數(shù)。

【樣例輸入】

4

3214

【樣例輸出】

I

提示:只需要一步就可以完成排序：32141234o

選址

Timelimit:10sMemorylimit:32768K

TotalSubmit:100AcceptedSubmit:13

【問(wèn)題描述】

很久以前，在世界的某處有一個(gè)形狀為凸多邊形的小島，島上的居民們決定建一個(gè)祭壇，居

民們認(rèn)為祭壇的位置離島的頂點(diǎn)處越遠(yuǎn)越好。你的任務(wù)是求凸多邊形內(nèi)一點(diǎn)，使其與各頂點(diǎn)

的距離中最短的距離最遠(yuǎn)，點(diǎn)在邊上也可以。這樣的點(diǎn)可能有多個(gè)，你只需輸出這些點(diǎn)與各

頂點(diǎn)的最短距離。

【要求】

【數(shù)據(jù)輸入】第一行是一個(gè)整數(shù)N(3WNW100)。

接下來(lái)N行按逆時(shí)針順序給出每個(gè)頂點(diǎn)的坐標(biāo)，每行包含2個(gè)實(shí)數(shù)，表示頂點(diǎn)的橫坐標(biāo)和

縱坐標(biāo)(坐標(biāo)絕對(duì)值小于10000)o

【數(shù)據(jù)輸出】輸出個(gè)實(shí)數(shù)，表示凸多邊形內(nèi)一點(diǎn)與各頂點(diǎn)的距離中最短的距離的最大值。

【樣例輸入】

3

02

90

77

【樣例輸出】

4.893

過(guò)河

Timelimit:isMemorylimit:32768K

TotalSubmit:518AcceptedSubmit:65

【問(wèn)題描述】

在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，

青蚌很討厭踩在這些石子上。由于橋的長(zhǎng)度和青蛙一次跳過(guò)的距離都是正整數(shù)，我們可以把

獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0,I,……，L（其中L是橋的長(zhǎng)度）。

坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L(zhǎng)的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開(kāi)始，不停的

向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或

跳過(guò)坐標(biāo)為L(zhǎng)的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長(zhǎng)度L,青蛙跳躍的

距離范圍S,T,橋上石子的位置。你的任務(wù)是確定青蛙要想過(guò)河，最少需要踩到的石子數(shù)。

【要求】

【數(shù)據(jù)輸入】輸入的第一行有一個(gè)正整數(shù)L（1<=L<=109）,表示獨(dú)木橋的長(zhǎng)度。第二行

有三個(gè)正整數(shù)S,T,M,分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)

數(shù)，其中1<=S<=T<=10,1<=M<=100。第三行有M個(gè)不同的正整數(shù)分別表示這M個(gè)

石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒(méi)有石子）。所有相鄰的整數(shù)之間用個(gè)

空格隔開(kāi)。

【數(shù)據(jù)輸出】輸出只包括一個(gè)整數(shù)，表示青蛙過(guò)河最少需要踩到的石子數(shù)。

【樣例輸入】

10

235

23567

【樣例輸出】

2

數(shù)字游戲

Timelimit:IsMemorylimit:32768K

TotalSubmit:323AcceptedSubmit:89

【問(wèn)題描述】

小w發(fā)明了一個(gè)游戲，他在黑板上寫(xiě)出了一行數(shù)字al,a2,….an,然后給你m個(gè)回合的機(jī)會(huì)，

每回合你可以從中選擇一個(gè)數(shù)擦去它，接著剩下來(lái)的每個(gè)數(shù)字ai都要遞減一個(gè)值bi?如此

重復(fù)m個(gè)回合，所有你擦去的數(shù)字之和就是你所得到的分?jǐn)?shù)。小W和他的好朋友小Y玩

了這個(gè)游戲，可是他發(fā)現(xiàn)，對(duì)于每個(gè)給出的an和bn序列，小Y的得分總是比他高，所以

他就很不服氣。于是他想讓你幫他算算，對(duì)于每個(gè)an和bn序列，可以得到的最大得分是多

少。這樣他就知道有沒(méi)有可能超過(guò)小Y的得分。

【要求】

【數(shù)據(jù)輸入】

第一行，一個(gè)整數(shù)n(l<=n<=200),表示數(shù)字的個(gè)數(shù)。

第二行，一個(gè)整數(shù)m(l<=m<=n),表示回合數(shù)。

接下來(lái)一行有n個(gè)不超過(guò)10000的正整數(shù)，al,a2…an,表示原始數(shù)字，最后一行有n個(gè)不

超過(guò)500的正整數(shù)，bl,b2-.bn,表示每回合每個(gè)數(shù)字遞減的值

【數(shù)據(jù)輸出】一個(gè)整數(shù)，表示最大可能的得分

【樣例輸入】

3

3

102030

456

【樣例輸出】

47

速配游戲

Timelimit:5sMemorylimit:32768K

TotalSubmit:295AcceptedSubmit:209

【問(wèn)題描述】

有這么?個(gè)速配電視節(jié)目。N位男士和N位女士要在攝像機(jī)前選出他們合適的伴侶。每位

女士按照其對(duì)每位男士作為配偶的偏愛(ài)程度給每位男士排名次，每位男士也按照其對(duì)每位女

士作為配偶的偏愛(ài)程度給每位女士排名次。這些名次不允許并列。然后每位男士將向心儀的

對(duì)象求婚，經(jīng)過(guò)“殘酷"的競(jìng)爭(zhēng)之后各自找到適合的伴侶。

最開(kāi)始的時(shí)候每位男士都還沒(méi)有被任何一位女士拒絕。求婚環(huán)節(jié)會(huì)經(jīng)過(guò)很多輪進(jìn)行，每一輪:

（1）每位男士向還沒(méi)有拒絕過(guò)自己的女士中選出自己認(rèn)為最理想的一個(gè)，并向她求婚

（2）每位女士在所有這一輪中向她求婚的男士中選出自己認(rèn)為最理想的一個(gè)，并不答應(yīng)，也

不拒絕。她把其余向她求婚的男士都婉言拒絕掉。經(jīng)過(guò)了若干輪求婚之后，在某一輪，幸運(yùn)

的事情發(fā)生了：所有的女士都恰好有一個(gè)求婚者，所有的男士都找到一個(gè)心儀的對(duì)象。主持

人將繼續(xù)指出這個(gè)配對(duì)方式的神奇之處：沒(méi)有任意的兩個(gè)配對(duì)，比方說(shuō)男士A和女士a配

對(duì)，男士B和女士b配對(duì),使得在A心目中b較a更理想，而且在b心目中A較B更理想（這

樣A和b就會(huì)"私奔因此，主持人總結(jié)說(shuō)，這個(gè)配對(duì)是非常合理的。（他知道，這種情況

是一定會(huì)發(fā)生的。）

主持人在節(jié)目之前已經(jīng)知道男士和女士之間的偏愛(ài)情況，他想預(yù)先知道最后的匹配結(jié)果是怎

么樣的，你能幫幫他嗎？

【要求】

【數(shù)據(jù)輸入】第一行包括一個(gè)數(shù)字N（l<=N<=1000）以卜N*2行，每行有N個(gè)數(shù)字。第i+1

行（l<=i<=N）表示編號(hào)為i的男士對(duì)女士們的排序（從最喜歡的到最不喜歡的）。第N+j+1

行（1<可<=N）表示編號(hào)為j的女士對(duì)男士們的排序（同樣從最喜歡的到最不喜歡的）.

【數(shù)據(jù)輸出】N行，每行包括一個(gè)數(shù)字。第i行的數(shù)字表示與編號(hào)為i的男士匹配的女士的

編號(hào)。

【樣例輸入】

3

123

231

213

321

231

231

【樣例輸出】

3

2

3n+l數(shù)鏈問(wèn)題

Timelimit:IsMemorylimit:32768K

TotalSubmit:471AcceptedSubmit:325

【問(wèn)題描述】

在計(jì)算機(jī)科學(xué)上，有很多類(lèi)問(wèn)題是無(wú)法解決的，我們稱(chēng)之為不可解決問(wèn)題。然而，在很多情

況我們并不知道哪一類(lèi)問(wèn)題可以解決，那一類(lèi)問(wèn)題不可解決?，F(xiàn)在我們就有這樣一個(gè)問(wèn)題，

問(wèn)題如下：

1.輸入一個(gè)正整數(shù)n；

2.把n顯示出來(lái)；

3.如果n=l則結(jié)束；

4.如果n是奇數(shù)則n變?yōu)?，否則n變?yōu)閚/2；

5.轉(zhuǎn)入第2步。

例如對(duì)于輸入的正整數(shù)22,應(yīng)該有如下數(shù)列被顯示出來(lái)：

221134175226134020105168421

我們推測(cè)：對(duì)于任意一個(gè)正整數(shù)，經(jīng)過(guò)以上算法最終會(huì)推到1。盡管這個(gè)算法很簡(jiǎn)單，但我

們?nèi)匀粺o(wú)法確定我們的推斷是否正確。不過(guò)好在我們有計(jì)算機(jī)，我們驗(yàn)證了對(duì)于小于

1,000,000的正整數(shù)都滿(mǎn)足以上推斷。對(duì)于給定的正整數(shù)n,我們把顯示出來(lái)的數(shù)的個(gè)數(shù)定義

為n的鏈長(zhǎng)，例如22的鏈長(zhǎng)為16o

你的任務(wù)是編寫(xiě)一個(gè)程序，對(duì)于任意一對(duì)正整數(shù)i和j,給出i、j之間的最長(zhǎng)鏈長(zhǎng)，當(dāng)然這

個(gè)最長(zhǎng)鏈長(zhǎng)是由i、j之間的其中一個(gè)正整數(shù)產(chǎn)生的。我們這里的i、j之間即包括i也包括j。

【要求】

【數(shù)據(jù)輸入】輸入文件只有一行，即為正整數(shù)i和j,i和j之間以一個(gè)空格隔開(kāi)。

0<iWj<10,000o

【數(shù)據(jù)輸出】文件只能有一行，即為i、j之間的最長(zhǎng)鏈長(zhǎng)。

【樣例輸入】

110

【樣例輸出】

20

數(shù)制轉(zhuǎn)換

Timelimit:IsMemorylimit:32768K

TotalSubmit:479AcceptedSubmit:190

【問(wèn)題描述】

有一種數(shù)制的基數(shù)是3,權(quán)值可以取-1,0,1,并分別用符號(hào)-,0,1表示，如這種數(shù)制的101表

示十進(jìn)制數(shù)的10,即1*(3A2)+0*(3A1)+1*(3A0)=l0,又如這種數(shù)制的-0表示十進(jìn)制數(shù)的-3,

即-1*(3八1)+0*(3八0)=-3。編程要求把給定的有符號(hào)整數(shù)轉(zhuǎn)換為新數(shù)制的數(shù)，該數(shù)的前面不能

有多余的0,如10的新數(shù)制表示是101,則不要輸出成301。

【要求】

【數(shù)據(jù)輸入】文件有?行或多行，每行有一個(gè)整數(shù)N(-2/47,483,647WNW2,147,483,647),

整數(shù)內(nèi)不會(huì)有其他分隔符。

【數(shù)據(jù)輸出】對(duì)輸入文件的每一行輸出一行，該行是輸入行的整數(shù)的新數(shù)制表示，不能有多

余空行，每行之前不能有前導(dǎo)空格。

【樣例輸入】

10

-3

【樣例輸出】

101

-0

數(shù)列

Timelimit:IsMemorylimit:32768K

TotalSubmit:415AcceptedSubmit:226

【問(wèn)題描述】

給定一個(gè)正整數(shù)k（3WkW15）,把所有k的方幕及所有有限個(gè)互不相等的k的方幕之和構(gòu)成一

個(gè)遞增的序列，例如，當(dāng)k=3時(shí)，這個(gè)序列是：1,3,4,9,10,12,13,…

（該序列實(shí)際上就是：30,31,30+31,32,30+32,31+32,30+31+32,???）

請(qǐng)你求出這個(gè)序列的第N項(xiàng)的值（用10進(jìn)制數(shù)表示）。

例如，對(duì)于k=3,N=100,正確答案應(yīng)該是981。

【要求】

【數(shù)據(jù)輸入】輸入包含多個(gè)測(cè)試數(shù)據(jù)。

每個(gè)測(cè)試數(shù)據(jù)只有1行，為2個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：kN

（k、N的含義與上述的問(wèn)題描述?致，且3WkW15,10WNW1000）

【數(shù)據(jù)輸出】對(duì)于每個(gè)測(cè)試數(shù)據(jù)輸出一個(gè)正整數(shù)（在所有的測(cè)試數(shù)據(jù)中，結(jié)果均不超過(guò)

2.1*109）。

【樣例輸入】

3100

3100

【樣例輸出】

981

981

2Ak進(jìn)制數(shù)

Timelimit:IsMemorylimit:32768K

TotalSubmit:110AcceptedSubmit:28

【問(wèn)題描述】

設(shè)r是個(gè)2k進(jìn)制數(shù)，并滿(mǎn)足以下條件：

（1）r至少是個(gè)2位的2k進(jìn)制數(shù)。

（2）作為2k進(jìn)制數(shù)，除最后一位外，r的每一位嚴(yán)格小于它右邊相鄰的那一位。

（3）將r轉(zhuǎn)換為2進(jìn)制數(shù)q后，則q的總位數(shù)不超過(guò)w。

在這里，正整數(shù)k（lWkW9）和w（k<w<30000）是事先給定的。

問(wèn)：滿(mǎn)足上述條件的不同的r共有多少個(gè)？

我們?cè)購(gòu)牧硪唤嵌茸餍┙忉專(zhuān)涸O(shè)S是長(zhǎng)度為w的01字符串（即字符串S由w個(gè)“0”或“I”

組成），S對(duì)應(yīng)于上述條件（3）中的q。將S從右起劃分為若干個(gè)長(zhǎng)度為k的段，每段對(duì)應(yīng)

一位2k進(jìn)制的數(shù)，如果S至少可分成2段，則S所對(duì)應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的2k

進(jìn)制數(shù)r。

例：設(shè)k=3,w=7。貝h是個(gè)八進(jìn)制數(shù)（23=8）o版w=7,長(zhǎng)度為7的01字符串按3位一

段分，可分為3段（即1,3,3,左邊第?段只有一個(gè)二進(jìn)制位），則滿(mǎn)足條件的八進(jìn)制數(shù)

有：2位數(shù)：高位為1：6個(gè)（即12,13,14,15,16,17）,般為2：5個(gè)，…，高位為

6：1個(gè)（即67）。共6+5+…+1=21個(gè)。3位數(shù):高位只能是1,第2位為2：5個(gè)（即123,

124,125,126,127）,第2位為3：4個(gè)，…，第2位為6：1個(gè)（即167）。共5+4+…+1=15

個(gè)。所以，滿(mǎn)足要求的r共有36個(gè)。

【要求】

【數(shù)據(jù)輸入】輸入包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)只有1行，為兩個(gè)正整數(shù)，用一個(gè)空格

隔開(kāi)：kW

【數(shù)據(jù)輸出】對(duì)于每個(gè)測(cè)試數(shù)據(jù)，輸出一行，是一個(gè)正整數(shù)，為所求的計(jì)算結(jié)果，即滿(mǎn)足條

件的不同的r的個(gè)數(shù)（用十進(jìn)制數(shù)表示），要求最高位不得為0,各數(shù)字之間不得插入數(shù)字

以外的其他字符（例如空格、換行符、逗號(hào)等）。

（提示：作為結(jié)果的正整數(shù)可能很大，但不會(huì)超過(guò)200位）

【樣例輸入】

37

37

【樣例輸出】

36

36

獎(jiǎng)學(xué)金

Timelimit:IsMemorylimit:32768K

TotalSubmit:363AcceptedSubmit:218

【問(wèn)題描述】

某小學(xué)最近得到了一筆贊助，打算拿出其中一部分為學(xué)習(xí)成績(jī)優(yōu)秀的前5名學(xué)生發(fā)獎(jiǎng)學(xué)金。

期末，每個(gè)學(xué)生都有3門(mén)課的成績(jī)：語(yǔ)文、數(shù)學(xué)、英語(yǔ)。先按總分從高到低排序，如果兩個(gè)

同學(xué)總分相同，再按語(yǔ)文成績(jī)從高到低排序，如果兩個(gè)同學(xué)總分和語(yǔ)文成績(jī)都相同，那么規(guī)

定學(xué)號(hào)小的同學(xué)排在前面，這樣，每個(gè)學(xué)生的排序是唯一確定的。

任務(wù)：先根據(jù)輸入的3門(mén)課的成績(jī)計(jì)算總分，然后按上述規(guī)則排序，最后按排名順序輸出前

5名學(xué)生的學(xué)號(hào)和總分。注意，在前5名同學(xué)中，每個(gè)人的獎(jiǎng)學(xué)金都不相同，因此，你必須

嚴(yán)格按上述規(guī)則排序。

例如，在某個(gè)正確答案中，如果前兩行的輸出數(shù)據(jù)（每行輸出兩個(gè)數(shù)：學(xué)號(hào)、總分）是：

7279

5279

這兩行數(shù)據(jù)的含義是：總分最高的兩個(gè)同學(xué)的學(xué)號(hào)依次是7號(hào)、5號(hào)。這兩名同學(xué)的總分都

是279（總分等于輸入的語(yǔ)文、數(shù)學(xué)、英語(yǔ)三科成績(jī)之和），但學(xué)號(hào)為7的學(xué)生語(yǔ)文成績(jī)更

高一些。如果你的前兩名的輸出數(shù)據(jù)是：

5279

7279

則按輸出錯(cuò)誤處理，不能得分。

【要求】

【數(shù)據(jù)輸入】輸入包含多組測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)有n+1行。

第1行為一個(gè)正整數(shù)n,表示該校參加評(píng)選的學(xué)生人數(shù)。

第2到n+1行，每行有3個(gè)用空格隔開(kāi)的數(shù)字，每個(gè)數(shù)字都在0至I」100之間。第j行的3個(gè)

數(shù)字依次表示學(xué)號(hào)為j-1的學(xué)生的語(yǔ)文、數(shù)學(xué)、英語(yǔ)的成績(jī)。每個(gè)學(xué)生的學(xué)號(hào)按照輸入順序

編號(hào)為l~n（恰好是輸入數(shù)據(jù)的行號(hào)減1）。

所給的數(shù)據(jù)都是正確的，不必檢驗(yàn)。

【數(shù)據(jù)輸出】對(duì)于每個(gè)測(cè)試數(shù)據(jù)輸出5行，每行是兩個(gè)用空格隔開(kāi)的正整數(shù)，依次表示前5

名學(xué)生的學(xué)號(hào)和總分。兩個(gè)相鄰測(cè)試數(shù)據(jù)間用一個(gè)空行隔開(kāi)。

【樣例輸入】

6

906780

876691

788991

889977

678964

788998

8

808989

889878

906780

876691

788991

889977

678964

788998

【樣例輸出】

6265

4264

3258

2244

1237

8265

2264

6264

1258

5258

紀(jì)念品分組

Timelimit:IsMemorylimit:32768K

TotalSubmit:92AcceptedSubmit:51

【問(wèn)題描述】

元旦快到了，校學(xué)生會(huì)讓樂(lè)樂(lè)負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。為使得參加晚會(huì)的同學(xué)所獲

得的紀(jì)念品價(jià)值相對(duì)均衡，他要把購(gòu)來(lái)的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組，但每組最多只能包括兩

件紀(jì)念品，并且每組紀(jì)念品的價(jià)格之和不能超過(guò)一個(gè)給定的整數(shù)。為了保證在盡量短的時(shí)間

內(nèi)發(fā)完所有紀(jì)念品，樂(lè)樂(lè)希望分組的數(shù)目最少。你的任務(wù)是寫(xiě)一個(gè)程序，找出所有分組方案

中分組數(shù)最少的一種，輸出最少的分組數(shù)目。

【要求】

【數(shù)據(jù)輸入】輸入包含多組測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)包含n+2行：

第1行包括一個(gè)整數(shù)w,為每組紀(jì)念品價(jià)格之和的上限。

第2行為一個(gè)整數(shù)n,表示購(gòu)來(lái)的紀(jì)念品的總件數(shù)。

第3~n+2行每行包含一個(gè)正整數(shù)pi(5<=pi<=w),表示所對(duì)應(yīng)紀(jì)念品的價(jià)格。

1<=n<=30000,80<=w<=200

【數(shù)據(jù)輸出】對(duì)每個(gè)測(cè)試數(shù)據(jù)，輸出一行，包含一個(gè)整數(shù)，即最少的分組數(shù)目。

相鄰兩個(gè)測(cè)試數(shù)據(jù)間用一個(gè)空行隔開(kāi)。

【樣例輸入】

100

9

90

20

20

30

50

60

70

80

90

【樣例輸出】

6

統(tǒng)計(jì)數(shù)字

Timelimit:IsMemorylimit:32768K

TotalSubmit:165AcceptedSubmit:58

【問(wèn)題描述】

某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò)1500000000(1.5*10^9)?已知不相同

的數(shù)不超過(guò)10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的

順序輸出統(tǒng)計(jì)結(jié)果。

【要求】

【數(shù)據(jù)輸入】包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)包含n+1行：

第1行是整數(shù)n,表示自然數(shù)的個(gè)數(shù)。

第2~n+l行每行一個(gè)自然數(shù)。

l<=n<=200000,每個(gè)數(shù)均不超過(guò)1500000000(1.5*109)

【數(shù)據(jù)輸出】對(duì)每個(gè)測(cè)試數(shù)據(jù)輸出m行(m為n個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù))，按照自然數(shù)

從小到大的順序輸出。每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個(gè)空

格隔開(kāi)。

相鄰兩個(gè)測(cè)試數(shù)據(jù)間用一個(gè)空行隔開(kāi)。

【樣例輸入】

8

2

4

2

4

5

100

2

100

【樣例輸出】

23

42

51

1002

矩陣取數(shù)游戲

Timelimit:IsMemorylimit:32768K

TotalSubmit:150AcceptedSubmit:27

【問(wèn)題描述】

帥帥經(jīng)常跟同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于?個(gè)給定的n*m的矩陣，矩陣中的每個(gè)元素aij

均為非負(fù)整數(shù)。游戲規(guī)則如下：

1.每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共n個(gè)。m次后取完矩陣所有元素；

2.每次取走的各個(gè)元素只能是該元素所在行的行首或行尾；

3.每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和，每行取數(shù)的得分=被取走的元

素值*2i,其中i表示第i次取數(shù)（從1開(kāi)始編號(hào)）；

4.游戲結(jié)束總得分為m次取數(shù)得分之和。

帥帥想請(qǐng)你幫忙寫(xiě)一個(gè)程序，對(duì)于任意矩陣，可以求出取數(shù)后的最大得分。

【要求】

【數(shù)據(jù)輸入】輸入有多個(gè)測(cè)試數(shù)據(jù)，每個(gè)包括n+1行：

第1行為兩個(gè)用空格隔開(kāi)的整數(shù)n和m。

第2~n+l行為n*m矩陣，其中每行有m個(gè)用單個(gè)空格隔開(kāi)的非負(fù)整數(shù)。

l<=n,m<=80,0<=aij<=1000

【數(shù)據(jù)輸出】對(duì)每個(gè)數(shù)據(jù)，輸出一行，為一個(gè)整數(shù)，即輸入矩陣取數(shù)后的最大得分。相鄰兩

個(gè)輸出間用一個(gè)空行隔開(kāi)。

【樣例輸入】

14

4505

210

96565446861223888043

16951829305388836467

【樣例輸出】

122

316994

四塔問(wèn)題

【問(wèn)題描述】

“漢諾塔”，是一個(gè)眾所周知的古老游戲?，F(xiàn)在我們把問(wèn)題稍微改變一下：如果一共有4

根柱子，而不是3根，那么至少需要移動(dòng)盤(pán)子多少次，才能把所有的盤(pán)子從第1根柱子移動(dòng)

到第4根柱子上呢？為了編程方便，您只需要輸出這個(gè)結(jié)果mod10000的值。

【要求】

【數(shù)據(jù)輸入】該題含有多組測(cè)試數(shù)據(jù)，每組一個(gè)正整數(shù)n。(0<n<=50000)

【數(shù)據(jù)輸出】一個(gè)正整數(shù)，表示把n個(gè)盤(pán)子從第1根柱子移動(dòng)到第4根柱子需要的最少移動(dòng)

次數(shù)mod10000的值。

【樣例輸入】

15

【數(shù)據(jù)輸出】

129

平方數(shù)

【問(wèn)題描述】

給出包含M個(gè)數(shù)字的列表，和列表中所有數(shù)字的所有質(zhì)因數(shù)。求出最長(zhǎng)的子列表，使得子

列表中所有數(shù)字的乘積是■?個(gè)完全平方數(shù)。

【要求】

【數(shù)據(jù)輸入】輸入文件包含多組測(cè)試數(shù)據(jù)。第一行包含兩個(gè)整數(shù)N,M(l<=N<=30,1<=

M<=30000).N是質(zhì)因數(shù)的個(gè)數(shù)。接下來(lái)一行有N個(gè)整數(shù)，給出所有的質(zhì)因數(shù)。然后一行

包含M個(gè)整數(shù)，給出列表。輸入文件結(jié)束于N=M=0.

【數(shù)據(jù)輸出】對(duì)于每組數(shù)據(jù)，輸出最長(zhǎng)子列表的兩個(gè)位置坐標(biāo)lr。1是該子列表在列表中的

起始位置，r是結(jié)束位置。如果多種情況都滿(mǎn)足子列表長(zhǎng)度最大，輸出1最小的一個(gè)。如果

不存在這樣的子列表輸出"None"。

【樣例輸入】

34

235

49256

34

235

6633

00

【樣例輸出】

13

I4

【問(wèn)題描述】

給定平面上三個(gè)圓的位置，請(qǐng)你用鋼筆在紙上畫(huà)出它們，作圖的起點(diǎn)自定。拿起鋼筆的時(shí)候,

你不能作圖。在畫(huà)完一個(gè)完整的圓后，才可以接著畫(huà)另一個(gè)，決不可半途中止去畫(huà)另一個(gè)圓.

已知把鋼筆移動(dòng)一個(gè)單位距離需要一個(gè)單位時(shí)間，拿起它則不需時(shí)間。請(qǐng)計(jì)算畫(huà)完這三個(gè)圓

所需的最小時(shí)間。

【要求】

【數(shù)據(jù)輸入】第一行為一個(gè)正整數(shù)T(T<=100),表示測(cè)試程序的次數(shù)。

接下來(lái)的T行，每一行都有9個(gè)實(shí)數(shù)Xl,y1,rl,x2,y2,r2,x3,y3,r3,分別指第訴=1,2,3)個(gè)圓的圓

心坐標(biāo)和半徑長(zhǎng)。其中，-10000<=xi,yi<=10000,0<ri<=10000.

【數(shù)據(jù)輸出】對(duì)于每?種測(cè)試情況，輸出相應(yīng)的最小作圖時(shí)間。

【樣例輸入】

2

000.5-200.5200.5

001-221221

【樣例輸出】

12.425

21.322

埃及分?jǐn)?shù)

【問(wèn)題描述】

在古埃及，人們使用單位分?jǐn)?shù)的和（形如1/a的,a是自然數(shù)）表示一切有理數(shù)。

如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因?yàn)榧訑?shù)中有相同的。

對(duì)于一個(gè)分?jǐn)?shù)a/b,表示方法有很多種，但是哪種最好呢？

首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個(gè)數(shù)相同的，最小的分?jǐn)?shù)越大越好。

如：

19/45=1/3+1/12+1/180

19/45=1/3+1/15+1/45

19/45=1/3+1/18+1/30,

19/45=1/4+1/6+1/180

19/45=1/5+1/6+1/18.

最好的是最后一種，因?yàn)?/18比1/180,1/45,1/30,1/180都大。

給出a,b（0<a<b〈1000）,編程計(jì)算最好的表達(dá)方式。

【要求】

【數(shù)據(jù)輸入】第一行:N表示有N組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)為一行包含a,b（0（a〈b〈1000）。

【數(shù)據(jù)輸出】每組測(cè)試數(shù)據(jù)若干個(gè)數(shù)，自小到大排列，依次是單位分?jǐn)?shù)的分母。

【樣例輸入】

1

1945

【樣例輸出】

5618

植樹(shù)活動(dòng)

TimeLimit:1000MSMemoryLimit:65536K

TotalSubmit:589Accepted:342

【問(wèn)題描述】春暖花開(kāi)，萬(wàn)物復(fù)蘇，這正是植物生長(zhǎng)的好季節(jié)。珠海校區(qū)舉行了一次題為“迎

百年校慶，添三分綠色”的植樹(shù)活動(dòng)。這次植樹(shù)活動(dòng)的目的除了美化我們的校