【測驗M16】 2004網際網路程式設計全國大賽高中組-決賽題目                        [回前頁]

題目A 地牛翻身

輸入檔: pa.in /輸出檔: pa.out

在眾多的天然災害之中，地震要算是最常發生破壞力卻又極為強大的一種了。歷史上著名的地震如舊金山大地震、阪神地震等都造成了人民生命財產的極大損失，而數年前臺灣地區發生的921大地震更瞬間將一些地方變為人間煉獄，災區路有死骨，百姓流離失所的慘狀在許多人心中一直揮之不去成為長久的夢魘。

令人失望地，「預測地震」這樣一個簡單的夢想在今日的科技仍然難以準確地實行，儘管傳說中大地震之前有許多小動物都有特別的感知能力可以察覺地底能量的爆發，但人類在科技如此發達的現代文明之中，對此問題仍然束手無策。雖然如此，隨著對地下世界的探勘，我們對於地震形成的原理卻已有了不少的認識，例如我們知道地震的發生是由於板塊的移動和推擠所形成，而能量的分布和累積則是決定地震發生地點和時機的重大因素。

為了進一步的探測進而預知地震的發生，我們準備長期而連續地對地下能量的分布情形進行勘測，現在我們將地下的板塊視作一個矩形的區塊，然後將這個矩形的區域分成n*m個小方格，並且對於每一個方格進行偵測的工作，探測的結果會得到某個「能量值」，代表這個地方能量累積的強度有多少。如果一塊區域能量累積得越多，就表示這個地區越有可能發生地震。藉由研究地底能量的活動和轉移，希望能夠增加我們對地殼活動的掌握，進而事先預知地震的發生。

所以你的任務是，給定一張地下板塊的能量分布圖和一些特定的子區域，回報在這塊區域當中的「總能量累積值」有多少。

輸入檔說明:

輸入的第一行有兩個數n m(0<n, m<=1000)，n代表地下板塊的的縱向長度，m則代表橫向寬度。接下來的n行中每行有m個以空白字元分隔的數字，第i行的第j個數字便代表了編號(i,j)的小區塊的能量累積值(每個數字的範圍都在0到1000之中)。

輸入的第n+2行有一個數字q(0<q<=100000)，接下去的q行每行都有四個數字Bi Ti Li Ri(1<=Bi<=Ti<=n, 1<=Li<=Ri<=m)，代表查詢所有編號(Xi, Yi)的區塊(Bi<=Xi<=Ti, Li<=Yi<=Ri)總能量累積值有多少。

輸出檔說明:

輸出應有q行，每行有一個單一的整數，分別對應輸入的第n+3行到第n+q+2的查詢結果。

範例輸入:

5 5

1 3 2 4 5

0 23 1 3 20

59 3 4 23 1

39 2 4 133 2

99 3 1 69 3

5

1 3 2 4

1 5 1 5

2 2 2 2

3 4 1 2

1 2 3 4    

範例輸出:

66

507

23

103

10

題B 半個蛋糕

輸入檔: pb.in /輸出檔: pb.out

大饅頭是蛋糕研究社的成員，因此非常喜歡做出各種不同口味的蛋糕然後把它們吃掉。只要一天沒吃到蛋糕，就會覺得這天好像少了點什麼。但是你也知道，吃蛋糕是很容易發胖的，為了控制自己的身材，她決定每天只吃半個蛋糕。另外，大饅頭吃蛋糕還有個習慣：根據「日取其半，萬世不竭」的道理，當它她每次吃某一塊蛋糕時，都只會把那塊蛋糕切成剛好一半來吃，所以這個蛋糕就可以吃很久很久！(因為她有個很好的蛋糕保存設備，可以放很久都不會壞掉) 因此大饅頭開始了以下的「半個蛋糕」計畫：

