題目 A
坦克任務
輸入檔: tank.in / 輸出檔: tank.out
你是一名駕駛坦克的優秀指揮官。你的任務是深入敵營，躲過或是摧毀敵方重重砲臺的火力，成功抵達並摧毀敵方的基地。由於戰時的油料和砲彈都是珍貴的資源，你奉命利用衛星搜集來的地形資料，找到最短的路徑，並使用最少的砲彈完成此任務。
當你在砲臺所面對的方向時，你會瞬間被擊斃，因此你無法走入砲臺所面對的區域。但你可以先繞到砲臺所背對，或側對的區域，砲轟敵方的砲臺。而砲彈是無法穿過任何障礙物的。你的坦克和砲臺所發射的砲戰，只能朝正北，正東，正西，正南發射。當敵方砲臺被你摧毀時，砲臺的殘骸會留在原地，你的坦克無法直接通過。
若你一共走了a步，發出了b發砲彈，則你的任務是使a+b為最小。
每一筆測試資料，開頭兩個數字n，m，(n, m ³ 2) 分為表示此地圖的東西向，南北向的大小。接下來有m行，表示你所在的地方的地圖，地圖由 ' '（空白） 和 '*'（星號）所組成，空白表示你可以行走的路，星號是無法通過的地形，此地圖的最外一圈必定由星號所圍成。
接下來的四個數字start_x，start_y，destination_x，destination_y分別表示你的出發位置，和敵方基地的位置，地圖中最西北角的座標為(0,0)。再來1個數字num_of_enemy (0 <= num_of_enemy <=4) 表示地圖上敵方砲臺的數目.接下來有num_of_enemy組的(x,y,d)，表示該砲臺的位置和面對的方向(方向N,E,S,W表示面對北,東,南,西)，相對於地圖上(上,右,下,左)。
最後一筆測試資料的開頭包含兩個0, 此時程式應結束。
對每一筆測試資料，輸出一行，告訴你的長官你所預計花費的行動數
"MINIMAL STEPS: n." 其中n是行動數: a+b (走了a步+發出b發砲彈)
若你發現你已受困，則輸出"IMPOSSIBLE."
6 6
******
*
*
*** *
**** *
*
*
******
1 1 1 4
1 4 1 S
6 6
******
*
*
**** *
**** *
*
*
******
1 1 1 4
1 4 4 N
0 0
MINIMAL STEPS: 10.
IMPOSSIBLE.
題目 B
錢幣王國
輸入檔: money.in / 輸出檔: money.out
錢幣王國有著一個以發行各種不同的錢幣為樂的國王，在他的國度裡，竟然有10000種不同的錢幣流通著！分別編號為1,2,3,4,......,9999,10000。然後國王並沒有公佈不同錢幣的幣值，只說了：1號和2號錢價值相當，而3號錢可以兌換1個1號錢和1個2號錢，4號錢可以兌換1個2號錢和1個3號錢，餘此類推 (n號錢可以兌換1個n-1號錢和1個n-2號錢, 3<=n<=10000)。
有一天，國王宣佈要找出誰是國家中最富有的人，可是錢幣的種類實在太多了，這個國家的人民為了比較誰的錢多誰的錢少而頭痛不已著. 你是一個聰明的旅行者，當你旅行到這個國度，見到人民的苦惱，便決定要幫助人民比較彼此的財產。
每一筆資料包含了兩個人的財產清單財產清單包含了不同的錢幣號碼和擁有的數目，寫成以下的格式：
x1 a1 x2 a2
x3 a3 ..... xm am 0
其中 1 <= x1 < x2 < x3 < ...< xm <=10000，x為錢幣的編號， ai 為此人擁有這種xi 錢幣的數量(0 < ai < 100000, 1 <= i <= m)。每人所擁有的錢幣種類不會超過2000種 (m<=2000)。
每個人的財產清單以0表示結束 (由於一個人擁有的錢幣種類可能很多，因此財產清單可能不只1行，請一律讀到0為止)。例如：
2 1 3 1 5 1 0 7 1 0
表示第1個人有1個2號錢, 1個3號錢, 1個5號錢, 而第2個人有1個7號錢。
測試資料的檔尾含有1個-1，讀到-1，表示測試資料全部結束。
每一筆測試資料有對應的一行輸出，輸出"MORE"或"LESS"，分別表示第1個人的財產多於或少於第2個人，當兩人財產相等時，請輸出"EVEN"。
2 1 3 1 5 1 0
7 1 0
3 5 0
3 1 6 1 0
1 145 0
12 1 0
-1
LESS
EVEN
MORE
題目 C
直線
輸入檔: line.in / 輸出檔: line.out
在平面上畫直線，兩條直線之間有幾種關係：
1. 重疊：
例如 x+y=1 與 2x+2y=2
2. 平行：
例如 x+y=1 與 x+y=2
3. 相交：
例如 x+y=1 與 x-y=1 交於點(1,0)
對於相交的直線，會有一個交點，很多直線可能交在同一個點上，例如 x+y=1 與 x-y=1 與 x+2y=1 均交於點 (1,0)
給定一些平面上的直線(不超過 256 條)，請寫一個程式算出它們「相交」所產生的相異交點數量。
提示：在此題中，重疊的兩直線之交點數目定義為0。因此您可以適當的選擇不要處理它們。
輸入檔是由許多組平面上的直線組成的。每一組資料的第一行會有一個整數 N
(1 <= N <= 256)，以下的 N 行每行各代表一條直線，它由三個整數a b c 組成，代表直線 ax+by=c
這三個整數都介在 -1000 到 1000 之間，而且 a 和 b 不會同時為 0
輸入檔的最後一行會有一個單獨的 0，這筆資料不用處理。
對每一組輸入檔內要處理的資料，輸出一行內含一個整數，代表資料內的直線相交所產生的相異交點數量。
3
1 1 1
1 -1 1
1 2 1
2
1 1 1
2 2 2
0
1
0
題目 D
翻譯
輸入檔: trans.in / 輸出檔: trans.out
宇宙中很多不同的語言可以互相翻譯，舉例來說，中文的「我」，英文是「I」，而德文是「Ich」，然而，由於各種語言的來源與演進不同，不同的語言之間有的比較相近，有的就比較不一樣，例如中文與台語的相似性，就遠比中文和火星話的相似性高不少。
為了克服星際旅行的困難，大家都會隨身帶著一台智慧型翻譯機。不過，由於翻譯機的設計，它只內建有某些語言的翻譯字典。例如某型的翻譯機，可能只有「中文à台語」與「英文à中文」的翻譯字典。於是對於一個到台灣南部旅行的英國人來說，如果他想把英文翻成台語，智慧型翻譯機會先從英文翻成中文，再從中文翻成台語，再輸出結果。大部份的時候，翻譯機可能有多種選擇，例如它也可能可以先把英文翻成日語，再把日語翻成台語，或把英文翻成火星話，再把火星話翻成中文，再把中文翻成台語。這種時候，翻譯機希望選擇一個失真度最小的方式來完成它的任務。
為了簡化問題，我們把這個宇宙中所有的語言用一個大寫英文字母來表示，也就是說，最多有 26 種。翻譯的方式用一個字串來代表，例如從AàBàDàC 就簡寫成 ABDC。
失真度是如何計算的呢？翻譯機把語言之間的相似性定義為一個 1 到 99 間的整數，數字越大代表越接近。這個定義是對稱的，也就是說，
相似性(A, B) = 相似性(B, A)
而一個翻譯方式的失真度，則定義為
100 - 最小值(翻譯過程所經過的語言間的相似性)
舉例來說，如果
相似性(A, B) = 90
相似性(B, D) = 80
相似性(D, C) = 85
則翻譯方式 ABDC 的失真度就是
100 - 最小值(90, 80, 85) = 20
於是翻譯機就可以計算使用不同方式的失真度來決定應該怎麼樣翻譯比較好。
給定各種語言之間的相似性，與翻譯機內建的可用的翻譯字典，假設您是說 A 語言的人，要去星際旅行，請您寫一個程式，列出所有這台翻譯機可以翻成的語言，與翻成這些語言的失真度。
輸入檔的前面 25 行，第 k 行會有 26-k 個數字，這行的第 m 個數字代第 k 種語言和第 m+k 種語言的相似度。舉例來說，如果第一行是
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25
就代表
相似度(A, B) = 1
相似度(A, C) = 2
依此類推
而如果第二行是
100 99 98 97 96 95 94 93 92 91 90 ……
就代表
相似度(B, C) = 100
相似度(B, D) = 99
依此類推…
輸入檔後面的部份是由許多組資料所組成的，每組就是一台翻譯機。每組資料的第一行會是一個整數 L (1 <= L <= 650)，代表這台翻譯機內建的字典數量。底下的 L 行每行由兩個不同的大寫英文字母組成，以空白鍵間隔。例如：
A C
代表翻譯機內建有 A 翻成 C 的字典，請特別注意字典只能單向使用。
輸入檔的最後一行會是一個整數 0，這組資料不用處理。
對於輸入檔中的每組資料，輸出檔要有一組相對應的輸出。若 A 能翻譯成 N 種語言(不包含 A 本身)，則輸出 N+1 行，第一行形如
Dataset X
此處 X 是一個整數，由 1 起算，代表第幾組資料。
後面 N 行每行有一個大寫英文字母，和一個整數，以空白鍵分隔。這 N 行的大寫英文字母代表所有可以從 A 語言翻譯成的語言，不包括 A 語言本身。並且依字母順序由小到大排列，而整數則代表翻成該語言之最小失真度值。
提示：隨著翻譯機的不同，N 的值會介在 0 和 25 之間。
60 30 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10
50 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10 10
10 10 10 10 10 10 10 10 10 10 10
10 10
10 10 10 10 10 10 10 10 10 10 10
10
10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10
10 10 10 10 10 10 10
10 10 10 10 10 10
10 10 10 10 10
10 10 10 10
10 10 10
10 10
10
3
A B
B C
A C
0
Dataset 1
B 40
C 50
題目 E
過橋
輸入檔: bridge.in / 輸出檔: bridge.out
台大聯誼會舉辦活動，邀請歷屆校友組成海外旅行團。一日，因為交通因素，眾人來到目的地時已經夜深，只有一盞油燈照明，並且要過一條窄橋才能到河對岸的旅館。由於團員老少體能不一，過橋所需的時間不盡相同，走得快的年輕人必須放慢腳步，和同行的長輩一起使用油燈到達彼岸，若是一趟走不完所有的人，則要派一個人把油燈提回來。油燈的燃料有限，若是過橋的先後順序不能妥善安排，可能人還沒走完燈就熄了。請你根據輸入檔的資料，計算出妥善的安排下，最快多少時間所有團員可以安全過橋。
輸入檔案中有多組測試資料。每組測試資料的第一行有兩個整數n和m，表示總共有n個人過橋，一次最多只能走m個人，且1 £ n, m £ 16。第二行有n個正整數，分別表示每個人過橋所需的時間，且不大於1000。在檔案的最後，以兩個0表示結束。各組測試均有解，即m等於1時，n也會等於1。
每一組測試資料，都輸出一個整數，表示團員全數過橋所需的最少時間。請每行輸出一組測試資料的答案。
1 1
1
3 2
1 2 3
5 2
1 3 6 8 12
0 0
1
6
29
我們可以證明加入以下的條件，並不會增加全數團員過橋的時間︰
1. 到達對岸後，僅派一個人把燈提回來。
2. 不論往那一個方向，若派出的人數小於m，這些人一定是該岸邊走得最快的。