10724 - Road Construction

孟加拉政府正在思考要如何解決達卡市的塞車問題，他們嘗試很多方向去解決這個問題。

上級長官 了解狀況的嚴重，他們向你求助於不同的看法與解決方法，作為一個資訊領域的你，給他們一個很簡單的想法，建造新的道路即可，但要確保這條新建道路可以使得旅途變短，這樣才能讓自動導航使用這條道路，進而改善塞車問題。

而達卡市的道路相當於無向圖，每個節點、邊分別對應站、道路。節點是由 2-D 平面的幾和點，而經由道路的花費由點與點的歐幾理德距離計算，現在只能新建一條道路，你將選擇其中兩個點建造出一條道路。

• 如果 (u, v)  本來就有一條道路，則不必考慮。
• 反之，C_uv = Sum (PreCost_ij -CurCost_ij)，CurCost_ij 表示加入新道路後的最短距離，而 PreCost_ij 表示之前的最短距離，將所有 i 到 j 都考慮，則最大的 C_uv 將會被選擇去新建。

Input
每組測資第一行有兩個整數 N, M (N <= 50, M <= 1225) ，

接下來會有 N 個點座標 (x, y), (-1000 <= x, y <= 1000)，而接下來會有 M 組 (u, v), (1 <= u, v <= N) 表示 u, v 之間已經有建造的道路。

當 N = M = 0 時，結束程式。

Output
對於每組測資，輸出最大的 C_uv  對應的 (u, v)，其中 u 越小越好，相同時 v 越小越好。

當 C_uv <= 1.0 時，則輸出 “No road required”。

Sample Input	Output for Sample Input
4 6 0 0 0 2 2 0 2 2 1 2 1 3 1 4 2 3 2 4 3 4 4 4 0 0 0 2 2 0 2 2 1 2 2 3 3 4 4 1 4 3 0 0 0 2 2 0 2 2 1 2 2 3 3 4 0 0	No road required 1 3 1 3

---

Problem setter: Md. Kamruzzaman
Member of Elite Problemsetters' Panel
Special thanks to Tahseen Mohammad

1229 - Sub-dictionary

在這個問題中，"dictionary" 字典定義為根據字典順序排序的單字，且每個單字有其相關連的定義，每個單字必然會使用其他單自來解釋，所以當字典定義 N 個單字時，則確切只會出現 N 個單字在字典中，當然不存在單字用來定義自己本身。


"sub-dictionary" 收集字典一部分的單字，當然也會符合上述的條件，而有門計算語言的課程指派一個作業，找到語言最基礎的單字量，並且把它建立成一部字典。 藉此可以推論理解出新的單字。


要讓機器自動學習相當困難，所以我們決定先教他幾個簡單常用的單字，一開始近似於 "sub-dictionary"，而藉由這些單字，機器將會拓展知識，逐步地理解新的單字，直到整個字典的單字都被理解。

例如要理解單字 "xyz" 前，必須理解所有它定義內的所有單字。

寫程式找到一個最小的 "sub-dictionary"。

Input 

輸入有多組測資。

每組測資第一行 有一個整數 n (1 <= n <= 100)，接下來會有 n 行，每行的第一個單字為字典內的單字，接下來會有數個單字表示定義該單字用的詞。

每個英文單字長度不超過 25，且每個單字的定義所需單字不超過 30 個。
而保證一開始給定的字典會符合上的描述。

Output 

對於每組測資，輸出最小字典的大小，接著按照字典順序輸出 sub-dictionary 內的單字。

Sample Input 

5 
aue oizer piqoi oizer 
doy oizer hweqlo hweqlo 
hweqlo piqoi aue 
oizer piqoi 
piqoi aue aue 
0

Sample Output 

3 
aue oizer piqoi

10765 - Doves and bombs

西元 1995 年，已經數年的和平日子，戰爭又即將爆發。

你的國家 Evergreen Macros And Confusing Shortcuts (EMACS) 要保護自己，免得受到鐵路帝國號稱的 Visually Impaired Machinists (VIM) 侵擾。

在這幾天爆發的戰爭中，政府投入大量資源去獲得 VIM 的情報，發現以下幾個資訊：

• VIM 具有龐大的鐵路網路，每個火車站彼此都是雙向連通的。
• 在戰爭爆發之前，每個火車站最多直接連接到另外 10 個火車站。
• VIM 的訊息交換都是藉由鐵路，在戰爭爆發之前，他們都盡可能使用鐵路通訊。
• 為了抵抗戰爭來襲，帝國中央命令可以藉由鴿子來傳遞訊息，但是這將會造成昂貴的負擔。因為鴿子要遠從 Pigeons In Courier Outfits (PICO) 的島嶼進口過來。
• 一旦鴿子抵達其中一個火車站，則就會休息，而且不能再次使用。因此盡可能使用火車來傳輸，而鴿子帶來的訊息將會被鐵路傳輸到其他火車站。