第一天，大饅頭做了一個草莓蛋糕，並且切了一半來吃。第二天，因為原來的草莓蛋糕只剩一半，如果再切一半的話會不夠一天的分量，所以她只好重新做一個巧克力蛋糕，並且切一半來吃。第三天的時候，既然草莓蛋糕和巧克力蛋糕都剩下一半，她只要把兩種蛋糕各取剩下的一半來吃，就吃到 1/4 + 1/4 = 1/2 個蛋糕。第四天，因為剩下的蛋糕各切一半之後份量不足 1/2，所以她又做了一個冰淇淋蛋糕，吃掉一半......。對了，如果有她可以有兩種以上的方法湊到半個蛋糕吃，貪吃的大饅頭希望能吃到最多種的口味；如果有好幾種方法可以吃到最多種的口味，她希望能先去吃放比較沒那麼久的蛋糕，因為你也知道，新鮮的蛋糕總是比較好吃嘛！

自從開始這個計畫之後，大饅頭每天都可以吃到份量相當於半個蛋糕的蛋糕，有時候只能吃到一種口味 (例如第一、二、四天)，有時候可以吃到好幾種口味 (例如第三天)，因此大饅頭想到了一個有趣的問題，到底某一天她會吃到幾種口味的蛋糕呢？現在，你得寫個程式，幫她回答這個問題。

輸入檔說明:

輸入檔裡包含許多列，每一列有一個正整數，範圍在 1 ~ 232 – 1 之間，代表大饅頭想知道第幾天她吃到的蛋糕口味數。

輸出檔說明:

對於輸入檔每一列的正整數 n，輸出一列整數代表大饅頭第 n 天可以吃到幾種口味的蛋糕，因此輸出檔的列數應該和輸入檔的列數一樣多。

範例輸入:

1

2

3

4

5

範例輸出:

1

1

2

1

3

題目C Prufer 序列

輸入檔: pc.in /輸出檔: pc.out

Prufer 序列是一種樹狀結構的表示法，如果一個樹狀結構有 N 個點、N – 1條邊，點的編號從 1 到 N，則每種能由這 N 個點所能表示出來的樹都可以被編碼成唯一一列 N – 2 個數字，當 N 為 4 時，所有組合如下圖：

編碼的方式如下：葉子是點只有一條邊而已，如上圖(b)：點 3和點4都是葉子，每次找一個編號最小的葉子，然後輸出和他相鄰的點的編號，接著把這個編號最小的葉子拿掉，重複一直做，直到圖剩下二個點為止。

現在給你一個 Prufer 序列，請描敘出這個序列所代表的樹狀結構。

輸入檔說明：

輸入檔第一行包含一個整數 N ( 1 ≤ N ≤ 1000 )，代表有多少個樹狀結構需要解碼，接下來有 N 行，每行的第一個數 M ( 3 ≤ M ≤ 500 )，代表這個樹狀結構有多少個點，接著有 M – 2 個數字，代表 Prufer 序列，點的編號由1到M。

輸出檔說明：

每組樹狀結構輸出 M – 1 行，代表 M – 1 條邊，每行包含兩個數字 A、B (A < B)，代表點A和點B之間有一條邊相連，輸出順序先考慮 A從小排到大，當A一樣時，B從小排到大。

範例輸入：

2

4 4 3

8 3 3 4 5 4 6

輸出範例：

1 4

2 3

3 4

1 3

2 3

3 4

4 5

4 6

5 7

6 8

題目D 交通堵塞

輸入檔: pd.in /輸出檔: pd.out

許小瑞是一個上班族，但是他每天都苦於下班時間回家的塞車之苦。每次塞車都要花上好幾個小時才能從公司回到家。於是他終於痛下決心，收集了公司到家裡附近一些路段的車流速度資料，現在他把這些資料交給你，希望你能幫許小瑞寫一個程式算出他下班以後要走哪條路回家才能最快到家。

許小瑞收集的資料很詳細，他會記錄在不同的時間經過這個路段所需要的時間，而他注意到一件奇怪的事情；事情是這樣的，假設車子開過從路口i到路口j的道路，可能因為塞車的情形太嚴重了，先進入這條路的車子反而有可能會比後進入這條路的車子晚到達路口j。

