397 - Equation Elation

小學數學教科書的作者請你幫忙寫一個程式處理簡單的代數運算，你需要處理的是代數恆等式，等式的形式為整數的四則運算後接上一個等號與一個變數，如下所示：

12 - 4 * 3 = x

你必須一個步驟一個步驟地處理等式，其輸出如下：

12 - 4 * 3 = x
12 - 12 = x
0 = x

你的程式處理的問題僅限於整數的四則運算，且需遵守先乘除後加減的法則，由左至右依序處理每一項，你可以假設所有除法結果必為整數。

Input

輸入的每一列代表一個等式，等式包含1~20個運算符號，且運算元會有2~21個(運算元的個數必然比運算符多一個)，運算元前面可能會有正負號，等式中可能包含空白字元。變數名稱長度介於1~8個英文字母之間。

Output

請對每組測試資料輸出其原來的等式及其計算的過程，輸出格式中的空白字元可有可無，正確的運算過程及答案才是最重要的。

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

Sample Input

3 * 4 + 4 - 1 / 1 = xyzzy
12 + 2 * 12 / 2 - 1 = y
2 * -3 + -6 - +4 = r
2*-3+-6-+4=r

Sample Output

3 * 4 + 4 - 1 / 1 = xyzzy
12 + 4 - 1 / 1 = xyzzy
12 + 4 - 1 = xyzzy
16 - 1 = xyzzy
15 = xyzzy

12 + 2 * 12 / 2 - 1 = y
12 + 24 / 2 - 1 = y
12 + 12 - 1 = y
24 - 1 = y
23 = y

2 * -3 + -6 - 4 = r
-6 + -6 - 4 = r
-12 - 4 = r
-16 = r

2 * -3 + -6 - 4 = r
-6 + -6 - 4 = r
-12 - 4 = r
-16 = r

原文出處

393 - The Doors

本題請你計算一個小房間內兩端點的最短距離，小房間的四個邊分別為：x=0, x=10, y=0, y=10，起點與終點分別為(0, 5), (10, 5)。小房間內會有0~18個垂直的牆，每面牆有兩道門，如下圖所示：

Input

每組測試資料的格式類似如下：

2
4 2 7 8 9
7 3 4.5 6 7

第一列的整數表示牆的數目，接下來每列有5個實數表示一道牆，第一個實數表示牆面位於x軸的位置(0 < x < 10)，其他四個實數表示兩道門的端點位於y軸的位置，每道牆的輸入順序由x軸位置由小到大排列，門的端點位置則由y軸位置由小到大排列。最後以-1表示輸入資料結束。

Output

請每組測試資料輸出兩端點的最短距離，請輸出到小數點後兩位。

Sample Input

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1

Sample Output

10.00
10.06

原文出處

391 - Mark-up

標記語言(mark-up languages)為一種以文字格式組成的電腦語言，特殊的關鍵字被用來標記文字以表示字型、頁面風格、段落風格…。例如TeX, troff, HTML皆為標記語言。

本題定義一種標記語言，請你讀取該語言的原始碼並輸出其文檔。

關鍵字會以 \ 字元開頭，若其後的字元並非合法的命令，則該字元會被視為一般字元作輸出，例如 \\ 可被用來表示 \ 的輸出。以下為合法的命令：

\b

開啟或關閉粗體字字型(預設為關)。

\i

開啟或關閉斜體字型(預設為關)。

\s

設定字體大小，其後緊接著一個數字表示字體大小，若其後並非數字則維持原字體大小。

\*

開啟或關閉標記功能，若標記功能設為關閉，則其後的字串皆視為一般的文字字串(預設為開啟)。

設定字體大小的數字可以包含小數點，例如12, 9.5, 11., .5皆為視為合法的數字格式。

Input and Output

請將輸入資料的每個字元視為標記語言的原始檔，並輸出其文檔，以EOF作為結束。

Sample Input

\s18.\bMARKUP sample\b\s

\*For bold statements use the \b command.\*

If you wish to \iemphasize\i something use the \\i command.

For titles use \s14BIG\s font sizes, 14 points usually works well.

Remember that all of the commands toggle except for the \\s command.

Sample Output

MARKUP sample

For bold statements use the \b command.

If you wish to emphasize something use the \i command.

For titles use BIG font sizes, 14 points usually works well.

Remember that all of the commands toggle except for the \s command.

原文出處

384 - Slurpys

本題請你寫一個程式判斷給定的字串是否符合某種特定的格式。