由於這些資訊，EMACS 政府打算擬策計畫來破壞邪惡帝國的活動，他們打算派出轟炸機摧毀火車站，妨礙帝國的訊息通訊，而帝國就必須引入鴿子來協助，藉此分散他們對戰爭的助力。

不幸地， 政府花太多錢在蒐集情報，以至於沒有足夠的錢製作炸彈，於是只能摧毀一個火車站。你要找到最好的候選車站進行催毀，好壞根據 "鴿子值" ，這個鴿子值定義：當一個火車站被摧毀後，中央至少要派幾隻鴿子進行傳輸的工作，才能傳遞到所有未摧毀的火車站

由於不知道中央指揮部在哪，也就是說他們至少一定會使用一個鴿子將訊息傳遞到一個未摧毀的火車站，再經由鐵路傳遞到更遠的火車站。

Input

輸入有多組測資，每組第一行有兩個整數 n, m。

• n：(3 <= n <= 10000) 表示帝國火車站個數，且編號從 0 到 n-1 。
• m：(1 <= m <= n) 表示要挑選候選的個數。

接下來會有數行表示鐵路連接資訊，每行 (x,y)，表示 x 和 y 相連，直到 x = y = -1 表示資訊結束。

當 n = m = 0 結束程式。

Output

對於每組測資，輸出 m 行，輸出候選火車站的資訊，根據鴿子值由高到低，相同時則按照鴿子值由小到大，只要輸出前 m 個即可。

每組測資後輸出一行空行。

Sample Input                             Output for Sample Input

8 4 0 4 1 2 2 3 2 4 3 5 3 6 3 7 6 7 -1 -1 0 0

2 3 3 3 4 2 0 1

---

Problemsetter: Paul Shelly

610 - Street Directions

根據汽車碰撞監測，很多致命的交通事故發生於雙向通行街道，為了減少意外事故的發生，市長決定要使盡可能多的街道變成單向，你被雇用來解決這個問題。

一開始給定一些雙向的道路，每個道路連接兩個十字路口，並且中間不會經過其他十字路口，每個路口最多 4 個街道相連，而最多只會有一條道路連接至相同的路口，也有可能道路的尾端是死路，當都是雙向道路時，任兩個目的地都可以相鄰。

Input 

測資有多組。

每組第一行有兩個整數 n, m (2 <= n <= 1000)，接下來會有 m 行表示雙道道路的資訊，每行上有兩個整數 i j，表示路口 i 和 j 互相連接。而路口的編號為 1 到 n。

當 n = m= 0 結束程式。

Output 

對於每組測資，先輸出測資組編號。緊接著依序輸出單向訊息 i, j ，表示 i 可以通往道 j。
因此輸出 i, j 不同於 j, i 的意思。

每組測資後輸出一個 '#' 字元。


任何一組符合解都可以被接受。

Sample Input 

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
0 0

Sample Output 

1

1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
2

1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#

---

Miguel A. Revilla
1999-03-24

848 - Fmt

 在 unix 系統中，有一個 fmt  程式，用來處理文字顯示，結合許多行，或者是將行與行之間分行，而且每一行最多 72 個字元(含)，處理結合行與分行的規則如下：

備註翻譯：想像文章中的段落，以下翻譯改編題目意思，因為看不懂，請高人指點。

• 對於一個新段落，一開始可能會有許多空白，而段落最後不會存在多餘的空白。
  
  
• 分行字元 '\n' 將不會在輸入時顯示，而在輸出部分，段落可能占有數行，其中的每一行尾端不會存在空白。在段落結束前，每一行一開始將不會有任何空白或者空行。如果輸入的 '\n' 字元被結合成一行時，則替換成一個空白進行串接。
• 每的字詞不超過 72 個字元，也就是再長的字元最多占有一行。
  
• 每個字詞不允許跨行，一定要在同一行顯示。

Sample Input 

   Unix fmt

The unix fmt program reads lines of text, combining
and breaking lines so as to create an
output file with lines as close to without exceeding
72 characters long as possible.  The rules for combining and breaking
lines are as follows.

   1.  A new line may be started anywhere there is a space in the input.
If a new line is started, there will be no trailing blanks at the
end of the previous line or at the beginning of the new line.

   2.  A line break in the input may be eliminated in the output, provided
it is not followed by a space or another line break.  If a line
break is eliminated, it is replaced by a space.

Sample Output 

   Unix fmt

The unix fmt program reads lines of text, combining and breaking lines
so as to create an output file with lines as close to without exceeding
72 characters long as possible.  The rules for combining and breaking
lines are as follows.

   1.  A new line may be started anywhere there is a space in the input.
If a new line is started, there will be no trailing blanks at the end of
the previous line or at the beginning of the new line.

   2.  A line break in the input may be eliminated in the output,
