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

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

最少錢幣數(shù)：

【問題描述】

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

如：給定了6種錢幣面值為2、5、10、20、50、100,用來湊15元，可以用5個2元、1

個5元，或者3個5元，或者1個5元、1個10元，等等。顯然，最少需要2個錢幣才能

湊成15元。

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

某個給出的錢數(shù)。

【要求】

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

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

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

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

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

【樣例輸入】

15

625102050100

1

I2

0

【樣例輸出】

2

Impossible

Feli的生日禮物

【問題描述】

Felicia的生日是11月1日（和Kitty是同一天生的哦）。于是Feli請來Kitty一起過生日。

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

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

個，n<=10700*_*,Kitty想知道確切的數(shù)字，而不是無聊的“一個數(shù)加個感嘆號”。Feli聽

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

Kitty也看不下去，因為當(dāng)n=20時，計算機(jī)的長整型已經(jīng)存不下了（Kitty只能接受1-9之間

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

手寫了個程序算出了正確的答案。現(xiàn)在，請你也試試看！注意哦，AC的男生將會得到一個

“HelloKitty”計算器（可編程，CPUITHz,Mem1TMB）,AC的女生將會得到一個仿真

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

【要求】

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

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

【樣例輸入】

1101

【樣例輸出】

8

蛇行矩陣

【問題描述】

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

【要求】

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

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

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

【樣例輸入】

5

【樣例輸出】

1361015

25914

4813

712

II

青蛙的約會

【問題描述】

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

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

了一?件很重要的事情，既沒有問清楚對方的特征，也沒有約定見面的具體位置。不過青蛙們

都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只

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

你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。

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

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

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

只青蛙跳一次所花費(fèi)的時間相同。緯度線總長L米?，F(xiàn)在要你求出它們跳了幾次以后才會

碰面。

【要求】

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

n<2000000000,0<L<2100000000o

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

【樣例輸入】

12345

【樣例輸出】

4

敲七

【問題描述】

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

【要求】

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

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

【樣例輸入】

20

【樣例輸出】

7

14

17

連續(xù)郵資問題

【問題描述】

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

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

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

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

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

【要求】

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

示文件結(jié)束。

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

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

【樣例輸入】

3

31

51

72

【樣例輸出】

16

kitty貓的基因編碼

【問題描述】

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

研究，需要把,01序列轉(zhuǎn)換為ABC編碼。用T(s)來表示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個長度相等的子串比如T('00')='A'T('0000111l')='CAB'

【要求】

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

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

【樣例輸出】

01001011

【樣例輸出】

CCCABACCBAB

取石子游戲

【問題描述】

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

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

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

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

【要求】

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

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

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

反之，則為0o

【樣例輸入】

21

84

47

【樣例輸出】

0

1

0

勇氣的挑戰(zhàn)

【問題描述】

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

一次，使走過的距離和最?。?/p>

【要求】

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

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

【樣例輸入】

3

000

I10

1-10

【樣例輸出】

3.4

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

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

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

【問題描述】

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

【要求】

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

第1行：N

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

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

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

數(shù)。

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

【樣例輸出】

3

806090

60

2

8566

0

5

6075905575

75

0

【樣例輸出】

1

0

2

錢幣兌換問題

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

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

【問題描述】

在一個國家僅有1分，2分，3分硬幣，將錢N兌換成硬幣有很多種兌法。請你編程序計算

出共有多少種兌法。

【要求】

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

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

【樣例輸入】

2934

12553

【樣例輸出】

718831

13137761

字串?dāng)?shù)

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

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

【問題描述】

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

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

【要求】

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

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

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

【樣例輸入】

2

12

3

222

0

【樣例輸出】

3

90

小希的數(shù)表

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

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

【問題描述】

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

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

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

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

答案計算出原來的數(shù)表么？

【要求】

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

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

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

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

【樣例輸入】

4

457101213

4

5678910

0

【樣例輸出】

1349

2346

士兵隊列訓(xùn)練問題

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

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

【問題描述】

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

如下：從頭開始一至二報數(shù)，凡報到二的出列，剩下的向小序號方向靠攏，再從頭開始進(jìn)行

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

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

【要求】

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

不超過5000。

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

號之間有一個空格。

【樣例輸入】

2

20

40

【樣例輸出】

1719

11937

最簡單的計算機(jī)

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

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

【問題描述】

一個名叫是PigHeadThree的研究組織設(shè)計了一臺實驗用的計算機(jī)，命名為PpMm。PpMm