Problem Statement

Slurpy為一種特定格式的字串，本題請你讀入一個字串後判斷該字串是否為一Slurpy字串。

定義Slump為符合下列要求的字串：

1. 其第一個字元為'D'或'E'。
2. 第一個字元之後會接一個或連續多個'F'。
3. 一或多個連續的'F'之後會再接上一個Slump或一個'G'，以此做為字串的結束。例如DFFEFFFG為Slump，因為第一個字元為D，且其後接兩個'F'，之後再接上一個Slump字串"EFFFG"。
4. 不符合上述要求的字串並不是一個Slump字串。
   

定義Slimp為符合下列要求的字串：

1. 其第一個字元為'A'。
2. 若該Slimp字串只有兩個字元，則它的第二個也是最後一個字元必為'H'。
3. 若該Slimp字串並非兩個字元的字串，則它滿足下列其中一種形式：
• 'A'之後為'B'再接上一個Slimp字串，並以'C'作結束。
• 'A'之後接上一個Slump字串，並以'C'作結束。
  
4. 不符合上述要求的字串並非一個Slimp字串。

Slurpy定義為一個Slimp後接著Slump的字串。

Examples

Slumps:   DFG, EFG, DFFFFFG, DFDFDFDFG, DFEFFFFFG

Slimps:   AH, ABAHC, ABABAHCC, ADFGC, ADFFFFGC, ABAEFGCC, ADFDFGC

Slurpy:   AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFG

Input

輸入資料的第一列為整數N(1 <= N <= 10)表示測試資料的組數，接下來的N列每列為長度介於1~60的字串。

Output

請在輸出資料的頭尾處輸出"SLURPYS OUTPUT", "END OF OUTPUT"。之中的每一列請依序判斷輸入字串是否為一Slurpy字串，若是請輸出"YES"，否則輸出"NO"。

Sample Input

2
AHDFG
DFGAH

Sample Output

SLURPYS OUTPUT
YES
NO
END OF OUTPUT

原文出處

379 - Hi-Q

Hi -Q是一種棋盤遊戲，棋盤形狀類似十字形，共有33個棋格，於其上被放置32個棋子，正中央位置會是空的，遊戲的玩法是把一個棋子跨過另一個棋子到另一邊空的位置上(必須為垂直或水平地移動)，被跨過的棋子會被拿掉。遊戲的目地是儘可能地移除最多的棋子，本題只需要你模擬遊戲的進行。

棋盤的形狀如下，且每一個棋格皆被賦予1~33的編號：

                              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        26        27
                             28        29        30
                             31        32        33

遊戲的一開始會在某些位置上放置棋子，而其他位置會是空的。遊戲的進行必須不斷的將一個棋子垂直或水平地跨過另一個棋子到另一邊空的位置上，且被跨過的棋子必須被移除，直到沒有辦法再移除多餘的棋子為止，此時你的程式必須回報在棋盤上還有棋子的編號之總和。移動棋子的原則為：儘可能的將棋子移動到編號最大的位置上去，若同時有不同的棋子可移動到相同的地方，請選擇位置編號最大的棋子。

例如下列中以X表示該位置上有棋子：

                              O         O         O
                              O         O         O
          O         O         O         X         O         X         O
          O         O         O         X         O         X         O
          O         O         O         O         X         O         O
                              O         O         O
                              O         O         O

其移動的順序為：將12移到26 -> 將25移到27 -> 將10移到24。最後有兩個棋子在24與27的位置上，24+27=51即為所求。

Input

輸入資料的第一列有一個整數N(1 <= N <= 10)表示測試資料的組數，接下來會有N組測試資料，每組資料會依序給定在哪些位置上被放置棋子，其值介於1 ~ 33，並以0表示該組測試資料結束。

Output

輸出資料共有N+2列，頭尾分別輸出"HI Q OUTPUT", "END OF OUTPUT"，並在這中間依序輸出每組資料的答案。

Sample Input

4
10 12 17 19 25 0 0 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 26   27 28 29 30 31 32 33 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0

Sample Output

HI Q OUTPUT
51                                                          
0
561  
98
END OF OUTPUT

原文出處

377 - Cowculations

本題請你實作一種特殊的運算，該運算有兩個數值Num1與Num2，Num1等於每組測試資料的第一列數值，Num2等於第二列數值，但是數值並非一般的阿拉伯數字，而是有四個字元：V, U, C, D，而其運算符號共有四種：A, R, L, N。
 