舉例來說，假設在t時間以前通過這條路要花10的時間，而t時間以後通過就只要花5的時間。那麼許小瑞若是在t-1時間經過這條路，那他就要在t+9時間才能到達路口j，但如果他在t時間經過的話，在t+5時間就可到達路口j了。若是這種情形發生的話，許小瑞可以選擇在路口i一直等到t時間再出發，或是乾脆走別的路來節省時間。

為了簡化問題起見，你只要幫許小瑞算出他最快可以什麼時候到家就行了。

輸入檔說明:

輸入檔可能會有好幾組，每組輸入檔的第一行是一個整數 N (1 ≤ N ≤ 10000) 代表總共有N個路口。第二行會表示成M T1 T2 ...TM-1，正整數M跟著M-1個數字，M代表許小瑞把時間分成M個時段(1 ≤ M ≤ 100)，第1段是0到T1，第2段是T1到T2 ...第M段是TM以後。(0<T1< T2< T3<…<TM-1) ﹝許小瑞從公司出發的時間為0﹞。

接下來會有N+1塊輸入，代表公司、這N個路口和許小瑞家的道路連接狀況，以0表示公司，1…N表示這N個路口，N+1表示許小瑞家。由第0組輸入開始直到第N組輸入，第0組輸入是從公司到其他地點的連接狀況，而1....N組輸入分別是這N個路口到其他地點的資料。

第i塊輸入的資料表示如下：

Pi

L1 U1,1 U1,2 … U1,M

L2 U2,1 U2,2 … U2,M

...

LPi UPi,1 UPi,2 …UPi,M

其中Pi表示接下來會有Pi行輸入，Lx 代表從第i個路口可以到達第Lx個路口﹝0代表公司，N+1代表許小瑞家。﹞，每個Lx後面會有Ux,1 Ux,2 … Ux,M代表在不同的時段從i到Lx所要花的時間。舉例來說，如果許小瑞在時間t時從路口i要到路口x，且t是在第a個時段裡﹝Ta-1≤t<Ta﹞，那麼他會在時間t+Ux,a時到達路口x。連接兩個路口的路最多只會有一條。

如果N等於0的話，代表輸入結束。

輸出檔說明:

請輸出許小瑞最快什麼時候可以到家。

範例輸入:

4

2  8

2

1 5 10

3 8 2

1

2 7 3

1

5 7 2

2

1 4 5

4 6 3

2

2 3 1

5 1 9

2

1

2

1 8

2 13

1

3 9

2

1 6

3 7

0

範例輸出:

13

17

題目E 井字遊戲

輸入檔: pe.in /輸出檔: pe.out

 x |   | o

-----------

   | x |

-----------

   |   | o

井字遊戲的進行場地是在一個由井字畫分的九個區域上進行,由兩個人輪流交替玩,先下者持o(英文小寫O),後下者持x(英文小寫X),每次輪到的時候可以在空白的區域上留下屬於自己的記號,進行到有一人獲勝為止

獲勝的條件是至少有一條三連線,可以是一列,一行,或是對角線

輸入檔說明:

n

???

???

???

???

???

???

....共n個盤面,1個盤面有3*3的'?'('?'可以是'x'或'o',不然就是'.','o'是先下的人的記

號,'x'是後下的人的記號,'.'是空白區域的代表),盤面不會是已經進行完的盤面

輸出檔說明:

如果目前輪到的人無論對手怎麼下都可以贏的話,就印'Y',如果無法確定就印N

範例輸入:

2

...

...

...

..x

..x

oo.

範例輸出:

N

Y

題目F 神射手

輸入檔: pf.in /輸出檔: pf.out

一年一度的射箭競賽又來到了，照慣例艾斯塔跟亨利這兩個村莊都要派出一位箭手來參加比賽，潘達是艾斯塔村中的高手，號稱能千步穿楊，跟古代楚國的養由基比簡直是有過之而無不及；思洛斯是亨利村的射箭達人，傳說他可以一箭射下三隻在空中飛的鴿子，連南北朝的長孫晟都比不上他。今年的比賽，想必又是份外精采。