provided it is not followed by a space or another line break.  If a line
break is eliminated, it is replaced by a space.

---

Miguel Revilla 2002-06-15

168 - Theseus and the Minotaur

在希臘神話中，有一個傳說「忒修斯(Theseus)和牛頭怪」 這是一個不太可能的故事，故事中參雜了一個牛頭的怪物、充滿曲折的地下迷宮、失戀的女孩以及線球。在這次競賽的教育性質上，我們要揭露這個真實故事。

迷宮有很多洞窟，每個洞窟經由幾個通道可以通往其他洞窟，而其中幾個只能單向通行。為了設下陷阱抓到牛頭怪，忒修斯發現牛頭怪怕光，於是帶著大量的蠟燭進入迷宮。

忒修斯在迷宮四處找尋，最後他聽到牛頭怪從通道另一端傳來的聲音，從那個時刻開始，忒修斯點燃蠟燭並且展開追逐行動，牛頭怪會離開原本的洞窟，並且移動到下一個洞窟。而忒修斯慢慢地跟著牛頭怪移動，當每經過 k 個洞窟，他將會在此點燃一個蠟燭放下，當他快速點燃蠟燭後，會繼續跟蹤牛頭怪。由於有蠟燭的洞窟牛頭怪不會靠近，因此將會限制住牛頭怪的移動。

當牛頭怪離開洞窟時，會依序檢察其它不存在蠟燭的洞窟，找到第一個可去的地方並且移動，最後牛頭怪會被困住無法移動，忒修斯將可以戰勝牠。

迷宮類似於下圖表示，而牛頭怪離開的時候就好比按照字典順序檢查：

假設忒修斯在 C，他會聽到牛頭怪從 A 傳來的聲音，假設 k = 3，而走的順序依序為 A, B, D(忒修斯在此放下點燃的蠟燭), G, E, F(再放一個), H, E, G(再放一個), H, E(牛頭怪最後受困的地點)。

備註翻譯：由於忒修斯尾隨牠，牛頭怪不會走回上次的洞窟。



寫一個程式模擬整個追逐過程，所有洞窟將只會用大寫英文字母表示，並且按照順序打印出蠟燭的放置，以及最後牛頭怪被困的洞窟。

Input

輸入有多組測資，每組用一行表示圖形以及忒修斯位置、牛頭怪位置、k。

每一行不超過 255 個字元。

讀到 '#' 結束程式。

Output

對於每組測資，按照順序輸出蠟燭的放置(追逐時的順序)，以及牛頭怪最後的位置。

Sample input

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
#

Sample output

D F G /E

10690 - Expression Again

給定一個代數方程 (x1+x2+x3+.....+xn)*(y1+y2+.........+ym) ，其中會有 n+m 個整數，必須要找到可以代出的 最大值 和 最小值。例如：給定  (x1+x2)*(y1+y2)，而能使用的數字為 1, 2, 3, 4，每個數字只能使用一次，則最大值為  (1+4)*(2+3) = 25，最小值則為 (4+3)*(2+1) = 21。

Input

對於每組測資，給定兩個正整數 N, M (N, M < 51)，接下來會有 N+M 個整數，每個數字介於 -50 到 50 之間(含)。

測資最多 110 組。

Output

對於每組測資，輸出一行最大值以及最小值。

Sample Input                           Output for Sample Input

2 2 1 2 3 4 3 1 1 2 3 4 2 2 2 2 2 2

25 21 24 9 16 16

---

Problem setter: Md Kamruzzaman, Member of Elite Problemsetters' Panel

Special Thanks: Monirul Hasan, Md. Sajjad Hossain

11664 - Langton's Ant

數學家 Christopher Langton 設計一套簡單的細胞自動機，名為 Langton's ant，根據給定的一個簡單行為規則但卻有趣的行為，這個行為是數學家研究的課題。


從分析螞蟻行為以及 Langton 的細胞自動機，根據給定的當下自動機的狀態，以及全自動的螞蟻能力，將會發現螞蟻呈現一個特別的走訪模式，進行探索這個世界。

螞蟻的世界為一個 n x n 的平面，每一格塗上藍色或者是紅色，而每一格座標定義 (i, j) (1 <= i, j <= n)，螞蟻的移動規則如下：

• 如果當前在藍色格子，她會將格子變成紅色，並且向左轉 90 度，並且朝這個方向前進一格。
• 如果當前在藍色格子，她會將格子變成紅色，並且向右轉 90 度，並且朝這個方向前進一格。
• 如果移動失敗，即掉出格子外，螞蟻則宣告死亡。

例如：假設有一隻螞蟻現在在紅色格子上，並且面朝東方，而牠會將這格變成紅色，並且面朝南方，如果南方沒有格子可走，那麼牠則會死亡 。反之，則會走下南方的那一格，並且重複步驟進行移動。