運算符號A表示將Num1與Num2相加之後，將其總和回存到Num2，其加法律規定如下：

對於上列對照表中的每一項，其第一個數值表示兩符號相加的結果，第二個數值表示進位值。

例如：U A V = U 且 C A C = V, 進位U。其他例子如下：

VUCDV A VUCDV = VDUCV

DVVCU A CVUCU = UUVCVC

運算符號R表示Num2的值向右移一位，最右邊的數值會遺失且V被補到最左邊的位數，例如VVCDU經運算後會變成VVVCD。

運算符號L表示Num2的值向左移一位，其最左邊的數值會保留且V被補到最右邊的位數，例如VVCDU會變成VVCDUV。

運算符號N表示空運算，即不做任何運算。

Input

輸入資料的第一列會有一個整數N表示測試資料的組數(1 <= N <= 10)，每組測試資料六列，前兩列表示Num1與Num2，接下來有三列，每列有一個運算符號，請你判斷Num1, Num2依序經過這三個運算之後是否會等於第六列的數值。

Output

請在輸出資料的開頭與結尾分別輸出"COWCULATIONS OUTPUT", "END OF OUTPUT"，請對每組測試資料判斷運算結果是否相同，是請輸出"YES"，否則請輸出"NO"。

Sample Input

5
VVVVU
VVVVU
A
A
A
VVVVVVUV
VVCCV
VVDCC
L
R
A
VVVVUCVC
VVCCV
VVDCC
R
L
A
VVVVUCVV
VVUUU
VVVVU
A
N
N
VVVVVUCU
DDDDD
VVVVU
A
L
L
UVVVVVVV

Sample Output

COWCULATIONS OUTPUT
YES
YES
YES
NO
YES
END OF OUTPUT

原文出處

362 - 18,000 Seconds Remaining

檔案傳輸程式通常都會估計並顯示剩餘的傳輸時間，用來估計剩餘時間的原則為：將剩餘欲傳送的資料大小(bytes)除以前幾秒的平均傳輸率。本題請你寫程式模擬這個功能。

Input

輸入會有多組測試資料，每組資料表示一次的檔案傳輸。每組資料的第一列為一個非零的整數表示檔案的大小(bytes)，接下來的每一列依序為每一秒所傳輸的資料量(bytes)，傳輸的總資料量會等於檔案的大小。

當檔案大小等於0時表示測試資料結束。

Output

每組輸出資料的第一列請輸出該組資料編號及檔案的大小，接下來每5秒輸出一次剩餘檔案傳輸所需的秒數。

計算所需的秒數時請先計算前五秒的平均傳輸率(bytes/秒)，若這5秒沒有傳輸任何資料表示這次的傳輸為stalled，你的程式必須輸出這種情況，否則請將剩餘資料量除以前5秒的平均傳輸率，得到剩餘秒數。剩餘秒數必須為整數，請無條件進位到整數(例如12.2進位到13)。

請在每組輸出資料的最後輸出該次傳輸共耗時多少秒，其格式請參考範例資料。

每組輸出之後請額外輸出一列空行。

Sample Input

100
10
20
20
0
10
0
10
0
10
0
20
200
60
30
100
10
50
5
5
5
5
25
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0

Sample Output

Output for data set 1, 100 bytes:
   Time remaining: 4 seconds
   Time remaining: 5 seconds
Total time: 11 seconds

Output for data set 2, 200 bytes:
Total time: 4 seconds

Output for data set 3, 50 bytes:
   Time remaining: 1 seconds
   Time remaining: stalled
   Time remaining: stalled
   Time remaining: 0 seconds
Total time: 20 seconds


原文出處

353 - Pesky Palindromes

一個迴文字(palindrome)表示從前面讀過來與從後面讀過來都一樣，例如Z, TOT, MADAM為迴文字，但ADAM並不是。
 

給定一個字串，請你計算該字串的所有子字串共有幾個不同的迴文字。

Input and Output

輸入會有多組測試資料，每組一列字串，字串長度最長80個字元。

請參考範例資料格式輸出該字串共有幾個不同的迴文字子字串，例如ADAM，的迴文字子字串為A, D, M, ADA，共四個，請輸出：

The string 'ADAM' contains 4 palindromes.

Sample input

boy 
adam 
madam 
tot

Sample output

The string 'boy' contains 3 palindromes. 
The string 'adam' contains 4 palindromes.
The string 'madam' contains 5 palindromes.
The string 'tot' contains 3 palindromes.

