259 - Software Allocation

學校的計算機中心有十台電腦(以0~9作編號)，所有電腦只支援單一行程。電腦上共有26個應用程式可供執行(分別以A~Z表示)，下面會說明哪些電腦可以執行哪些應用程式。

每天早上，使用者會帶著他們當天需要執行的應用程式到計算機中心，可能會有兩位使用者帶相同的應用程式，但此時就需要兩台不同的電腦分別執行該程式。

計算機中心的櫃台會收集當天所有使用者的應用程式，並整理一份各個應用程式能在哪幾台電腦執行的清單，並將每個應用程式指派給電腦去執行，注意，每台電腦一天只能執行一個應用程式。

櫃台所整理的清單格式如下：

1. 一個大寫的字元A...Z表示一種應用程式。
2. 一個位數的數字1...9表示該應用程式有幾位使用者需要執行。
3. 一個空白字元。
4. 一或多個位數的數字0~9表示該應用程式可在哪些電腦上執行。
5. 一個表示該列結束的分號 ;。
6. 換程符號。
   

Input

輸入會有多組測試資料，每組資料以一列空行隔開，且會有一到多列清單資訊，請你寫程式判斷該組資料是否有足夠的電腦來執行，如果足夠的話，請輸出一組可能的配置方式。

Output

每組測試資料輸出一列，其格式如下：

• 若存在一組可能的配置方式，請輸出十個{'A'...'Z', '_'}的字元，分別依序表示這十台電腦上分別執行哪個應用程式，以 _ 表示該台電腦並不需要執行任何應用程式。
• 一個 ! 字元表示找不到任何一種可能的配置方式來執行所有應用程式。
  

Sample Input

A4 01234;
Q1 5;
P4 56789;

A4 01234;
Q1 5;
P5 56789;

Sample Output

AAAA_QPPPP
!

原文出處

222 - Budget Travel

本題請你計算開車從一地開往另一地最少所需的費用，旅程沿途會有一些加油站，每個加油站的油價不儘相同。

為了簡化問題，我們定義駕駛者的行為如下：

• 當油箱的油超過一半的時候，駕駛者不會停下來加油，除非剩下的油無法讓他到達下一個加油站(或終點)。
• 當駕駛者停下來到加油站加油的時候，他一定會把油加滿。
• 當駕駛者停下來來加油的時候，他會額外多花2塊錢來買些零食或其他什麼的。
• 駕駛者不需要為油箱保留一個「安全的額度」，即到達下一個加油站前都不需要多餘的油。
• 駕駛者一開始會把油箱加滿。
• 每次加油的油錢都會做四捨五入進位到幾分錢(100分錢等於1塊錢)。

請你寫一個程式計算駕駛者一路上最少需要花多少錢在油料與零食上。

Input

輸入會有多組測試資料，每組資料格式如下：

第一列：會有一個實數表示終點離起點的距離。

第二列：有三個實數與一個整數：

• 第一個實數表示油箱的容量。
• 第二個實數表示車子每英哩的油耗。
• 第三個實數表示車子於起點加油的油價。
• 以一個整數表示沿途有多少加油站。

接下來每一列會有一個加油站的資訊，每列有兩個實數：

• 第一個實數表示加油站與起點的距離。
• 第二個實數表示該加油站每加侖的油價(單位為一分錢=0.01元)。

每個數值皆為正值。加油站出現的順序以距離起點的距離由小到大排列，且不會大於終點的距離。不會存在無法到達終點的情況。當出現負值表示測試資料結束。

Output

請參考範列資料輸出每組資料編號及最少所需的費用，費用請包含於起點加油所需的花費。

Sample Input

475.6
11.9 27.4 14.98 6
102.0 99.9
220.0 132.9
256.3 147.9
275.0 102.9
277.6 112.9
381.8 100.9
516.3
15.7 22.1 20.87 3
125.4 125.9
297.9 112.9
345.2 99.9
-1

Sample Output

Data Set #1
minimum cost = $27.31
Data Set #2
minimum cost = $38.09

原文出處

296 - Safebreaker

猜數字的遊戲中，首先選擇四個位數的數字(0000 ~ 9999)，遊戲的玩法是在提供一些提示的情況下猜中數字，例如玩家A選擇數字3321，玩家B第一次以任一數字作猜測，例如猜1223，此時玩家A提供此猜測的正確度的提示，提示包含兩個數字，第一個數字表示完全猜對幾個位數(此例中完全猜對第三位數為2)，第二個數字表示僅猜對數字但位置不對的個數(此例中為1與3)，提示以"1/2"表示。

本題給定一組猜測的數字及其提示，請你找出該數字。

Input Specification