只能執(zhí)行簡單的六種命令A(yù),B,C,D,E,F；只有二個內(nèi)存MLM2；三個寄存器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è)計一個程序模擬PpMm的運(yùn)行。

【要求】

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

容；第二行是一串長度不超過200的由大寫字母A到F組成的命令串，命令串的含義如上

所述。

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

其中Ml和M2之間用逗號隔開。

其他說明: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

【問題描述】

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

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

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

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

【要求】

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

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

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

【數(shù)據(jù)輸出】對于每組測試，請在一行里面輸出愚人指數(shù)。

【樣例輸入】

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

(B)

【樣例輸出】

4

1

整數(shù)對

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

TotalSubmission(s):111AcceptedSubmission⑸：29

【問題描述】

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

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

不過為了公平起見，如果小?；卮鸬臄?shù)雖然不是A,但同樣能達(dá)到那個條件(去掉其中的一

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

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

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

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

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

【要求】

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

結(jié)尾。

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

樣的解，輸出"Nosolution."

【樣例輸入】

34

152

21

0

【樣例輸出】

273132

126136139141

Nosolution.

寒冰王座

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

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

【問題描述】

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

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

要買道具！”地精商人：“我們這里有三種道具，血瓶150塊一個，魔法藥200塊一個，無敵

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

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

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

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

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

【要求】

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

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

面值.

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

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

【樣例輸入】

2

900

250

【樣例輸出】

0

50

覆蓋的面積

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

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

【問題描述】

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

【要求】

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

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

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

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

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

【數(shù)據(jù)輸出】對于每組測試數(shù)據(jù)，請計算出被這些矩形覆蓋過至少兩次的區(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

【問題描述】

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

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

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

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

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

【要求】

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

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

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

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

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

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

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

【樣例輸入】

4

【樣例輸出】

96

猴子的爭斗

Timelimit:IsMemorylimit:32768K

TotalSubmit:184AcceptedSubmit:75

【問題描述】

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

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

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

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

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

同的過程：12->13,12->23,13->12,13->32,23->21,23->31。

【要求】

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

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

【樣例輸入】

4

【樣例輸出】

96

排序

Timelimit:10sMemorylimit:32768K

TotalSubmit:70AcceptedSubmit:2

【問題描述】

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

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

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

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

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

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

【要求】

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

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

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

【樣例輸入】

4

3214

【樣例輸出】

I

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

選址

Timelimit:10sMemorylimit:32768K

TotalSubmit:100AcceptedSubmit:13

【問題描述】

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

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

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

頂點的最短距離。

【要求】

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

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

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

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

【樣例輸入】

3

02

90

77

【樣例輸出】

4.893

過河

Timelimit:isMemorylimit:32768K

TotalSubmit:518AcceptedSubmit:65

【問題描述】

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

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

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

坐標(biāo)為0的點表示橋的起點，坐標(biāo)為L的點表示橋的終點。青蛙從橋的起點開始，不停的

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

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

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

【要求】

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

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

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

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

空格隔開。

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

【樣例輸入】

10

235

23567

【樣例輸出】

2

數(shù)字游戲

Timelimit:IsMemorylimit:32768K

TotalSubmit:323AcceptedSubmit:89

【問題描述】

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

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

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

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

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

少。這樣他就知道有沒有可能超過小Y的得分。

【要求】

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

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

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

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

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

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

【樣例輸入】

3

3

102030

456

【樣例輸出】

47

速配游戲

Timelimit:5sMemorylimit:32768K

TotalSubmit:295AcceptedSubmit:209

【問題描述】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

么樣的，你能幫幫他嗎？

【要求】

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

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

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

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

編號。

【樣例輸入】

3

123

231

213

321

231

231

【樣例輸出】

3

2

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

Timelimit:IsMemorylimit:32768K

TotalSubmit:471AcceptedSubmit:325

【問題描述】

在計算機(jī)科學(xué)上，有很多類問題是無法解決的，我們稱之為不可解決問題。然而，在很多情

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

問題如下：

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

2.把n顯示出來；

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

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

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

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

221134175226134020105168421

我們推測：對于任意一個正整數(shù)，經(jīng)過以上算法最終會推到1。盡管這個算法很簡單，但我

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

1,000,000的正整數(shù)都滿足以上推斷。對于給定的正整數(shù)n,我們把顯示出來的數(shù)的個數(shù)定義

為n的鏈長，例如22的鏈長為16o

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

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

【要求】

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

0<iWj<10,000o

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

【樣例輸入】

110

【樣例輸出】

20

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

Timelimit:IsMemorylimit:32768K

TotalSubmit:479AcceptedSubmit:190

【問題描述】

有一種數(shù)制的基數(shù)是3,權(quán)值可以取-1,0,1,并分別用符號-,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。編程要求把給定的有符號整數(shù)轉(zhuǎn)換為新數(shù)制的數(shù)，該數(shù)的前面不能

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

【要求】

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

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

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

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

【樣例輸入】

10

-3

【樣例輸出】

101

-0

數(shù)列

Timelimit:IsMemorylimit:32768K

TotalSubmit:415AcceptedSubmit:226

【問題描述】

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

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

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

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

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

【要求】

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

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

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

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

2.1*109）。

【樣例輸入】

3100

3100

【樣例輸出】

981

981

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

Timelimit:IsMemorylimit:32768K

TotalSubmit:110AcceptedSubmit:28

【問題描述】

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

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

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

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

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

問：滿足上述條件的不同的r共有多少個？

我們再從另一角度作些解釋：設(shè)S是長度為w的01字符串（即字符串S由w個“0”或“I”

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

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

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

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

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

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

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

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

個。所以，滿足要求的r共有36個。

【要求】

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

隔開：kW

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

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

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

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

【樣例輸入】

37

37

【樣例輸出】

36

36

獎學(xué)金

Timelimit:IsMemorylimit:32768K

TotalSubmit:363AcceptedSubmit:218

【問題描述】

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

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

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

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

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

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

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

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

7279

5279

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

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

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

5279

7279

則按輸出錯誤處理，不能得分。

【要求】

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

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

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

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

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

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

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

名學(xué)生的學(xué)號和總分。兩個相鄰測試數(shù)據(jù)間用一個空行隔開。

【樣例輸入】

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

【問題描述】

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

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

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

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

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

【要求】

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

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

第2行為一個整數(shù)n,表示購來的紀(jì)念品的總件數(shù)。

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

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

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

相鄰兩個測試數(shù)據(jù)間用一個空行隔開。

【樣例輸入】

100

9

90

20

20

30

50

60

70

80

90

【樣例輸出】

6

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

Timelimit:IsMemorylimit:32768K

TotalSubmit:165AcceptedSubmit:58

【問題描述】

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

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

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

【要求】

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

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

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

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

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

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

格隔開。

相鄰兩個測試數(shù)據(jù)間用一個空行隔開。

【樣例輸入】

8

2

4

2

4

5

100

2

100

【樣例輸出】

23

42

51

1002

矩陣取數(shù)游戲

Timelimit:IsMemorylimit:32768K

TotalSubmit:150AcceptedSubmit:27

【問題描述】

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

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

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

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

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

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

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

帥帥想請你幫忙寫一個程序，對于任意矩陣，可以求出取數(shù)后的最大得分。

【要求】

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

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

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

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

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

個輸出間用一個空行隔開。

【樣例輸入】

14

4505

210

96565446861223888043

16951829305388836467

【樣例輸出】

122

316994

四塔問題

【問題描述】

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

根柱子，而不是3根，那么至少需要移動盤子多少次，才能把所有的盤子從第1根柱子移動

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

【要求】

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

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

次數(shù)mod10000的值。

【樣例輸入】

15

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

129

平方數(shù)

【問題描述】

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

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

【要求】

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

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

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

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

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

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

【樣例輸入】

34

235

49256

34

235

6633

00

【樣例輸出】

13

I4

【問題描述】

給定平面上三個圓的位置，請你用鋼筆在紙上畫出它們，作圖的起點自定。拿起鋼筆的時候,

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

已知把鋼筆移動一個單位距離需要一個單位時間，拿起它則不需時間。請計算畫完這三個圓

所需的最小時間。

【要求】

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

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

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

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

【樣例輸入】

2

000.5-200.5200.5

001-221221

【樣例輸出】

12.425

21.322

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

【問題描述】

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

如：2/3=1/2+1/6,但不允許2/3=1/3+1/3,因為加數(shù)中有相同的。

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

首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個數(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.

最好的是最后一種，因為1/18比1/180,1/45,1/30,1/180都大。

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

【要求】

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

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

【樣例輸入】

1

1945

【樣例輸出】

5618

植樹活動

TimeLimit:1000MSMemoryLimit:65536K

TotalSubmit:589Accepted:342

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

百年校慶，添三分綠色”的植樹活動。這次植樹活動的目的除了美化我們的校