Note

The 3 unique palindromes in 'boy' are 'b', 'o' and 'y'.

The 4 unique palindromes in 'adam' are 'a', 'd', 'm', and 'ada'.

The 5 unique palindromes in 'madam' are 'm', 'a', 'd', 'ada', and 'madam'.

The 3 unique palindromes in 'tot' are 't', 'o' and 'tot'.

---

原文出處

347 - Run

一個N位數字的「迂迴數」(runaround number)定義如下：

• 為一個剛好有N個位數的整數，每個位數值介於1~9之間。
• 每個位數值指示下一個位數在其右邊的第幾個，若超過最右邊的位數請循環到最左邊。
• 最左邊的位數為第一個位數，依序找出下一個位數，每個位數剛好只出現一次，且循環到第一個位數。
• 每個位數只會走訪一次。
  

例如數值81362是一個迂迴數，因為：

1. 由最左端的位數8開始。
2. 8的右邊第8個位數為6(作一次循環到最左邊)。
3. 6的右邊第6個位數為2。
4. 2的右邊第2個位數為1。
5. 1的右邊第1個位數為3。
6. 3的右邊第3個位數為8，剛好就是第一個位數。
   

Input and Output

輸入會有多組測試資料，每組資料一個整數R，其位數介於2~7個，請輸出大於等於R且最小的迂迴數，對於每組測試資料一定存在該數字，其格式請參考範例資料。當R=0表示測試資料結束。

Sample Input

12
123
1234
81111
82222
83333
911111
7654321
0

Sample Output

Case 1: 13
Case 2: 147
Case 3: 1263
Case 4: 81236
Case 5: 83491
Case 6: 83491
Case 7: 913425
Case 8: 8124956

原文出處

341 - Non-Stop Travel

David討厭在開車的時候等紅綠燈，為了避免多餘的等待時間，他規劃了他常行駛的路段，並統計各路段的平均等待時間(以秒為單位)，他希望找到一條路徑使得從起點到終點的總等待時間最短(他不在乎行駛的距離長短)。

Input

對於每組測試資料，David提供了一個地圖，每個地圖的第一個整數NI表示節點的數目，節點數最多不會超過10個，且由1開始作編號。接下來的每一列依序為各個節點到其他節點的路徑，例如第一列為 2  3 3  4 6，表示有兩條路徑，節點1通往節點3的等待時間為3秒，節點1通往節點4的等待時間為6秒。最後一列有兩個整數指示起點與終點。當NI=0表示測試資料結束。

Output

請對每組測試資料輸出資料編號、路徑沿途經過的節點編號、共等待的秒數，其格式請參考範列資料。

Notes

1. 最少等待時間的路徑一定唯有一條。
2. 每個路段皆是單向的。
3. 由 I 到 J 的路段最多只會有一條。
   

Example

第一組範例資料的示意圖如下：

+---------------+                   From To Delay
                |               V                     1   3   3
                1<------2------>3------>4<------5     1   4   6
                |       |               ^       ^     2   1   2
                |       +---------------|-------+     2   3   7
                |                       |             2   5   6
                +-----------------------+             3   4   5
                                                      5   4   7

Sample Input

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

2
1   2 5
1   1 6
1 2

7
4   2 5   3 13   4 8   5 18
2   3 7   6 14
1   6 6
2   3 5   5 9
3   6 2   7 9    4 6
1   7 2
0
1 7

0

Sample Output

Case 1: Path = 2 1 4; 8 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay

原文出處

337 - Interpreting Control Sequences

文字介面終端機會有序列埠(用來與外部資料作交換)、鍵盤、螢幕、處理器與RAM。

當一個字元被送到終端機的時候(透過鍵盤或序列埠)，終端機上的軟體會判斷該字元為可顯示的字元(此時直接輸出到螢幕)或是控制字元，控制字元用來做類似將螢幕畫面清除、移動游標或改變字型的動作。

本題請你寫一個用於10x10大小的螢幕上的軟體，用來處理並顯示送到螢幕上的字元。螢幕的列與行被編號為0~9，控制字元以 ^ 表示，一個或兩個字元緊接著在 ^ 符號之後表示特殊的控制功能，所有功能如下所述：

^b

將遊標移動到該列的最前面。

^c

清除整個螢幕畫面，游標不動。

^d

如果可能的話將遊標移至下一列，直行位置不變。

^e

清除遊標所在位置之後該列的字元(包含游標上的字元)，且游標位置不動。