輸入的第一列有一個整數N表示測試資料的組數，每組測試資料的第一列有一整數G(0 <= G <= 10)表示猜測的個數，每次猜測包含8個字元：四位數的數字、一個空白字元、完全正確的個數、/、猜對數字但位置不對的個數。

Output Specification

請對每組測試資料輸出下列其中一種答案：

• impossible：表示無解。
• XXXX：表示有唯一一解的答案。
• indeterminate：表示有多組可能的解。
  

Example Input

4
6
9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0
1
1234 4/0
1
1234 2/2
2
6428 3/0
1357 3/0

Example Output

3411
1234
indeterminate
impossible

原文出處

288 - Arithmetic Operations With Large Integers

本題是關於大數運算，數值最大到1000位，運算僅包含加法、減法、乘法、指數次方。 指數項的底數為正數且小於10，而指數部份則為正值。

輸入資料為合法的運算式，不會出現括號，但一般的先乘除後加減的法則是存在的。

以兩個*符號表示指數。

12345678 * 129876 + 2**1993為合法的運算式，12345678 * 129876 + 12**1993為不合法的運算式，因為指數項的底數大於9。

Input

輸入會有多組測試資料，每組運算式一列，其格式為： n op n { op n}，n 表示正的十進位數，且最多1000位，op 表示 +, -, *, ** 其中一種。每個運算式最多有100個運算元，且不會有空白字元或其他不合法的字元出現在運算式裡面。

Output

請每組一列輸出每個運算式的答案，每個答案最長不會超過3000個字元。

Sample Input

12345678*129876+2**1993

Sample Output

896977105683011347056900938420064050017435704756793125373158388145129891712789307700515223684770523373785909874208955291755561688174261977676508872005197801086953040197752187505381087095625350558038492109870986287356370809737409093338414265941143390397695285610643740694879918793932122262001282984143224073001319601441082075018589725061828585163552941409601583724270514300953188533095947591884905338415676554651534516617357655143781579373852994152663198702360093129335607684294312805938140290754926427776409574872859496315224893901812925850900592061583009183090068756428459147015355107518672556877720


原文出處

280 - Vertex

在一個有向圖中，從一個特定的起點開始走訪，請找出所有無法拜訪的節點。

有向圖的節點個數為 n (1 <= n <= 100)，其節點依序編號為1 ~ n，並以 p -> q 表示由 p 到 q 的邊。

節點 r 可從 p 拜訪，表示存在一 p -> r 的邊，或是存在一節點 q 使得 q 可從 p 拜訪且 r 可從 q 拜訪。

Input

輸入會有多組測試資料，每組資料會給定一有向圖，及一些起始節點。

有向圖的第一列會給定一個整數 n 表示節點數，接下來會有許多列，每列有許多整數， 令每列的第一個整數為 i ，且之後的整數為 j... k，表示存在邊 i -> j, ..., i -> k，每列的最後一定以 0 作為結束，i 滿足 1 <= i <= n，且每列的 i 之值不會相同。圖的最後一列以一個 0 表示結束，在圖的定義之後會有一列整數，第一個整數表示該列之後有多少個整數，每個整數表示起始節點編號，請對所有起始節點輸出其所有不可及的節點。當 n = 0 表示測試資料結束。

Output

請對每組測試資料輸出每一個起始節點出發的不可及的節點，每組一列，每列的第一個整數表示該列有幾個不可及節點。

Sample Input

3
1 2 0
2 2 0
3 1 2 0
0
2 1 2
0

Sample Output

2 1 3
2 1 3

原文出處

276 - Egyptian Multiplication

埃及的數字系統與阿拉伯數字系統並不相同，埃及數字以不同符號表示一，十，佰，仟，萬，十萬，佰萬，仟萬，本題以ASCII字元表示如下：

• | 表示一(注意 | 並不同於 1)
• n 表示十。
  
• 9 表示佰。
  
• 8 表示仟。
  
• r 表示萬。

(本題不討論大於99,999的數目)

數字的表示方式很簡單，以4,023為例，共有3個一、兩個十、零個佰、四個仟，表示成 ||| nn 8888。位數為零的符號不需要寫出來。40,230的埃及數字寫成：nnn 99 rrrr。

對於兩個數字 a 與 b 的乘法而言，埃及數字的乘法運算式以兩欄數字表示，第一列的左欄數字為 |，右欄數字為 a，接下來每一列兩欄的數字為上一列的兩倍，所以下一列可簡單地將上一列的每一組數字乘兩倍而得到，且當數量大於九時作進位。左欄的數字不斷乘上兩倍，且到不超過 b 為止。從左欄的數字中選擇部份的數字做加總使之等於 b，並在被選擇的數字後打上星號(*)，將所有打上星號的每一列的右欄數字加總即為 a * b 的值。