根據給定的狀態以及當前螞蟻所在位置，你的任務是要決定螞蟻能不能到達 (n, n)。

假設螞蟻一開始面朝北方。

Input 

由於狀態是 n x n ，可以表示 n² bits 的二進制數字，方便起見定義 0 是藍色，1 是紅色。而給定的順序為由左而右、由下而上。

例如：0100 (十進制為 4) 表示一個 2 x 2 的狀態

blue	blue
blue	red

而  011010100 (十進制為 212) 表示一個 3 x 3 的狀態

red	blue	blue
blue	red	blue
blue	red	red

額外補充：相對應座標如下 (x, y)

(3,1)	(3,2)	(3,3)
(2,1)	(2,2)	(2,3)
(1,1)	(1,2)	(1,3)

輸入有多組測資，每組測資第一行會有四個整數 n, c, x, y

• n ( 1 <=  n  <= 16)：狀態的大小
• c ( 0 <= c  < 2⁽ⁿ²⁾)：一個十進制表示  n²-bit 二進制數，其數值為上描述。
• (x, y)：表示螞蟻一開始所在的位置 (1 <= x, y <= n)。

當 n = c = x = y = 0 結束程式。

Output 

對於每組測資，輸出格式為以下兩種的其中一種：

• `Yes'：如果螞蟻能夠抵達 (n, n)
• `Kaputt!'：如果螞蟻無法抵達 (n, n)

對於每組測資，保證一定會在有限步數內得到其中一種結果。

Sample Input 

2 8 1 1
2 4 1 1
2 15 1 1
0 0 0 0

Sample Output 

Yes
Kaputt!
Kaputt!

---

10992 - The Ghost of Programmers

西元 2500 年，Dhaka 學校的資工系系主任向大學新鮮人介紹：「這是一個 Dhaka 學校中最古老的一棟建築，而我們從來沒有進去過」接著學生好奇地向他問道「為什麼沒進去過？」主任回答道：「這個原因追溯到 21 世紀，我們那時常在這裡舉辦程式設計競賽，當時所有的出題者們常會來到這裡，由於他們太喜歡這個地方了，以至於連他們死後也會來這裡！」學生緊接著問道「先生，有多少鬼魂會來到這呢？」主任回答「沒人知道有多少，但有九個最常見的鬼會出現！」

0. The ghost of Tanveer Ahsan – 每隔 2 年出現一次。

1. The ghost of Shahriar Manzoor - 每隔 5 年出現一次。

2. The ghost of Adrian Kugel - 每隔 7 年出現一次。

3. The ghost of Anton Maydell - 每隔 11 年出現一次。

4. The ghost of Derek Kisman - 每隔 15 年出現一次。

5. The ghost of Rezaul Alam Chowdhury - 每隔 20 年出現一次。

6. The ghost of Jimmy Mardell - 每隔 28 年出現一次。

7. The ghost of Monirul Hasan - 每隔 36 年出現一次。

最後一隻鬼最特別，他來得頻率最高！

8. The ghost of K. M. Iftekhar - 每逢閏年必來！

而學生問什麼時候全部的鬼都會同時來？回答道「在西元 2148 年，所有的鬼第一次集合於此！」(即在西元 2148 年前，出題者可能還沒死。)

給定一個年份，求當年有哪些鬼會來。 

Input

測資最多 250 筆。

每一行有一個正整數 Y，Y 最多 55 位(64-bit 至多 20 位)。

當 Y = 0 結束程式。

Output

對於每組測資，先輸出 Y，根據名稱的順序輸出有哪些鬼來，格式為 "Ghost of G!!!"。

如果當年沒有任何一個鬼來，則輸出  "No ghost will come in this year"。

測資組間空一行。

Sample Input                               Output for Sample Input

2500 3000 0

2500 Ghost of Tanveer Ahsan!!! Ghost of Anton Maydell!!! 3000 Ghost of Tanveer Ahsan!!!

---

Problem setter: K. M. Iftekhar

Moderator: Shahriar Manzoor, EPS

10747 - Maximum Subsequence

給定 N 個整數，每個整數絕對值不大於 10,000，從裡面挑出 K 個數字相乘越大越好，然而這裡要求找到在最大乘積的情況下，最大總和為多少？

例如：有四個整數 4, 4, -4, -4，要求挑 2 個整數出來，有兩種方式可以得到最大值，分別是 4, 4 跟 -4, -4，但其中 4, 4 總和最大，因此答案為 8。 

Input

輸入最多 60 筆測資。 

每組測資第一行會有兩個整數 N, K (1<=K<=N<=10000)，接下來會有 N 個整數。

當 N = K = 0 結束程式。

Output

對於每組測資，輸出一行描述的總和值。

Sample Input                               Output for Sample Input