^h

將游標位置移動到列編號0、行編號0的位置。

^i

切換到插入模式insert mode(請見下面說明)。

^l

如果可能的話將游標左移一行。

^o

切換到覆寫模式overwrite mode(請見下面說明)。

^r

如果可能的話將游標右移一行。

^u

如果可能的話將游標上移一列，直行位置不變。

^^

表示輸出字元^，輸出的結果視「輸入模式」或「覆寫模式」而定。

^##

##分別表示兩個0~9的數值，表示要將游標移動到哪一列、哪一行。

不會有不合法的字元被送到螢幕上，且游標不會超出螢幕的範圍。

當一個非控制字元被送到螢幕時，其顯示的方式視目前螢幕的顯示模式而定，當為「覆寫模式」時(這也是螢幕一開始的顯示模式)，抵達的字元會取代游標所在的字 元。當螢幕為「插入模式」時，游標所在字元及其之後該列的字元向右移一位(該列最右邊的字元會遺失)，且新的字元會被寫在游標所在位置上。在這兩種模式之 下，輸出一個字元後遊標皆會向右移動一位(如果可能的話)。

Input

輸入會有多組測試資料，每組資料的第一列有一個整數N表示接下來有N列資料，每列資料的每個字元應被視為螢幕的輸入字元，不會出現tab字元，且每列最後的換行字元也請忽略，而空白字元應被視為需顯示在螢幕上的字元，當N=0表示測式資料結束。

每組測試資料的一開始你必須假定螢幕是清空的(即顯示空白字元)，且游標位於第0列第0行的位置。

Output

請對每組測試資料輸出資料編號，並輸出螢幕最後顯示的畫面，畫面必須被框起來，如範例資料所示。

Sample Input

7
This is bad^h^c
^05^^
^14/ \^d^b   /   \
^u^d^d^l^l^l^l^l^l^l^l^l
^r^r< ACM >^l^l^d/^b   \
^b^d    \ /
^d^l^lv
7
^i9^l8^l7^l6^l5^l4^l3^l2^l1^l0
^o^d^lThis is #1^d^bThis is #2
^d^bThis is #3^d^bThis is #4
^d^bThis is #5^d^bThis is #6
^d^bThis is #7^d^bThis is #8
^i^d^bThis is #9^d^bThis is #10
^54^e Hello^d^l^l^l^lWorld
0

Sample Output

Case 1
+----------+
|     ^    |
|    / \   |
|   /   \  |
|  < ACM > |
|   \   /  |
|    \ /   |
|     v    |
|          |
|          |
|          |
+----------+
Case 2
+----------+
|0123456789|
|This is #1|
|This is #2|
|This is #3|
|This is #4|
|This Hello|
|This World|
|This is #7|
|This is #8|
|This is #0|
+----------+

原文出處

331 - Mapping the Swaps

藉由不斷地對兩個陣列元素作交換以完成陣列元素的排序，這種方法是眾所皆知的「泡泡排序法」(bubble sort) 所用的方式。本題請你計算對於一個陣列共有幾種不同的最小置換順序，例如對3 2 1作排序共有兩種不同的置換順序，分別為：

1. 321 -> 231 -> 213 -> 123。

2. 321 -> 312 -> 132 -> 123。

Input

輸入會有多組測試資料，每組資料的第一個整數表示該陣列元素的個數 n，接下來依序為 n 個元素值。

Output

請參考範例資料輸出每組測試資料共有幾種不同的置換順序，並輸出測試資料編號，注意 n 最大值為5。

Sample Input

2 9 7
2 12 50
3 3 2 1
3 9 1 5
0

Sample Output

There are 1 swap maps for input data set 1.
There are 0 swap maps for input data set 2.
There are 2 swap maps for input data set 3.
There are 1 swap maps for input data set 4.

原文出處

327 - Evaluating Simple C Expressions

本題請你解析C語言的運算式，每個運算式一列且不超過110個字元。每個運算式僅包含整數變數及部份運算符號，且運算式內不會出現常數值。運算式中最多可能會有26個變數，其變數名稱分別為a ~ z(僅包含小寫字元)，且每個變數的初始值依序分別為1 ~ 26(即a=1, b=2, ..., n=14, o=15, ..., z=26)。每個變數最多只會在運算式內出現一次，不見得所有26個變數都會被用上。