下列顯示 483 * 27 的運算過程：

| *                             ||| nnnnnnnn 9999
|| *                            |||||| nnnnnn 999999999
||||                            || nnn 999999999 8
|||||||| *                      |||| nnnnnn 99999999 888
|||||| n *                      |||||||| nn 9999999 8888888
The solution is:  | nnnn 888 r

總和為 | nnnn 888 r，為下列埃及數字的總和：

||| nnnnnnnn 9999
|||||| nnnnnn 999999999
|||| nnnnnn 99999999 888
|||||||| nn 9999999 8888888

本題請你寫一個程式來作埃及數字的乘法運算。

Input

測試資料兩列一組，分別以埃數數字表示兩個大於零的數字。以空行表示測試資料結束。

Output

請對每組測試資料輸出埃及數字的乘法運算過程，左欄請靠左輸出，每個數字的每個位數符號之後皆必須有一個空白字元，包含最後的位數。請以空白字元填滿左欄的輸出，並在第35個字元位置開始輸出右欄的數字。

請參考範例資料格式，本題的測試資料可以保證不會有字元重疊的問題，請在每組的最後輸出"The solution is: "並接著以埃及數字輸出其乘數(請取除100000的餘數)。

Sample Input

||
||
||| 
|||| 
nnnnnn 9 
||| n 
n 
9 
||| 
8

Sample Output

|                                 || 
|| *                              |||| 
The solution is: ||||
|                                 ||| 
||                                |||||| 
|||| *                            || n 
The solution is: || n 
| *                               nnnnnn 9 
||                                nn 999 
|||| *                            nnnn 999999 
|||||||| *                        nnnnnnnn 99 8 
The solution is: nnnnnnnn 88 
|                                 n 
||                                nn 
|||| *                            nnnn 
||||||||                          nnnnnnnn 
|||||| n                          nnnnnn 9 
|| nnn *                          nn 999 
|||| nnnnnn *                     nnnn 999999 
The solution is: 8 
|                                 ||| 
||                                |||||| 
||||                              || n 
|||||||| *                        |||| nn 
|||||| n                          |||||||| nnnn 
|| nnn *                          |||||| nnnnnnnnn 
|||| nnnnnn *                     || nnnnnnnnn 9 
|||||||| nn 9 *                   |||| nnnnnnnn 999 
|||||| nnnnn 99 *                 |||||||| nnnnnn 9999999 
|| n 99999 *                      |||||| nnn 99999 8 
The solution is: 888

原文出處

260 - Il Gioco dell'X

有一個名為"Il Gioco dell' X"的遊戲，其玩法是在N x N的板子上(N >= 2)，由黑白雙方輪流下子，雙方要使自已的棋子鋪出一條由一邊連到對邊的路徑，先達成者得勝。雖然盤棋大小為N x N，但並非正方形，而比較像是菱形。在棋盤中第 i 列第 j 欄的位置定為(i, j) (1 <= i, j <= N)，與(i, j)相鄰的點為：

( i-1 , j-1 ) , ( i-1 ,  j  ) 
(  i  , j-1 ) , (  i  , j+1 ) 
( i+1 ,  j  ) , ( i+l , j+1 )

請注意這些位置不能超出棋盤外。

黑子必須要從第1列連到第N列，白子要從第1欄連到第N欄。

數學上已經證明並不存在雙方平手的可能性，由於測試資料一定是處於棋盤被填滿的狀態，所以一定會有一方是贏家，請你找出誰才是贏家。

Examples:

下圖有兩個例子，左圖白子勝，右圖黑子勝。

Input

輸入有多組測試資料，每組的第一列為整數N，表示接下來N列每列有N個字元，為一個棋盤(2 <= N <= 200)，棋盤上的每個字元僅包含{'b', 'w'}，分別表示黑子與白子。黑子與白子的棋子數目最多相差一子，且棋盤上必被黑子或白子所填滿。當N=0表示測試資料結束。

Output

每組測試資料請輸出一列，請輸出測試資料編號，並以B表示黑子勝，以W表示白子勝。

Sample Input

4
bbwb
wwbw
bbwb
bwww
4
bbwb
wwbw
bwwb
wwbb
0

Sample Output

1 W
2 B


原文出處

255 - Correct Move

在一個正方形棋盤上有64個位置，並被付予0~63的編號，如下圖所示。在棋盤上放置兩個棋子，一為國王一為皇后，國王與皇后所在的位置被稱為「狀態」 (state)，只要雙方不在同一個位置就被視為「合法的狀態」，國王與皇后交互移動，國王可以在垂直或水平的方向移動一格，但不能移動到皇后所在的位置，皇后可在垂直或水平的方向上移動一到多格，且不能移動到與國王相遇(即國王所在的位置及其後的位置)，以上所有的移動方式稱為「合法的移步」。請注意棋子皆不能作對角線的移動。