4 4 1 2 3 4 4 1 1 2 3 4 4 2 4 4 –4 –4 0 0

10 4 8

---

1195 - Calling Extraterrestrial Intelligence Again

在 1974 年，11 月 16 日星期六中午，有一則由人類撰寫的訊息經由 波多黎各 的 阿雷西博天文台 傳送給外星生命，這則訊息由 1679 bits 構成，將轉換成 23 x 73 矩形的圖示。由於 23 和 73分別都是質數，因此圖形將只會有一種轉換可能，但不保證接收到的外星生命會將此進行轉換，就算會進行轉換也有可能不正確，阿雷西博天文台的發送者非常樂觀看待。



我們也有一個非常類似的計畫，你的任務要找到最合適的長和寬來轉換圖片，而什麼是"最合適"定義如下：

對於一個整數 m  > 4，而有一個分數 a/b <= 1，而圖片面積不超過 m，而且長寬都必須要是質數，且寬長比不可小於 a/b，也不可大於 1，要最大化圖片面積。


換個方式說，給定一個整數 m，以及分數 a/b，其中 m > 4, 0 < a/b <= 1，找到一組質數 p, q 符合 pq <= m, a/b <= p/q <= 1， p*q 越大越好，輸出一組 p, q。

Input 

輸入測資不超過 2000 筆，最後一行以 0 0 0 結束。


每組測資有三個整數 m, a, b ( 4 < m <= 100000,  1 <= a <= b <= 1000 )

Output 

對於每組測資，輸出一對整數，分別對應 p, q。

Sample Input 

5 1 2
99999 999 999
1680 5 16
1970 1 1
2002 4 11
0 0 0

Sample Output 

2 2
313 313
23 73
43 43
37 53

1098 - Robots on Ice

這題的靈感來自於哈爾濱的冰雕節，在參賽隊伍回國前，北極大學(Arctic University) 的機器人將會帶領程式比賽的隊伍參觀這場慶典，他們打算從冬季結冰的湖水得到巨大的冰塊，為了監視脆弱的冰層，他們將湖畫分成網格狀，而讓機器人在湖面上運行檢查工作。

檢查工作中，將會有 3 個重要的 check-in 報到點，必須在此以無線電回報工作進度，而這三個點分別在路程的 1/4, 2/4, 3/4 的位置。為了避免與冰層表面不必要的摩擦，機器人打算從左下角 (0, 0) 出發，經過所有格子一次後，最後到 (0, 1)。如果有多種走法，而機器人盡可能每天使用不同路徑，而機器人一次只能移動四個方向一步(東西南北)。


寫一個程式，根據不同的網格大小，以及給定 3 個 check-in 點，計算有多少不同路徑種數。

例如：有一個網格 3 x 6，3 個 check-in 點順序位在 (2, 1) (2, 4) (0, 4)，機器人一開始一定在 (0, 0) 出後，經過 18 個格子後，停在 (0, 1)。而會在第 4 ( = floor(18/4)) 步走到 (2, 1)，第 9 ( = floor(2*18/4)) 步走到 (2, 4)，第 13 ( = floor(3x18/4)) 步走到 (0, 4)。

如下圖表示將會只有兩種方式：

也許會存在沒有任何的合法路徑，如 4 x 3 網格，check-in 點分別在 (2,0), (3,2), (0,2)。

Input 

輸入有多組測資，每組第一行會有兩個整數  2 <= m, n <= 8，分別表示 行(row)與列(column)。而接下來會有 6 個整數 r₁, c₁, r₂, c₂,  r₃, c₃,
(0<= r_i < m , 0 <= c_i < n for i = 1, 2, 3)
最後一組 m = n = 0  結束程式。

Output 

對於每組測資，輸出測資組編號，以及其可能的路徑總數。

並且在指定步數時抵達報到點。

$$\left \lfloor i*m*n/4 \right \rfloor \text{for i = 1, 2,3 }$$

Sample Input 

3 6 
2 1 2 4 0 4 
4 3 
2 0 3 2 0 2 
0 0

Sample Output 

Case 1: 2 
Case 2: 0

11335 - Discrete Pursuit

Robocops Inc. 是一家玩具製造公司，發明了一套機器人遊戲，遊戲中警察想要抓到小偷，整個過程在一個整數點的座標系中，而時間總是分布在離散的整數時間中：這裡時間分布於非負整數 0, 1, 2 ...

當物體移動時，取決於水平速度和垂直速度，此外可以存在有一單位的正負加速度。

更準確地來說，當在時間點 k 時，當前位置 (x, y), 速度 (u, v)，而下一秒 k+1，物體可能會出現在 (x', y') =  (x + u + ϵ, y + v + δ)，ϵ, δ ∈ {-1, 0, 1}。而在移動的過程中，速度是定值，且在 k+1 的速度為 (x'-x, y'-y)。