運算符號的部份包含用來對兩個運算元作加減的 +, - 符號，例如 a + c - d + b = 2 (因為1+3-4+2=2)，除此之外還有兩個運算符號：++, --， 僅對單一運算元作運算，且可能出現在運算元的前面或後面，當++運算子出現在變數之前的時候，會先對變數作加一的動作，之後才將被加一的變數用於整個運算式的計算，例如 ++c - b = 2，因為 c 被加到4之後才減b(2)。當++運算子出現在變數之後，會先將變數值拿來做為整個運算式的計算，之後才會對變數做加一的動作，例如 c++ - b = 1，雖然 c 最後的值還是4。--運算子放在變數前後對算式的影響與++運算子一樣，但它會對變數作減一的動作。

以 ++a + b++為例，其算法是先將a加上1，再作a+b的計算，最後才將b加上1。

Input and Output

請對每一列運算式作計算，先輸出該運算式之後再輸出該運算式的值，並在之後的每一列中依a~z的順序輸出各變數值，請參考範列資料。

請忽略運算式中所有的空白字元，並且你可以假設不會存在模稜兩可的運算式，例如 a+++b 不會出現在輸入資料中。另外像是++a++亦不會出現在輸入資料中。

Sample Input

a + b
b - z
a+b--+c++
c+f--+--a
   f-- + c-- + d-++e

Sample Output

Expression: a + b
    value = 3
    a = 1
    b = 2
Expression: b - z
    value = -24
    b = 2
    z = 26
Expression: a+b--+c++
    value = 6
    a = 1
    b = 1
    c = 4
Expression: c+f--+--a
    value = 9
    a = 0
    c = 3
    f = 5
Expression:    f-- + c-- + d-++e
    value = 7
    c = 2
    d = 4
    e = 6
    f = 5

---

原文出處

325 - Identifying Legal Pascal Real Constants

Pascal 程式語言規定實數必須包含小數點或是以指數形式表示(指數以e或E作為開頭字元)，或是兩者同時使用。若使用小數點表示，則小數點前後皆最少需要有一位數 字，正負符號或指數符號可能出現在最前面，指數部份必需為整數。空白字元可能出現在實數的前面或後面，但一定不能被嵌在實數裡面。注意Pascal的語法不會對實數的大小範圍作限制，所以本題不需要你考慮數值的範圍。
 

本題請你判斷某實數是否為Pascal的合法實數。

Input and Output

請對每列輸入資料驗證是否為合法的Pascal實數，請參考範例資料。輸入以一列一個星號表示結束。

Sample Input

1.2
   1.
  1.0e-55
  e-12
    6.5E
     1e-12
  +4.1234567890E-99999
   7.6e+12.5
99
*

Sample Output

1.2 is legal.
1. is illegal.
1.0e-55 is legal.
e-12 is illegal.
6.5E is illegal.
1e-12 is legal.
+4.1234567890E-99999 is legal.
7.6e+12.5 is illegal.
99 is illegal.

原文出處

320 - Border

在一個點陣圖中請你繪出一個封閉路徑的邊，如下圖所示：

封閉路線為沿著方格的邊以逆時針方向行走，沿途的右手邊方格被塗黑。點陣圖大小為32 x 32，且左下角定義為原點(0, 0)。你可以假設路徑不會與點陣圖的邊界接觸，亦不會與自身接觸。請注意被塗黑的部份必定是在封閉路徑外圍。

Input

輸入資料的第一列有一個整數表示測試資料的組數，每組測試資料兩列，第一列有兩個整數x, y表示路徑的起點，第二列有一個字串，由左到右的每個字元表示行進的方向，東西南北分別以'E', 'W', 'S', 'N'表示，並以 '.' 表示路徑結束。

Output

請參考範列資料格式輸出測試資料編號及其點陣圖，請在每組資料後輸出一列空行。

Sample Input

1
2 1
EENNWNENWWWSSSES.

Sample Output

Bitmap #1
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
................................
.XXX............................
X...X...........................
X..X............................
X...X...........................
.X..X...........................
..XX............................


原文出處

312 - Crosswords (II)

一個猜字謎的遊戲可用一個由0與1所組成，大小為m x n的矩陣表示，0表示白色方格，1表示黑色方格，部份方格會被賦予編號，一個編號代表一個必須被填入方格中直向或橫向的單字，一個被賦予編號的方格必需是白色方格，且滿足下列兩個條件：1. 該方格之下必須是白色方格，且之上不是白色方格；2. 該方格的右邊方格為白色，且左邊不是白色方格。編號由左到右、由上到下依序被賦予。
 