例如我們將國王放置在17的位置，將皇后放置在49的位置，如下左圖所示。國王合法的移步方式為9, 16, 18, 25，皇后合法的移步方式為25, 33, 41, 48, 50, 51, 52, 53, 54, 55, 57。我們此時再引入一個限制：一個棋子不能移動到另一個棋子可移動的範圍，一個合法的移步方式只要滿足這項限制則稱為「允許的移步」，如下左圖中，國王與皇后的允許的移步分別以()與()表示。下右圖中國王無法做任何移步(稱為被鎖死的)。

 \ 

本題請你檢查皇后的移步方式是否正確。

Input

輸入有多組測試資料，每組一列，每列有三個整數，分別介於0~63，並以一個空白字元隔開。前兩個整數分別表示國王與皇后的位置，第三個整數表示皇后移動到哪個位置，你的程式必須判斷：

• 初始位置是否是「合法的狀態」
• 皇后的移步是否是合法的。
• 皇后的移步是否是被允許的。

除此之外，若滿足以上三種情況，你的程式還需要進一步判斷皇后移步之後，國王是否處於鎖死的狀態。

Output

請對每組測試資料輸出以下其中一種情況：

• Illegal state
• Illegal move
• Move not allowed
• Continue
• Stop

"Illegal state"表示給定的狀態是不合法的，即兩棋子在同一位置。
"Illegal move"表示給定的狀態是合法的，但皇后的移步是不合法的。
"Move not allowed"表示狀態與皇后的移步都是合法的，但移步卻是不被允許的。
"Continue"與"Stop"表示狀態合法，且皇后的移步亦是被允許的，若國王可移動到下一個位置，請輸出"Continue"，若被鎖死請輸出"Stop"。

Sample Input

 17 17 49
 17 49 56
 17 49 9
 17 49 17
 17 49 25
 17 49 33
 17 49 41
 17 49 49
 56 48 49

Sample Output

Illegal state
Illegal move
Illegal move
Illegal move
Move not allowed
Continue
Continue
Illegal move
Stop


原文出處

247 - Calling Circles

電信公司提供一種稱為「朋友圈」的電信服務，由你提供一組最常聯絡的朋友列表，當你撥打給這些朋友的時候會以較低的費率計費。

LibertyBell Phone Co.最近提供一種更好的服務方案，他們自動幫你找出朋友圈。原理是這樣的，首先他們會記錄所有通話記錄，包含誰打給誰。

例如Ben打給Alexander，Alexander打給Dolly，Dolly打給Ben，則他們會在同一個朋友圈內。若Dolly打給 Benedict，而Benedict也打給Dolly，則Benedict會加進Ben, Alexander, Dolly這三人的朋友圈。若Alexander打給Aaron，但Aaron不打給Alexander或Ben或Dolly或Benedict的任一人，則Aaron不在這朋友圈裡面。

給定一組人的通話記錄，請你找出所有朋友圈。

Input

輸入包含一到多組測試資料，每組資料的第一列會有兩個整數 n, m，n 表示資料中的人數(n <= 25)，而接下來會有 m 列，每列為一組通話記錄，表示誰打給誰，人名中間以一個空白字元隔開，不同人不會有相同的名字，且區分大小寫，姓名僅包含英文字母且長度不超過25個字元。

例如Ben打給Dolly會以下列表示：
Ben Dolly

當 n = m = 0表示測試資料結束。

Output

請參考範例資料格式輸出每組答案，每組朋友圈請獨立以一列表示，朋友圈的人名可以以任意順序輸出，並請以逗號與一空白字元隔開。每組測試資料之間亦請以一列空行隔開。

Sample Input

5 6
Ben Alexander
Alexander Dolly
Dolly Ben
Dolly Benedict
Benedict Dolly
Alexander Aaron
14 34
John Aaron
Aaron Benedict
Betsy John
Betsy Ringo
Ringo Dolly
Benedict Paul
John Betsy
John Aaron
Benedict George
Dolly Ringo
Paul Martha
George Ben
Alexander George
Betsy Ringo
Alexander Stephen
Martha Stephen
Benedict Alexander
Stephen Paul
Betsy Ringo
Quincy Martha
Ben Patrick
Betsy Ringo
Patrick Stephen
Paul Alexander
Patrick Ben
Stephen Quincy
Ringo Betsy
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Quincy Martha
0 0

Sample Output

Calling circles for data set 1:
Ben, Alexander, Dolly, Benedict
Aaron