在時間 0 時，警察位於原點 (0, 0)，而小偷為於  (a, 0)，小偷以一個橫定速度移動，一開始警察處於靜止狀態，他的速度增加根據上述的規則。而最後警察將會在時間 k  時與小偷同一個位置。


寫一個程式，計算警察追到小偷的最少時間。

Input 

輸入有多組測資。

每組測資有三個整數，分別為 a, u, v (0 <= a <= 1000, 0 <= u, v <= 10)。
以檔案 EOF 為結束。

Output 

對於每組測資輸出一行，一個整數表示最少花費的時間。

Sample Input 

1    1 1
3            1   0

Sample Output 

2 
3

10982 - Troublemakers

每個學校班級中，總是會有那群搗蛋鬼，使得老師的生活苦不堪言。對老師來說，搗蛋鬼還算可以控制的，如果將成對的搗蛋鬼放在同一班，上課就會變得十分困難。現在有 n 個搗蛋鬼，而其中會有 m 對搗蛋鬼會造成老師上課的為害，老師決定將其拆成兩班上課，使得麻煩的事件減少一半。

寫一個程式找到分配方法，符合老師的要求。

Input

輸入第一行會有一個整數 N，表示皆下來有多少測資組。

對於每組測資第一行有兩個整數 n, m (0 <= n <= 100, 0 < m < 5000)。

接下來會有 m 行，每行上有一對整數 u, v 表示這兩個小孩在同一般即會鬧事。

搗蛋鬼的編號為 1 到 n。

Output

對於每組測資，先輸出  "Case #x:" 測資組編號，以及一個整數 L，表示其中一個班級的人數，下一行以空白隔開輸出該班級的每個搗蛋鬼的編號。

如果沒有辦法符合老師的條件，則輸出 "Impossible." 取代 L 的位置，以及一行空行。

Sample Input	Sample Output
2 4 3 1 2 2 3 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4	Case #1: 3 1 3 4 Case #2: 2 1 2

11269 - Setting Problems

設計程式競賽的題目是件困難的工作，有很多事情要做，如出題目、題目解答、測試數據以、驗證題目描述以及撰寫多組解的程式 ... 等。

在一場名為 "If you can not crash judges by solutions, crash contestants by problems" 的競賽中被賦予出題目的責任， Sultan 和 GolapiBaba 將負責出題，他們決定在這場競賽出 N 道題目，而首先由 Sultan 創建題目描述、題目解答及測試數據，而當他完成該題目時，緊接著由 GolapiBaba 負責驗正題目描述以及撰寫多組解的程式。

然而這工作耗費多時，而且不會有一個人手上同時執行多個題目的編寫，特別注意 GolapiBaba 一定要等到 Sultan 將題目完成後，才能開始動作該題的驗證工作。

寫一個程式安排順題編寫的順序，使得 Sultan 和 GolapiBaba 在最少的時間內完成所有題目。 

Input

輸入最多 50 組測資，每組測資第一行會有一個整數 N (1 <= N <= 20)，表示有多少題目。

接著會有 N 個整數 S_i (1 <= S_i <= 100, 1 <= i <= N)，表示 Sultan 完成第 i 題的工作時間。

以及會有 N 個整數 G_i (1 <= G_i <= 100, 1 <= i <= N)，表示 Golapibaba 完成第 i 題的工作時間。

Output

輸出完成所有題目的最少時間。

Sample Input	Sample Output
3 8 1 6 1 6 3 3 4 5 6 1 1 6	16 16

---

Problemsetter: Mohammad Mahmudur Rahman

Special Thanks To: Abdullah Al Mahmud

10086 - Test the Rods

National Construction and Project Centre (NCPC) 和 Bureau of Civil Engineering Works (BCEW) 是國內最具權威的測試與驗證道路的機構。

有一家名為 Get and Do 的建設公司得到在不同地點的建設專案，在這個 n 個地點的道路中，想要請 NCPC 檢測 T₁ 個道路、BCEW 檢測 T₂ 個道路，在每一個地點有不同個數的道路需要被檢測，保證所有檢測的樣本總數等於 T₁ + T₂ ，假設第 i (1 <= i <= n)地點中，有 m_i 個樣本需要被檢測，而在該地點時，對於 NCPC、BCEW 的檢測費用是看檢測的個數，如果要在此檢查 j 個樣本，對於 NCPC 花費 C_i,j,1、BCEW 花費 C_i,j,2 ，找到一種分配方式，具有最少花費。

Input

輸入有多組測資，每組第一行會有兩個整數 T₁, T₂ (1 <= T₁ + T₂ <= 300)，表示內容如上描述，接下來會有一行一個整數 n (1 <= n <= 30)，接下來會有 n 組地點資訊。

對於地點，會有一個整數 m_i (1 <= m_i <= 20)，表示該地點有多少樣品要被檢測。