該矩陣必須重新做輸出，每個方格以一個4x6的字元表示，下列依序為黑色方格、被賦予編號的白方格與未被賦予編號的白方格：

++++++                        ++++++         ++++++
++++++                        +nnn +         +    +
++++++                        +    +         +    +
++++++                        ++++++         ++++++

若黑色方格在四週則不需要繪出，請參考範例資料。請注意圖形每列的最後不可有多餘的空白字元。

Input

每組測試資料的第一列有兩個整數分別表示 m, n (m, n < 25)，接下來的 m 列每列有 n 個0或1的整數，每個整數之間皆以一個空白字元隔開。當 m = n = 0 表示測試資料結束。

Output

請繪出該字謎的圖形。請在每組資料之後輸出一列空行。

Sample Input

6 7
1 0 0 0 0 1 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 1 0 0 1 1 1
0 0 0 1 0 0 0
1 0 0 0 0 0 1
5 3
1 0 1
0 0 0
1 1 1
0 0 0
1 0 1
0 0

Sample Output

     +++++++++++++++++++++
     +001 +    +002 +003 +
     +    +    +    +    +
++++++++++++++++++++++++++++++++++++
+004 +    ++++++005 +    +006 +007 +
+    +    ++++++    +    +    +    +
++++++++++++++++++++++++++++++++++++
+008 +    +009 +    +    +010 +    +
+    +    +    +    +    +    +    +
+++++++++++++++++++++    +++++++++++
+    ++++++011 +    +
+    ++++++    +    +
++++++++++++++++++++++++++++++++++++
+012 +013 +    ++++++014 +015 +    +
+    +    +    ++++++    +    +    +
++++++++++++++++++++++++++++++++++++
     +016 +    +    +    +    +
     +    +    +    +    +    +
     ++++++++++++++++++++++++++

     ++++++
     +001 +
     +    +
++++++++++++++++
+002 +    +    +
+    +    +    +
++++++++++++++++


++++++++++++++++
+003 +004 +    +
+    +    +    +
++++++++++++++++
     +    +
     +    +
     ++++++


原文出處

301 - Transportation

鐵路運輸公司TransRuratania經營一項由城市A到城市B的鐵路運輸事業，沿途有許多停靠站，各停靠站由A到B依序編號，以A為編號0，B為編號 m。該公司進行一項研究用來改善旅客的載運量，進而提高收益。火車最多可同時搭載 n 位旅客。火車票價等於旅客上車後沿途停靠站的個數(包含目地的)，火車由A城出發，並可於各站訂票，由車站S訂的票表示會由S開始劃位直到目的地為止。由於火車承載量的限制，該鐵路公司可能無法接受所有的訂位需求，訂票的原則為必須全部接受訂位的數量或是全部拒絕該數量。
 

給定由A到B各站所有的訂位需求，本題請你寫一個程式計算該公司最大可能的收益，單一訂票的收益等於人數乘於票價，總收益等於所有訂票收益的總和。

Input

每組測試資料的第一列有三個整數 n、m及訂票的數目，接下來的每一列為其訂票資訊，每筆資料有三個整數：出發站、目地站及旅客人數，最多會有22筆訂票資訊，且 m 值最大為7。當 n、m 及訂票數目皆為零時表示測試資料結束。

Output

請輸出每組測試資料的最大收益。

Sample Input

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

Sample Output

19
34

原文出處

300 - Maya Calendar

馬亞教授在研究馬雅文明的曆法上有了重大的發現，教授從繩結上的訊息發現馬雅文明的一年有19個月共365天，這種曆制稱作"Haab"，前18個月每月有20天，由0開始編號到19，而第19個月只有5天，分別為0, 1, 2, 3, 4，另外，每個月都有一個名字，依序為：pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu, uayet。馬雅人相信第19個月是不幸的月份，所在在該月所有經濟活動都會停止，甚至會避免從事家務，連地都不掃了。

另外，基於宗教上的理由，馬雅人還會使用另一種曆制，該曆制稱為"Tzolkin"，這種曆制的一年有260天，分為20種日子，每種日子13天，用13個整數與20個日子的名稱來區分每一天，整數為1~13，20種日子的名稱為：imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau。

注意，每一天的名稱不會衝突，例如一年前幾天的名稱如下所示：

1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, 8 imix, 9 ik, 10 akbal...

每一年以整數表示，例如：0, 1, ...，由0開始表示，所以兩種歷制的第一天分別為：