Calling circles for data set 2:
John, Betsy, Ringo, Dolly
Aaron
Benedict
Paul, George, Martha, Ben, Alexander, Stephen, Quincy, Patrick
原文出處

232 - Crossword Answers

猜字謎的遊戲包含一個由黑與白區塊所組成的棋盤方格，另外提供兩列單字。其中的一列為棋盤中由左到右白色方格中橫列的單字，另一列為由上到下白色方格中直行的單字。為了解出猜字謎遊戲，玩家從所提供的兩列單字從填入白色方格中。

為了找出棋盤方格中的所有單字，首先必須對所有「適合的(eligible)」白色方格依序做編號，其左方或上方為「黑色方格或沒有方格」的所有白色方格稱為「適合的」，並將所有適合的白色方格由上到下，由左至右依序做編號，如下圖所示：

猜字謎中的「橫列單字」為橫列中由左到右的每一組單字，「直行單字」為直行中由上到下的每一組單字。

請你寫一個程式從已經解決的字謎遊戲中找出所有「橫列單字」與「直行單字」並以編號大小排列輸出。

Input

每組測試資料的第一列有兩個整數 r 與 c (1 <= r, c <= 10)，r 表示猜字謎遊戲的列數，c 表示行數。接下來會有 r 列，每列 c 個字元，以英文字母表示被填滿的白色方格，以 * 表示黑色方格。以一列 r = 0 表示測試資料結束。

Output