而接下來會有 m_i 個整數 C_i,j,1 (1 <= j <= m_i)，接續也會有 m_i 個整數
C_i,j,2 (1 <= j <= m_i)，分別表示 NCPC、BCEW 在該地點檢測樣本個數的花費。

當 T₁ = T₂ = 0 ，結束程式。

Output

對於每組測資輸出兩行，第一行有一個整數表示最少花費測試所有的道路。

第二行輸出，輸出 n 個整數，第 i 個整數表示 NCPC 在第 i 地點的檢測個數，這裡可以暗示出 BECW 檢測了多少個。如果有多組分配方式，任何一組都可以。

在每組測資後，輸出一行空行。

Sample Input

10 12
5
5
10 30 70 150 310
10 20 40 60 180
7
30 60 90 120 160 200 240
20 60 100 130 160 200 240
4
40 60 80 100
30 70 100 120
3
60 120 180
20 50 90
3
30 70 100
30 70 100
0 0

Sample Output

580
1 3 4 0 2

196 - Spreadsheet

在 1979 年，Dan Bricklin 和 Bob Frankston 撰寫了 VisiCalc 這套電腦程式，是第一款的電子試算表(就如同 Excel)的運用，在當時是個相當大的成功，號稱是 Apple II 電腦的殺手應用軟體。現今，電子試算表(spreadsheets)仍可以在很多電腦中找到。


電子試算表的想法非常簡單，但卻相當強大。試算表的每格會有一個數值或者是公式，公式可以藉由表示法以及其他表格的數值計算得到，而文字和圖形可以用來輔助說明。


你可以寫一個簡單的試算表應用，程式會接到幾組試算表，每格會有整數數值或者是公式表示，公式中只會有計算總和，請計算所有表格中的數值，並且輸出。

由左而右開始命名每一列(column)。

Input

輸入第一行會有一個整數，表示皆下來有多少組測資。

每組測資第一行會有兩個整數 column, row ，而接下來會有 row 行，每行上會有 column個訊息，表示該格的數值或者是公式。

公式表示法為：一個等號(=)接著有數個格子的編號，以加號(+)分隔。藉此計算該格的數值。

需要去找那格的數值出來進行加總，找的時候可能也會遇到公式表示的格子。公式表示法中不會有任何的空白。

保證測資中，不會有任何環狀不可解的情況，每一個都是可以被計算出來的。

格式的命名方式，先用字母表示 column，緊接著是一個整數(範圍從 1 - 999)表示 row。
而字母的順序為：A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, ..., BZ, CA, ..., ZZ, AAA, AAB, ..., AAZ, ABA, ..., ABZ, ACA, ..., ZZZ，依序對照整數 1 到 18278。例如左上角的格子即為 A1。

Output

對於每組測資，輸出 row x column 的表格。

Sample Input

1
4 3
10 34 37 =A1+B1+C1
40 17 34 =A2+B2+C2
=A1+A2 =B1+B2 =C1+C2 =D1+D2

Sample Output

10 34 37 81
40 17 34 91
50 51 71 172

1530 - Floating Point Numbers

浮點數表示法，在電腦中採用二進制的科學記號表示法，假設這裡有台電腦使用 16-bit 的表示方法如下圖一：

 

  在最常見的 Intel 晶片中，使用的 float 指數(exponent)具有 8 bits，而尾數(mantissa)具有 23 bits，而其餘的晶片都跟圖一使用的一樣。


舉個十進制的例子 -10.375：

如果該數是正的，則 sign bit 或是 1，反之 0。而接下來 7 個 bits，(例子中使用 1000010)，表示二進制科學記號的指數次方，而處理步驟如下，得到實際次方：

計算二進制的值 1000010： 1*64+0*32+0*16+0*8+0*4+1*2+0*1 = 66.

並且減去 63，就會得到指數部分， 這種方式是為了使用負數的次方關係。

接著繼續計算尾數(mantissa)部分，假設數字表示成二進制科學記號，如下圖二，分別對應三個欄位(sign, mantissa, exponent)如下：

尾數部分指得是在小數點之後的部分(補充說明：小數點之前稱作首數)。

由於是二進制科學記號，因此首數一定為 1，除了 0 的表示法比較特別外，因此只會使用尾數記錄。

因此二進制如圖二中的可以對照十進制的科學記號：

$$-(1+2^{-2}+2^{-5}+2^{-6}) * 2^{3} = -10.375 = -1.0375 * 10^{1}$$

而在程式語言中，通常表示格式如 -1.0375e+001，使用小寫 "e" 或者大寫 "E" 表示指數次方。而當所有 bits(忽略 sign bit) 皆為 0 時，用來表示 0。

Input 

輸入有多組測資，每一行將會有長度為 16 的字串，只會由 0 跟 1 夠成。
第一個字元表示 sign bit，接下來七個字元表示 exponent，剩餘的表示 mantissa。