Haab: 0. pop 0

Tzolkin: 1 imix 0

請寫一個程式幫助馬亞教授做日期的轉換，由Haab曆制轉到Tzolkin曆制。

Input

Haab的日期格式為：日 月 年

輸入的第一列為一個整數表示共有多少日期需要轉換，接下來有n列，每一列為一個以Haab曆制表示的日期，年份最多到5000。

Output

Tzolkin的日期格式為：數字 名稱 年

請在輸出的第一列顯示共有幾組日期，接下來的n列顯示對應的Tzolkin日期。

Sample Input

3
10. zac 0
0. pop 0
10. zac 1995

Sample Output

3
3 chuen 0
1 imix 0
9 cimi 2801

原文出處

352 - The Seasonal War

老虎村與大象村兩邊的居民又在打仗了，上個月大象村成功地發射間諜衛星「鳥鳥號」(Bumble Scope)到對方的領空，發射鳥鳥號的目的在於窺視老虎村上空有幾隻"戰鬥鷹(War Eagles)"，然而因為品管不良導致鳥鳥號有兩個瑕疵，首先，在它品質不佳的主鏡頭上摻有許多小蟲，會使照出來的衛星照片有許多小污點，另外由於對焦功能異常，使得照片的大小與銳度變得無法控制。

程式設計師們被一群披著虎皮的大象挾持，把他們囚禁在旅館內逼他們要解決衛星照片失真的問題。失真的照片以每一點的像素(pixel)儲存在檔名為Bumble.in的檔案中，每張照片皆為正方形且每一個"像素"或"點"的資訊不是0就是1。如果一點的像素為1，表示鳥鳥號照像機照到了一整隻戰鬥鷹或只是一隻鷹的一小部份；若像素為0，可能只是因為鏡頭上的污點，或是根本什麼都沒照到，程式設計師們必須假定：

a)

一隻戰鬥鷹至少佔一個點(或像素)。

b)

像素為1相鄰的兩點表示同一隻鷹(相鄰包括上下左右與四個斜角)，一張戰鬥鷹的特寫可能會是整張都為1的圖。

c)

不同的兩隻鷹不會彼此靠在一起，雖然這個假設很沒有根據，不過程式設計師們也只能作這樣的假設。

d)

照片的左邊不會循環到右邊，上邊不會循環到下邊，彼此並不相鄰 (當然，如果只有左右兩行，則左行當然與右行相鄰)。

Input and Output

從輸入中讀取一張照片的資訊，第一個整數代表照片的大小，照片由0與1所構成，請計算圖上有幾隻戰鬥鷹。請參考下面的Sample input。

請依照Sample output的格式輸出照片的編號與戰鬥鷹的數目，照片大小不會超過25像素。

Sample input

6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000

Sample output

Image number 1 contains 3 war eagles.
Image number 2 contains 6 war eagles.

原文出處

371 - Ackermann Functions

Ackermann function的特徵為：其所產生出來的數列長度無法由輸入值直接計算，一個整數的Ackermann function如下：

Ackermann數列最終會收斂到1，如下列的幾個例子。例子中的初始值寫在中括號內，再接所產生出的數列，最後數列的長度以大括號表示。

[10] 5 16 8 4 2 1 {6}
[13] 40 20 10 5 16 8 4 2 1 {9}
[14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}
[19] 58 29 88 44 22 ... 2 1 {20}
[32] 16 8 4 2 1 {5}
[1] 4 2 1 {3}
Input and Output
你的程式要讀入多對數值，每一個數對表示一個循序的閉集合數列中的第一個數值與最後一個數值，對每一個閉集合數列中的每一個數值，你必須從中找出能產生最大長度的Ackermann數列的數值為何。本問題所計算的數列其值皆不會超過32位元整數的範圍，最後一對整數為0, 0，輸出格式為：
Between L and H, V generates the longest sequence of S values.
其中：
L = 所要計算的數列下限值。
H = 所要計算的數列上限值。
V = 最先得出最長Ackermann數列的值(如果能產生出最長數列的值不只一個，只列出其值最小的那一個)。
S = 最長的數列的長度。
Sample Input
 1 20
35 55
 0 0
Sample Output
Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.
1. 本題與 100 - The 3n + 1 problem 幾乎一樣，但因為首項不列入計算，所以其輸出會比第100題少1。 
2. 注意1的序列為: [1] 4 2 1 {3}，而非[1] {0}。
原文出處