請對每組測試資料輸出資料編號(puzzle #1, puzzle #2, ...)，接著輸出「橫列單字」與「直行單字」，橫列單字前請輸出一列"Across"，直行單字前請輸出"Down"，每個單字請以第一個字母的編號依序輸出，請參考測試資料。

請在每組測試資料之間以一列空行隔開。

Sample Input

2 2
AT
*O
6 7
AIM*DEN
*ME*ONE
UPON*TO
SO*ERIN
*SA*OR*
IES*DEA
0

Sample Output

puzzle #1:
Across
  1.AT
  3.O
Down
  1.A
  2.TO

puzzle #2:
Across
  1.AIM
  4.DEN
  7.ME
  8.ONE
  9.UPON
 11.TO
 12.SO
 13.ERIN
 15.SA
 17.OR
 18.IES
 19.DEA
Down
  1.A
  2.IMPOSE
  3.MEO
  4.DO
  5.ENTIRE
  6.NEON
  9.US
 10.NE
 14.ROD
 16.AS
 18.I
 20.A

原文出處

227 - Puzzle

有一種拼圖以 5x5 大小的方格所構成，其中包含24個相同大小的小方塊，小方塊上分別印有一個英文字母。由於只有24個小方塊，所以會有一個位置是空的，在空格四週的方塊可以移到空格中。請參考下圖。

左圖經過六次的移動可變為右圖的形式，步驟如下：

1. 空格上方的方塊D向下移動。
2. 空格右方的方塊O向左移動。
3. 空格右方的方塊K向左移動。
4. 空格下方的方塊L向上移動。
5. 空格下方的方塊B向上移動。
6. 空格左方的方塊A向右移動。
   

給定方格一開始的佈局及移動步驟，請輸出方格最後的形式。

Input

輸入會有多組測試資料，每組資料的前五列每列有五個字元，表示方格一開始的佈局，以空白字元表示空格。第六列開始為移動步驟，每個步驟一個字元，以A表示空格上面的方塊向下移動；B表示空格下面的方塊向上移動；R表示空格右邊的方塊向左移動；L表示空格左邊的方塊向右移動。注意可能會有不合法的移動方式(就算所有移步僅包含ABRL，也可能會有不合法的移步)，若出現不合法的移步，則視為該組資料無解。移步可能會有許多列，並以 0 表示移步結束。當出現字元 Z 表示測試資料結束。

Output

請在每組測試資料輸出資料編號(Puzzle #1, Puzzle #2...)，若無解請輸出"This puzzle has no final configuration."，否則請輸出方塊最後的佈局，每列的字母以一個空白字元隔開，請參考範列輸出。

請每組輸出之間以一列空行隔開。

Sample Input

TRGSJ
XDOKI
M VLN
WPABE
UQHCF
ARRBBL0
ABCDE
FGHIJ
KLMNO
PQRS 
TUVWX
AAA
LLLL0
ABCDE
FGHIJ
KLMNO
PQRS 
TUVWX
AAAAABBRRRLL0
Z

Sample Output

Puzzle #1:
T R G S J
X O K L I
M D V B N
W P   A E
U Q H C F

Puzzle #2:
  A B C D
F G H I E
K L M N J
P Q R S O
T U V W X

Puzzle #3:
This puzzle has no final configuration.

原文出處

218 - Moth Eradication

本題請你找出「凸包」的點集合，並依序列出，請參考下圖：

Input

輸入會有多組測試資料，每組資料的第一列有一個整數 n 表示所有點的個數，接下每一列會給定各點的(x, y)座標，不會有重複的點在相同位置。當 n = 0 表示測試資料結束。

Output

每組測試資料請輸出三列，分別為：

• 第一列：測試資料編號(Region #1, Region #2...)。
• 第二列：請以順時間方向依序輸出所有點，以任何一點開始皆可，注意輸出的第一點與最後一點必須一樣。每點的格式為(x,y)，請輸出到小數點後一位。每個點之間需以 - 隔開。
  
• 第三列：請依範列資料格式輸出該路徑的長度，請輸出到小數點後兩位。
  

Sample Input

3
1 2
4 10
5 12.3
6
0 0
1 1
3.1 1.3
3 4.5
6 2.1
2 -3.2
7
1 0.5
5 0
4 1.5
3 -0.2
2.5 -1.5
0 0
2 2
0

Sample Output

Region #1:
(1.0,2.0)-(4.0,10.0)-(5.0,12.3)-(1.0,2.0)
Perimeter length = 22.10

Region #2:
(0.0,0.0)-(3.0,4.5)-(6.0,2.1)-(2.0,-3.2)-(0.0,0.0)
Perimeter length = 19.66

Region #3:
(0.0,0.0)-(2.0,2.0)-(4.0,1.5)-(5.0,0.0)-(2.5,-1.5)-(0.0,0.0)
Perimeter length = 12.52

原文出處

213 - Message Decoding

有一種加密演算法會將密文編碼成兩個部份，第一個部份稱為檔頭(header)，為一列有多個字元，第二部份為某種形式的資訊，用來做為解碼之用，本題請你對資訊做解碼。

此加密演算法的核心觀念是由一組以0或1所組成的鍵值(key)而來：
0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, ..., 1101, 1110, 00000, ...

此序列中的第一個鍵值長度為1，接下來長度為2的鍵值有三個，再接下來長度為3的鍵值有七個，長度為4的鍵值共有15個。相同長度的鍵值依序由二進制的0開始每個遞增1而來，但不包含所有位數皆為1的情況。

這些鍵值依序對應到檔頭的每個字元，即鍵值"0"對應到檔頭的第一個字元，"00"對應到第二個字元，第 k 個鍵值對應到第 k 個字元。例如若檔頭如下：

AB#TANCnrtXc
則0對應到A，00對應到B，01 = #，10 = T，000 = A, ..., 110 = X，0000 = c。

被編碼的訊息僅包含字元'0'與'1'及換行字元，換行字元可被忽略。訊息可被區分為許多區段，每一區段的頭三個位數以二進制表示接來下該區段鍵值的長度，例如若一區段的頭三個位數為010，表示該區段接下來的每一個鍵值長度皆為2(00, 01, 10)，該區段的最後以連續多個1表示結束，其連續多個1的個數與該區域的鍵值長度相同，所以鍵值長度為2的區段是以11做結尾。整個編碼訊息是以000 表示結束(即為區段的鍵值長度為0時)。將每個鍵值從檔頭資訊中做一對一的對應之後可解碼得到原文。

Input

輸入會有多組測試資料，每組資料會有一列檔頭及一段加密密文，密文可能會分成許多列。檔頭的長度一定不會大於所有不同鍵值的個數(而最大鍵值長度被限制在二進制的111)。若檔頭內有重複出現的字元，表示有不同的鍵值會對應到相同的字元。密文僅包含'0'或'1'字元，其格式如上所述。

換行字元可能出現在密文中的任何地方，你不應該視換行字元為密文的一部份。

Output

請對每組測試資料輸出一列，表示解密後的訊息，每列之間不能有空行。

Sample input

TNM AEIOU
0010101100011
1010001001110110011
11000
$#**\
0100000101101100011100101000

Sample output

TAN ME
##*\$


原文出處

209 - Triangular Vertices

請參考下圖由點與邊所構成的三角型結構：

我們對此圖形的所有點作編號，由1開始，從上到下、由左至右依序進行編號，並選擇一些點來構成幾何圖形，例如點{1, 2, 3}與{7, 9, 18}分別構成一個三角形，{11, 13, 26, 24}與{2, 7, 9, 18}分別構成四邊形，而{4, 5, 9, 13, 12, 7}與{8, 10, 17, 21, 32, 34}分別構成六角形。

本題請你寫一個程式分別對一組點集合判斷該點集合是否可構成：三角形或四邊形或六角形，且必須滿足下列兩個條件：

• 圖形的每一個邊必須與上圖的邊重疊。
• 所有邊長必須相等。
  

Input

輸入會有多組測試資料，每組資料一列，每個點以其編號表示，且每列最多有六個點，編號的範圍介於1 ~ 32767。

Output

請參考範例資料輸出每組資料的答案，共有四種可能的情況，其中一種表示無法構成任一圖形。

Sample Input

1 2 3
11 13 29 31
26 11 13 24
4 5 9 13 12 7
1 2 3 4 5
47
11 13 23 25

Sample Output

1 2 3 are the vertices of a triangle
11 13 29 31 are not the vertices of an acceptable figure
26 11 13 24 are the vertices of a parallelogram
4 5 9 13 12 7 are the vertices of a hexagon
1 2 3 4 5 are not the vertices of an acceptable figure
47 are not the vertices of an acceptable figure
11 13 23 25 are not the vertices of an acceptable figure

原文出處

208 - Firetruck

Center City的消防局與交通部合作，同步更新市區街道的運作情形，因為任何一天都可能因為道路維護或整修的需要而封閉部份道路，消防車需要選擇適當的路徑抵達火場，避免誤入已封閉的路段而延誤救援。

城市已被區分為不重疊的行政區，每一區都有一個消防局，當有火災警報時，火災地點所在行政區的消防局會被通報，並指示通往火災現場的所有可能的路徑。本題請你寫一個程式找出所有可能的路徑。

Input

每一個行政區的地圖都是獨立的，所有地點的編號皆為小於21的正整數，且消防局所在的地點一定是#1，每組測試資料會提供火災地點及路線圖，詳細說明如下：

• 每組測試資料的第一列有一個整數，表示火災地點的編號。
• 接下來每一列會有兩個以一到多個空白字元隔開的正整數，表示這兩個地點之間的聯絡道路是正常運作的(例如：4 7 表示4與7之間的道路是可行走的)
• 最後以兩個0表示測試資料結束。
  

Output

請對每組測試資料輸出其資料編號(CASE #1, CASE #2...)，並分別在不同列輸出每一條可行的路徑，並依序輸出路徑所經過的地點，且同一個地點不能重複經過兩次。最後一列請輸出所有路徑總數，請參考範列資料。

Sample Input

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

Sample Output

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

原文出處

201 - Squares

一個由點組成的正方形矩陣，例如下圖中的16個點，將部份相鄰的點用垂直線或水平線連接起來後，所組成的圖形如下，之後再計算此圖正方形的數量，例如下圖中，正方形寬度為1的數目共2個，正方形寬度為2的數目共1個，所以共有3個正方形。


本題請你計算圖形中，正方形的數量。

Input

輸入包含多組測試資料，每組測試資料的第一列為整數 n (2 <= n <= 9)，表示大正方形的大小，點的數目即為n^2。

輸入資料的第二列為 m，為相鄰兩點的連接線總數，接下來有 m 列，每列為一條長度為1之連接線的資訊，其格式有兩種：

H i j：為一條水平線，在第 i 列上連接第 j 欄到第 j+1欄的水平線。
V i j：為一條垂直線，在第 i 欄上連接第 i 列到第 j+1列的垂直線。

上圖的例子即為範例資料中的第一筆。

Output

每組測試資料請先輸出"Problem #NUM"，NUM為測試資料的編號，空一列後請輸出不同正方形大小各別的總數，請由正方形大小由小到大輸出，其格式為"NUM1 square (s) of size NUM2"，表示正方形大小為NUM2的數目共NUM1個。若沒辦法連成任一組正方形，請輸出"No completed squares can be found."。每組測試資料間請以兩個空行與一列星號隔開，請參考範例資料。

Sample Input

4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1

Sample Output

Problem #1

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #2

No completed squares can be found.

---

原文出處

263 - Number Chains

給定一個整數，你必須以下列的方式產生出另一個整數：

1. 將該數的每一個位數由大到小排列。
2. 將該數的每一個位數由小到大排列。
3. 將上述第一步驟所得的數減掉第二步驟所得的數，產生另一個數。
4. 重複上述步驟，直到出現重複的數字為止。

注意，0是合法的數值。在找到重複出現的數字之前，所出現的不同數值的個數，稱作"數列的長度"(the length of the chain)。你必須寫一個程式讀取一個數值，並輸出該數值所產生出"數列的長度"。

Input and Output

輸入資料會有許多正整數，皆小於10^9，每個正整數一列，以0做為結束。輸入檔案最多有5000個數值。

請輸出以輸入值開始的"數列的長度"，並以Sample Output的格式輸出每一個數值。不會有數列長度超過1000的數值。

Sample Input

123456789
1234
444
0

Sample Output

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 1234
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 4

Original number was 444
444 - 444 = 0
0 - 0 = 0
Chain length 2

(注意這裡有一空行)

注意，每一組輸出後面要多一列空行喔~(包含最後一組)

原文出處

297 - Quadtrees

四元樹(quadtree)可被用來當作圖像編碼的一種格式，背後的原理是基於任何一張圖片都可被切割成4等份，被分割後的每一塊又可再分割成4等份，如此不斷分割下去。每一張圖可被視為樹的父節點，而被分割的四個區塊則以其四個子節點表示，其次序是預先定義的。

如果整張圖只有一種顏色，則可以用只有一個節點的四元樹來表示。一般而言，當一個區塊內有多種顏色才需要再作細部的切割，所以這種四元樹各節點的深度不一定會相同。

本題要處理的是圖片大小為32x32的黑白圖片，共有1024個像素(pixel)，並且要把兩張圖"加"起來組合成新的圖片，"加"的動作是指一個像素在原來的兩張圖上最少有一張是黑色，則該像素為黑色，否則該像素為白色。

本題會給你兩張圖的四元樹表示式，你必須寫一個程式計算這兩張圖相加之後，所有黑色像素的總數。

下圖顯示圖片分割的順序，並以一個例子表示兩張圖片相加所產生的新圖片，及其四元樹的表示方式。

Input Specification

程式一開始會有一個整數N表示測試資料的總數。

每組測試資料有兩列字串，每個字串表示一張圖，以"前序"的方式來表示一個四元樹，'p'代表父節點，'f'(full)代表黑色的區塊，'e'(empty)表示白色的區塊。字串保證是正確的四元樹格式，且樹的深度不會超過5。

Output Specification

請輸出每組測試資料的合成圖有幾個像素是黑色的，輸出格式："There are X black pixels." X表示黑像素的總數。

Example Input

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

Example Output

There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

原文出處

278 - Chess

著名的八皇后問題是把八個皇后放在一個8x8的棋盤上，並使得彼此之間不能互相攻擊。現在，我們想知道如何在一個 m x n 的棋盤上放置最多數量的單一棋種(城堡Rook，騎士Knight，皇后Queen，國王King，其中一種)，使得彼此之間不能互相攻擊。

INPUT

輸入的第一列有一個整數，表示有幾組測試資料。接下來的每列一開始會給定棋種的名稱，r k Q K，依序分別表示城堡Rook，騎士Knight，皇后Queen，國王King。接著會有兩個整數 m (4<=m<=10)，n (4<=n<=10)，表示棋盤的列數與行數。

Output

針對每組測試資料，你必須輸出棋盤上可放置最大數量的棋子，使得彼此之間不會互相攻擊。
注意：棋盤的左下角坐標為1, 1。

SAMPLE INPUT

2
r 6 7
k 8 8

SAMPLE OUTPUT

6
32

231 - Testing the CATCHER

國防部的軍事武器承包商剛完成一種新式飛彈防禦系統的測試工作，該系統稱為"CATCHER"，可以攔截朝我方發射過來的飛彈，該系統非常強大，有極佳的機動性及自我防禦能力，但它有一個缺點：雖然它能攔截的飛彈高度沒有上限，但是能攔截的飛彈高度只能比上一次攔截的高度更低或相等，它沒有足夠的動力攔截更高的飛彈。

承包商所做的電腦模擬測試相當簡單，僅僅只做高度測試，也就是每隔一段時間就會有一顆欲攔截的飛彈，並顯示該飛彈可以被攔截到的高度，所有飛彈都是循序的。

測試報告中只會循序顯示所模擬的飛彈高度，及所有這些飛彈中可以被CATCHER攔截到的總數。

現在國防部需要驗證承包商所做的測試報告的正確性，你必須幫忙寫一個程式循序讀入多組飛彈高度，並計算CATCHER系統最多可攔截的飛彈總數，請注意到CATCHER系統本身的限制，當他選擇攔截某一顆飛彈之後，再也不能攔截更高的飛彈了。

Input

輸入包含多組測試資料，每組資料會有多非負整數，其值介於0~32767之間，用來表示飛彈的高度，測試資料的最後以-1表示該組資料結束，並非表示飛彈的高度。如果該組測試資料的第一個數值為-1，表示測試資料結束。

Output

請輸出每組測試資料的編號(Test #1, Test #2 ...)，及在該組資料下CATCHER系統所能攔截到的最大飛彈總數，輸出的格式如下所示。並請注意每組輸出資料之間請以空行隔開。

注意：每組測試資料的飛彈總數並沒有限制，所以一個效率不佳的演算法可能無法在時限內完成問題。

Sample Input

389
207
155
300
299
170
158
65
-1
23
34
21
-1
-1

Sample Output

Test #1:
maximum possible interceptions: 6

Test #2:
maximum possible interceptions: 2

原文出處