Output 

在程式開始前輸出一行 "Program 6 by team X"。

對於每組測資輸出一行，格式如下：

使用十進制的科學符號表示法。

在 Column 1 中，如果是正數則輸出空白，負數則輸出一個減號 "-"。

在 Column 2 中，輸出一個位數。

在 Column 3 中，有一個小數點。

在 Columns 4 - 9 中，表示 6 位的浮點數精準度。

而剩餘的部分表示指數，確切的格式請參考範例測資。

程式結束前，輸出一行 "End of program 6 by team X" 。

特別注意，內建的表示法將根據不同語言而有所不同，建議在此題不要使用。

Sample Input 

1100001001001100
0011111100000000
1011111110000000
0000000010101010
0011011111100000
1001111011100000
0101011001010101
0100011011101101
0111111111111111
1100001000101100
0000000000000000
1000000000000000

Sample Output 

Program 6 by team X
-1.037500e+001
 1.000000e+000
-1.500000e+000
 1.804180e-019
 7.324219e-003
-2.182787e-010
 1.117389e+007
 2.465000e+002
 3.682143e+019
-9.375000e+000
 0.000000e+000
 0.000000e+000
End of program 6 by team X

11566 - Let's Yum Cha!

Introduction

Yum cha 是粵語中的用來描述 "飲茶" 的術語，指吃不同的小點心，同時喝著中國茶的一種文化。飲茶是中國廣東與香港文化中的一部分，對廣東人來說，飲茶傳統上會在週末早上，全家人聚在一起聊天吃點心、喝喝中國茶，而茶是最重要的， 用來幫助消化食物。在過去，人們常去茶館飲茶，但是近幾年中，點心餐廳普及已經勝過茶館。

點 心在中文字面意思上 "點觸你的心"，點心可選擇的範圍相當廣泛，包括肉類、海鮮、甜品及水果的各種組合，點心通常藉由蒸的或者是油炸的烹飪方式，通常是用蒸籠或者是小盤子裝 著呈上來，而通常是三四件點心一盤，由於分量小，因此可以嘗試非常多樣的點心，最常見的點心有：'

·  Har gow: A delicate steamed dumpling with shrimp filling and thin (almost translucent) wheat starch skin. It is one of my favourite dim sum.

·  Siu mai: A small steamed dumpling with pork inside a thin wheat flour wrapper. It is usually topped off with crab roe and mushroom.

·  Char siu bau: A bun with Cantonese barbeque-flavoured pork and onions inside. It is probably the most famous dim sum around the world.

·  Sweet cream bun: A steamed bun with milk custard filling. It is sweet and spongy.

·  Spring roll: Consists of sliced carrot, wood-ear fungus, and sometimes meat, rolled inside a thin flour skin and deep-fried. It is crispy and delicious.
右圖即上述描述的點心，你能夠猜出是哪幾道嗎？

Description

今天有 N 位朋友一起飲茶，你和你的朋友將會付一樣的錢，而每個人(包括你) 最多付 $x，而餐廳有 K  種點心可以點，而對於一種點心，每個人將會獲得一個喜愛指數(favour index)，範圍介於 0 ~ 10 的整數。

現在將要點餐，你想要最大化自己的喜愛指數的總和，但是如果忽略朋友的喜愛點心，你將會被狠狠地痛打一頓，因此你改成要最大化平均每個人得到的喜愛指數，根據以下的公式

$$\frac{\text{Total favour value of all dishes ordered}}{N+1}$$

將這個公式計算出來的稱為 "mean favour value"，這並不表示每個人都會拿點心來吃，但是朋友總是會一起分享點心，來讓每個人都開心。

由於想要點多一點不同種的點心 ，你將不會點同一種點心大於 2 次，而且為了不浪費食物，也不會點大於 2(N+1) 盤點心，也就是每個人點 2 盤。帳單在計算時，不會只有點心的價錢，還會加上兩種基本費。 茶費: 每個人需要支付 $T 元的茶費。 10% 服務費: 在所有花費加總後，會再加收 10% 的服務費，採用無條件進位。

Input

輸入最多 25 組測資， 每組測資第一行會有四個整數 N, x, T, K，分別代表的如上描述

1 ≤ N ≤ 10, 1 ≤ x ≤ 100, 0 ≤ T ≤ 20, 1 ≤ K ≤ 100, $1 ≤ price of a dim sum ≤ $100. 

接著會有 K 行，每行表示點心的訊息，第一個整數表示點心的價錢，接著會有 N+1 個整數表示喜愛指數。

當  N = x = T = K = 0，結束程式。

Output

對於每組測資，輸出一行最大的 "mean favour value"，精準到小數點第二位。

Sample Input

3 10 5 2

6 7 5 6 9

10 9 10 10 8

0 0 0 0

Sample Output

16.00