亨利村村長方奇想出了一個比賽的新點子，在比賽場地的一方圍起了一條水平線，選手們不得超越這條線，違者出局，在遙遠的另一方有著許多大大小小矩形的靶，位置高低各不同，靶的下緣和地面平行，當然靶有可能會互相重疊，比賽的方式是潘達跟思洛斯輪流射箭，射出的箭都只能水平飛行，所以在選手這一方會有各式各樣的梯子讓選手可以在任何高度都能射箭，當然，以潘達和思洛斯的程度，射出去的箭一定會貫穿所有的靶，飛向不可知的遠方。算分方式就是每回合兩個人各射一箭，然後去計算這一箭貫穿了多少個靶，打到靶邊的話也算是打中靶，貫穿比較多靶的人得一分，若兩人貫穿的靶數一樣則不計分，在好幾回合之後，得多分者勝！

輸入檔說明：

輸入檔的第一行包含一個整數 G ( 1 ≤ G ≤ 10 )，代表總共舉行了G場比賽，每場比賽輸入的第一行有二個整數 N, M ( 1 ≤ N ≤ 100000, 1 ≤ M ≤ 10000 )，代表這場比賽用了N個矩形靶比了M回合，接下來會有N行，每行有四個數字，分別代表矩形靶左下角的X座標、Y座標、寬、高，四個數字都介於 0 到 1500 之間，接下來會有M行，每行也有四個數字，分別代表了潘達這回合射出箭的X座標、Y座標和思洛斯射出箭的X座標、Y座標。(範例輸入的靶如下圖，最左下的點座標為 0, 0)

輸出檔說明：

每場比賽輸出一行結果，若潘達獲勝請輸出”Panda”，若思洛斯獲勝則請輸出”Sloth”，若雙方戰成平手則輸出”Draw”。

範例輸入：

1

3 2

0 0 3 5

2 3 4 5

1 4 7 2

3 5 2 3

4 5 1 1

範例輸出：

Panda

題目G  電晶體的祕密

輸入檔: pg.in /輸出檔: pg.out

實驗室從美國買了一批新式的電晶體, 這些電晶體的表面有許多許多的接腳, 因為這些東西從美國進口很貴, 所以他們想要自己來製造具有一樣功能的電晶體. 而複造的第一步, 就是先了解這些電晶體的構造.

據可靠情報指出, 這些電晶體的內部有一些長短不一的導電通路, 而這些導電通路彼此相接, 把電晶體表面的這些接腳都接在一起, 而且任兩個接腳之間, 只會有一條通路, 請看下面兩個示意圖, 左圖是只有一條通路的意思, 右圖的左上接腳和左下接腳之間有兩條通路, 另外左上接腳和右下接腳也不通.

當我們在導線的一端加上電壓, 在非常短的時間內, 它另一端的電壓也會上升, 而這個時間長度和這導線的長度成正比. 在這個實驗室裡有很精密的儀器, 可以測量這極短的時間差, 所以他們就對每一個電晶體測量, 找出任兩個接腳之間連接的導電通路的長度, 爾後就可以藉著這些資料, 找出這些電晶體的結構. 現在他們要先估算出每一個電晶體所需要的導線的總長度.

輸入檔說明：

輸入資料的第一行有一個正整數 N, 表示有 N 個電晶體. 接下來就是這 N 個電晶體的資料. 每一個電晶體的資料的第一行是一個正整數 M, 表示這個電晶體有 M 個接腳, M 不會超過 3000, 接下來有 M 行, 每行 M 個非負整數, 分別就是第 i 個接腳到第 j 個接腳的導體長度. 當然從 i 到 i 的長度是 0, 而從 i 到 j 和從 j 到 i 的長度一樣.

輸出檔說明：

有幾個電晶體就輸出幾行, 各行寫著該電晶體內導體的總長度.

輸入範例:

2

3

0 2 2

2 0 2

2 2 0

4

0 3 5 5

3 0 6 6

5 6 0 4

5 6 4 0

輸出範例:

3

9