159 - Word Crosses

一個十字交錯字由兩個單字組成，第一個單字以水平排列，第二個單字以垂直排列，於交錯的位置共用同一個字母，其共用字母必須盡可能接近水平文字的開頭，在此情況下亦盡可能接近垂直文字的開頭。例如"DEFER"與"PREFECT"的共同字母為彼此的第一個"E"，而"PREFECT"與"DEFER"的共同字母為"R"。雙十字交錯字由四個單字組成，兩個水平單字必須在同一列。

本題給定每組四個單字(水平1, 垂直1, 水平2, 垂直2)，請你輸出每組雙十字交錯字。

Input

會有多列輸入資料，每列有四個單字，兩兩一組，每個單字包含1~10個大寫字母，每個單字之間最少以一個空白字元隔開。以一列僅含一個"#"字元表示測試資料結束。

Output

請對每組測試資料輸出雙十字交錯字，水平文字間以三個空白字元隔開，如果無法組成這兩個十字交錯字，請輸出"Unable to make two crosses"。請每組測試資料間輸出一列空行。

Sample input

MATCHES CHEESECAKE PICNIC EXCUSES
PEANUT BANANA VACUUM  GREEDY
#

Sample output

 C
 H
 E
 E
 S
 E          E
 C          X
MATCHES   PICNIC
 K          U
 E          S
            E
            S

Unable to make two crosses

原文出處

148 - Anagram checker

重新排列一段文字的字母而得到另一段文字有時候還蠻有趣的，例如重組原始文字："WILLIAM SHAKESPEARE"可得到重組字："SPEAK REALISM AWHILE"。

本題請你寫一個程式讀取一部字典及數列文字，請你從字典中選出一些單字，該組單字的字母經過重新排列後可組成原始的文字，請你從字典中找出所有可能的單字組合，且勿與原始的文字相同，若不存在任何一組重組字，請不做任何輸出，甚至連一列空行也不輸出。

Input

輸入資料包含兩部份，每一部份的最後以一列一個"#"符號作結束，第一部份為一部字典，第二部份為多列文字，你必須從字典中找出每一列的所有重組字。字典會以單字的大小順序作排列且不超過2000個，且每個單字一列。所有資料皆為大寫字母，且每個單字不會超過20個字元。

Output

請參考範例資料輸出所有原始文字與重組字，並以" = "隔開。重組字的每個單字須以一個空白字元隔開，且單字必須以字典順序排列輸出。

Sample input

ABC
AND
DEF
DXZ
K
KX
LJSRT
LT
PT
PTYYWQ
Y
YWJSRQ
ZD
ZZXY
# 
ZZXY ABC DEF
SXZYTWQP KLJ YRTD
ZZXY YWJSRQ PTYYWQ ZZXY
#

Sample output

SXZYTWQP KLJ YRTD = DXZ K LJSRT PTYYWQ
SXZYTWQP KLJ YRTD = DXZ K LT PT Y YWJSRQ
SXZYTWQP KLJ YRTD = KX LJSRT PTYYWQ ZD
SXZYTWQP KLJ YRTD = KX LT PT Y YWJSRQ ZD

原文出處

139 - Telephone Tangles

有一間公司想要控管員工撥打私人電話的電話費成本，所有通話會被記錄下來，包含撥打的號碼(最多15位數字)、通話時間。請你寫一個程式處理通話記錄，並整理成一份報表。

國際電話號碼以兩個零開頭(00)，接著一組國碼(1~3位數)，最後再接著一組用戶號碼(4~10位數)。國內長途電話號碼以一個零開頭(0)， 接著一組區碼(1~5位數)，最後再接著一組用戶號碼(4~7位數)。每通的通話費取決於所撥打的地區與通話時間。國內短途電話號碼以任何非零數字開頭，且通話費用為零。

Input

輸入資料包含兩個部份，第一部份包含「國際碼」或「國內長途碼」及其地區與通話費率，其格式如下：

編碼 地區名稱$每分鐘的通話費

地區名稱不會超過25個字元，輸入資料的第一部份會以6個零表示結束(000000)。
第二部份的每一列都是一筆通話記錄，包含撥打的號碼與通話時間(分鐘)，並以最少一個空白字元隔開，該部份資料以一個#符號表示結束。通話號碼不會有模稜兩可的情形。

Output

輸出資料包含通話號碼、地區名稱、用戶號碼、通話時間、每分鐘通話費率、通話費，其格式請參考範列資料。國內短途電話費率為0，若有不合法的電話號碼，請在地區名稱輸出"Unknown"，且通話費用為-1.00。

Sample input

088925 Broadwood$81
03 Arrowtown$38
0061 Australia$140
000000
031526        22
0061853279  3
0889256287213   122
779760 1
002832769 5
#

Sample output

---

原文出處

129 - Krypton Factor

在一個字串中如果相同的兩個子字串相鄰地靠在一起，我們稱該字串為"easy"，否則稱為"hard"。
下例為easy字串：

• BB
• ABCDACABCAB
• ABCDABCD

下例為hard字串：

• D
• DC
• ABDAB
• CBABCBA

Input and Output

輸入會有多組測試資料，每組資料一列會有兩個整數 n, L，其中 n > 0 且 1 <= L <= 26，請你輸出以字典順序排列的第 n 個hard字串(只能利用前L個字母)，並接著顯示該字串的長度。第一個字串一定是A。你可以假定所給定的 n 與 L 必存在第 n 個hard字串。
例如當L=3, 前7個hard字串依序分別為：

A
AB
ABA
ABAC
ABACA
ABACAB
ABACABA

請在每組輸出字串之間，以四個字元為一組並以一個空白字元隔開，且每16組一列，第17組之前請輸出一換行字元，因此上例中 n = 7, L = 3其輸出為：

ABAC ABA

7

當 n = 0, L = 0表示測試資料結束。你可以假定最長的輸出字串不會超過80個字元。

Sample Input

30 3
0 0

Sample Output

ABAC ABCA CBAB CABA CABC ACBA CABA
28

原文出處

126 - The Errant Physicist

本題討論包含 x, y 變數多項式函數的乘法，如下式中：


將上式乘開得到：


本題給定兩個多項式，請你將這兩個多項式相乘後輸出。

Input

輸入資料以兩列為一組，每列不超過80個字元，最後一列以 # 表示測試資料結束。每列有一個多項式，且不會有任何的空白字元與指數符號^，指數值為大於零的整數，係數亦為整數，但可為負值。指數值與係數皆小於等於100，每一項最多有一個 x 一個 y。

Output

請將每組測試資料的二列多項式相乘，並將其解輸出為兩列，第一列包含指數的部份，該列必須對齊第二列。其輸出的規則如下：

1. 項次的排列必須以 x 的指數由大到小排列，並以 y 的指數由小到大排列。
2. 指數相同的項必須結合在一起，例如 40x²y³ - 38x²y³ 表示為 2x²y³.。
3. 不可輸出係數為零的項。
4. 除了常數1之外，為1的係數不可輸出。
5. 為1的指數不可輸出。
6. 指數為零的部份不可輸出。
7. 連接前後項次的加減符號前後必須有一個空白字元隔開。
8. 若第一項的係數為負值，請輸出 '-'，且該表示負數的符號前後不能有任何空白字元。
9. 你可以假定每列輸出長度不會超過80個字元。
10. 每組輸出資料之間不能有多餘的空行。
11. 每組輸出的兩列資料長度必須一致，較短的一列必須以空白字元補足長度。

Sample Input

-yx8+9x3-1+y
x5y+1+x3
1
1
#

Sample Output

13 2    11      8      6    5     5 2     3    3
-x  y  - x  y + 8x y + 9x  - x y + x y  + 8x  + x y - 1 + y 

1


原文出處

152 - Tree's a Crowd

威廉博士是一位著名的植物心理學家，他發明了一種新的植物分類法，這是個複雜的分類法，在分類之前必須先對每顆樹定義三個一組的參數(每個參數值在[0, 255]的範圍)，因此每顆樹可被視為三維空間內的一點。基於自然的生長法則，測量大樣本數量的樹木通常都會均勻地分佈在整個空間。博士發現在空間內相鄰的樹木之間有很高的相似性，為了要驗證這項假設，他必須統計每顆樹與其最靠近的樹木的距離，並依固定的距離組距做成直方圖。

請寫一個程式最多可處理5000顆樹，並決定每一顆樹與其最接近的樹的距離小於1的共有幾顆，大於等於1且小於2的有幾顆，以此類推，直到統計出大於等於9且小於10的有幾顆。因此，假如 di 定義為第 i 顆樹與其最靠近的樹的距離，且 j<= di < k (其中 k = j+1)，則這顆樹就在直方圖 j 的那一組的數量加1(最小一組為第0組)。例如，若共有兩顆距離為1.414單位的樹，則直方圖每組的長度為：0, 2, 0, 0, 0, 0, 0, 0, 0, 0。

Input and Output

輸入會有許多列，每一列有三個整數，其值介於[0, 255]之間，並以三個0做為結束。輸出只有一列，包含10個整數表示每組的數量，每個數的寬度為4，並向右對齊輸出。

Sample input

10 10 0
10 10 0
10 10 1
10 10 3
10 10 6
10 10 10
10 10 15
10 10 21
10 10 28
10 10 36
10 10 45
0 0 0

Sample output

   2   1   1   1   1   1   1   1   1   1

輸出只有一列，請在該列最後補上換行字元

原文出處

141 - The Spot Game

放石頭遊戲(The game of Spot)在一塊NxN的板子上進行，如下圖為N=4的板子。遊戲的玩法是兩個玩家輪流放一塊石頭在空的格子上，或是可以從板子上拿一塊石頭起來，遊戲的進行中可以發現，板子上石頭的佈局會不斷變化，當一玩家排出已重複出現過的佈局時，他就算輸了這一局(一種佈局如果將之旋轉90度、180度、270度亦視為相同的佈局)。若在2N步內未出現過相同的佈局就算和局。

請參考下列幾種佈局：



若出現過第一種佈局，則再出現2、3、4種佈局即結束比賽(還有另一種能結束比賽的佈局未畫出)，注意，第5種佈局並不能算是相同的佈局。

Input and Output

輸入會有多組測試資料，一開始會給定板子的大小N (2  N  50)，接下來會有2N個移步方式，當然也有可能2N步還沒走完就有人贏得了比賽。每一列會有一個座標位置，並以 + 或 - 來表示新增或移除一塊石頭。你可以假定所有的步驟都是合法的，也就是說，不會在空格子上拿走一塊石塊，也不會重複放置石頭在同一個位置上。輸入的最後會以0做結束。

請輸出哪位玩家贏得了比賽，並在哪一步贏得比賽，若平手則輸出draw。

Sample input

2
1 1 +
2 2 +
2 2 -
1 2 +
2
1 1 +
2 2 +
1 2 +
2 2 -
0

Sample output

Player 2 wins on move 3
Draw

原文出處

164 - String Computer

Extel推出最新型的電腦 "X9091字串處理機"，主要用途在於密碼學上的應用。該電腦可藉由編程由一組輸入字串產生另一組字串，該電腦用的是精簡指令集晶片(RSIC)，只有三個指令：
1. 刪除(D)特定位置上的字元。
2. 插入(I)一個字元到特定位置。
3. 改變(C)特定位置上的字元。


電腦程式是由機器語言所寫成，且每個指令為固定長度，格式為ZXdd，Z表示刪除(D), 插入(i), 改變(C)其中之一，X表示字元，dd表示兩位數字。程式的結束以一個特殊的結束指令E來表示。


以一個例子來說明，若輸入字串為abcde，我們希望藉由字串的運算得到bcgfe，以下是一個比較簡單的運算方式：


指令      字串
             abcde
Da01     bcde        % a 是必要的
Cg03     bcge
If04       bcgfe
E           bcgef      %程式結束


寫一個程式讀入兩組字串(輸入字串與目標字串)，並找到由輸入字串轉換成目標字串最少所需的指令總數，若有多種可能的解法，只要輸出任一種就可以了。


Input and Output
輸入有許多列，每列有兩個字串，並以一個空白字元分隔。字串長度不會超過20個小寫字元，以#表示輸入結束。


Sample input

abcde bcgfe

#

Sample output

Da01Cg03If04E

原文出處

125 - Numbering Paths

Background

由輸入資料產生出肯定或否定(yes or no)兩種答案的問題被稱為「判定性問題」(decision problems)。一個典型的判定性問題是NP-完備性問題(NP-complete problems)，這種問題並無法用一般通用而有效率的方法處理。有些問題與判定性問題一樣單純，不過要試著列舉出所有肯定的答案就很困難了(或至少會花很多時間)。

這問題關於車輛在一個僅含單向道路的城市中，如何決定所有可能路徑的總數。

The Problem

給定城市中所有由道路連接的交叉點，你必須寫一個程式決定每個交叉點之間所有可能路徑的總數，一條路徑是由一節點到另一節點之間所依序經過的道路集合。

城市內的點由0開始被賦予編號，一條單向道路會由兩個節點來指定，例如表示由節點 j 到節點 k 的單向道路，注意，雙向道路可藉由定義兩條對向的道路來處理： 與 。

考慮一個有四個節點，並以以下四條單向道路所連結的城市：

0  1
0  2
1  2
2  3

由 0 到 1 之間共有 1 條可能的路徑，由 0 到 2 之間共有 2 條可能的路徑( 及 )，由 0 到 3 有 2 條路徑，1 到 2 有 1 條，1到 3 有 1 條，2 到 3 有 1 條。
兩點之間的路徑可能存在有無限多條，例如上例中再增加一條由 3 到 2 的路徑，則由 0 到 2 的路徑選擇會變的有無限多條，因為可藉由 2 3 之間來來回回來增加路徑總數，因此路徑 與路徑 是不同的。

The Input

輸入會有許多城市的道路資訊，一開始會有該城市的單行道總數，接著是每條由 j 到 k 的單行路，以 j k 來表示。所有測試資料的節點編號都是由 0 開始依序增加。所有輸入中的整數都以空白字元分隔，並以EOF結束。

不會存在有連接相同節點的道路。

The Output

針對每個城市請輸出所有節點兩兩之間所存在的路徑總數，其輸出的格式請用矩陣的形式表示，假設該矩陣定義為M，則 M[j][k]表示每個由 j 到 k 的不同路徑總數，輸出矩陣時請以矩陣的「列順序」(row-major order)來表示，矩陣的每列輸出為一列。在輸出矩陣之前請先輸出"matrix for city k'"，k以 0 開始表示城市的編號，。

若兩節點之間存在有無窮多組路徑選擇，請輸出 -1，每列之間的整數請以空白字元隔開。

Sample Input

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

Sample Output

matrix for city 0
0 4 1 3 2
0 0 0 0 0
0 2 0 2 1
0 1 0 0 0
0 1 0 1 0
matrix for city 1
0 2 1 0 0 3
0 0 0 0 0 1
0 1 0 0 0 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
matrix for city 2
-1 -1 -1 -1 -1
0 0 0 0 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0 0 0 0

原文出處

144 - Student Grants

某國政府為了降低申請助學貸款的意願，設計了一套費時而又冗長的請款流程，每位申請的學生會收到一張提款卡，記錄目前已提領的金額，一開始已提領金額當然為零，且每年的提領上限為$40。詭異的是，領款時間只限該學生生日後的第一個銀行工作日，所以通常一天最多只有25個學生會來領錢。

學生必須拿著提款卡到特定的提款機領錢，這種提款機被設計成有極佳的安全性，它有兩層金庫，安全性較高的內層金庫有許多$1元硬幣，而安全性較低的外層金庫則負責儲放少量的$1元硬幣供學生直接提領。為了降低被搶所造成的損失，只有當外層金庫的硬幣用完的時候，才會由系統自動把硬幣由內層移到外層。每天一開始外層金庫會是空的，且馬上會有$1元硬幣由內層移往外層，之後當外層金庫的硬幣被領完的時候，由內層移往外層的硬幣會增加到$2，下次再領完則再增加到$3…以此類推，直到到達某一個最大值 k 為止，下次移往外層的金額又會由$1開始累加。

每位學生排隊領$40，領錢時會插入自已的提款卡，提款卡會記錄已提領的總金額。每次領錢最多只能領到外層金庫內的硬幣金額，若學生總提領金額未到達$40，則他會拿回他的提款卡到後面重新排隊，當然，此時外庫金庫的金額為零，系統會馬上補上一筆錢到外層金庫。若外層金庫的金額加學生已提領總額大於$40，則系統只會發出剛好總額達到$40的錢給學生，剩下在外層金庫的錢會留下來給下一位學生提領。

請寫程式處理兩個整數為一組的資料，N表示學生數(1 N 25)，k 表示提款機硬幣由內移往外層的最大限制(1 k 40)，請依序輸出學生領滿$40後離開的次序。

Input and Output

輸入每列有兩個整數 N 與 k ，(0, 0)表示資料結束。

針對每組輸入，請依序輸出領完錢離開隊伍的學生編號，學生的編號是最一開始排隊的次序，並以1開始。輸出編號時請設寬度為3，向右對齊。

Sample input

5 3
0 0

Sample output

  1  3  5  2  4

原文出處

140 - Bandwidth

給定一圖(V, E)，V為節點集合，E為邊的集合，並指定一組有序的節點(V內的所有節點)，則一個節點N的bandwidth定義為所有與該節點N相鄰的節點在這一組有序的集合裡面，與該節點N之距離之最大值，而一組有序節點集合O的bandwidth則定義為所有節點的bandwidth之最大值。以下圖為例：

我們隨便把這八個節點作排序，選其中兩組排序如下：

左圖中每個節點的bandwidth由左至右分別為：6, 6, 1, 4, 1, 1, 6, 6，取最大值得到該序列的bandwidth為6，同理，右圖中每個節點的bandwidth由左至右分別為：5, 3, 1, 4, 3, 5, 1, 4，取最大值得到該序列的bandwidth為5。

請寫一個程式，找出一組可能的序列，使得該序列之bandwidth最小。

Input

輸入會有多組測試資料，每組一列表示一組圖形，最後以 # 字元結束輸入。圖形的表示方法是告訴你所有節點與其相鄰的節點，可能的節點名稱為所有大寫英文字母'A'-'Z'。每組資料以分號 ; 隔開，以測式資料A:FB;B:GC;D:GC;F:AGH;E:HD為例，第一組A:FB表示與A相鄰的節點為F及B，第二組B:GC表示與B相鄰的節點為G及C，以此類推，此例共有5組。

一個圖形最多會有8個節點。

Output

請輸出bandwidth最小的序列，並輸出其bandwidth，格式請參考下面。每個序列中的節點請以一個空白字元隔開，若有多組可能的答案，請輸出字典順序最小的那組。

Sample input

A:FB;B:GC;D:GC;F:AGH;E:HD
A:FB;B:GC;D:GC;F:AGH;E:H
A:B;B:C;C:D;D:E;E:F;F:G;G:H
#

Sample output

A B C F G D H E -> 3
C D B G A F E H -> 2
A B C D E F G H -> 1

原文出處

123 - Searching Quickly

給你一組標題字串，並告訴你那些是相對不重要的字，請你寫一個程式找出標題字串中所有關鍵字(Key Word In Context)，並依照關鍵字的字典順序依序列出。

關鍵字是除了所有不重要的字以外的字，而我們會給你那些不重要的字。

例如，不重要的字若為：``the, of, and, as, a''，且有四組標題列：

Descent of Man
The Ascent of Man
The Old Man and The Sea
A Portrait of The Artist As a Young Man

而我們需要你依字典順序找出所有關鍵字後，把整個標題列出，並把關鍵字改為大寫：

                      a portrait of the ARTIST as a young man
                              the ASCENT of man
                                  DESCENT of man
                       descent of MAN
                    the ascent of MAN
                          the old MAN and the sea
a portrait of the artist as a young MAN
                              the OLD man and the sea
                                a PORTRAIT of the artist as a young man
              the old man and the SEA
    a portrait of the artist as a YOUNG man

The Input

輸入的每一列都是一筆資料，上半部會給你所有「不重要的字」，下半部會給你所有標題列，中間以雙冒號(::)隔開，「不重要的字」會以英文小寫的型式出現，每一列都表示一個字，最多不會超過10個字元。而標題列也是一列表示一個標題，但是會有大小寫混合，標題中的字會以空白字元隔開，裡面的字最多15個字元。

「不重要的字」最多50個，標題列最多200個，輸入資料的總字元數則不超過10,000個，除了英文大小寫('a'-'z', 'A'-'Z')及空白字元外，不會出現其他字元。

The Output

我們的目的是找出所有標題列中所有關鍵字(即扣除那些不重要的字)，但並非只把關鍵字列出即可，請列出整列標題。並以關鍵字的字典順序依序列出，如果標題內有多個相同的關鍵字，則亦必需重複列出此標題。

所列出的標題中的關鍵字必須改為全大寫，而其他字則必須全小寫。不同標題若有相同的關鍵字，請依標題輸入的順序列出，同一標題內重複出現的關鍵字之輸出順序，請以由左到右的原則來做輸出。

判繼哪些是「不重要的字」時，請無視大小寫的差異。

輸出整列標題時不需要有多餘的空白字元，請勿依關鍵字向左或向右對齊，格式如下所示。

Sample Input

is
the
of
and
as
a
but
::
Descent of Man
The Ascent of Man
The Old Man and The Sea
A Portrait of The Artist As a Young Man
A Man is a Man but Bubblesort IS A DOG

Sample Output

a portrait of the ARTIST as a young man
the ASCENT of man
a man is a man but BUBBLESORT is a dog
DESCENT of man
a man is a man but bubblesort is a DOG
descent of MAN
the ascent of MAN
the old MAN and the sea
a portrait of the artist as a young MAN
a MAN is a man but bubblesort is a dog
a man is a MAN but bubblesort is a dog
the OLD man and the sea
a PORTRAIT of the artist as a young man
the old man and the SEA
a portrait of the artist as a YOUNG man

原文出處

197 - Cube

由27個小方塊組合而成的3x3x3方塊被拆解成下面七個部份：

Figure 1: 組成3x3x3方塊的七種結構

這七種結構可以以許多種不同的方式重新組合成3x3x3的大方塊，下圖顯示有兩種組合方式。上面三張圖與下面三張圖分別表示一種方塊的組成方式，左圖表示方塊的第一層，中間為方塊的第二層，右圖為方塊的第三層，每一張圖有9個字母，表示在這9個位置上分別為七種結構中的一種，這七種結構的代號如上圖所示，為a~g。

Figure 2: 兩種可能的組合方式

請你寫一個程式輸出所有可能的組合方式，但若僅僅透過旋轉的方式由一種組合產生另一種組合，則不輸出此種重複的組合。

Hint: 結構 a 是所有七種結構中唯一一種不能經由旋轉或平移後還能變回自已原來樣子的結構，為了避免產生出與其他組合方式相同的解(僅僅只是角度不同)，你可以限定 a 結構只能平移而不能旋轉，這樣可避免產生出相同的解。

Input

輸入會有多組測試資料，每一組測試資會指定 a 結構的初始位置，你可以對a作平移，但決不能旋轉它。

Output

對每一個找到的組合，請輸出一列以字串表示的組合結構，字串是用來表示方塊組成結構的線性表示法，每一個字元代表佔據在該位置上的七種可能結構之一，請照下列方式輸出字串：

• 整個字串由三個子字串組成，分別為第一層、第二層、第三層。
• 每個子字串又分別由三個子字串所組成，分別為上列、中列、下列。
• 列字串由三個字元組成，分別表示左邊、中間，與右邊的小方塊。

Figure 2 的字串表示式如下：

adcaccaacddgbfgffedggbfebee

aababbadcffegfcddcfeeggedgc 

按照a~g的七種結構命名方式來表示上述的方塊表示式對你的程式來說應該會是較好的選擇。

在每組測試資料之後輸出一個空行。

Figure 3: 方塊與字串位置的對應關係

上圖顯示各個字元對應到小方塊的位置。

Sample input

aa.a..a....................
.........a..a..aa..........

Sample output

aababbadcggeffcddcgeegfedfc
aababbadceffgdcgdceefedfggc
...
aababbadcffegfcddcfeeggedgc

adcaccaacfddfebgeeffdggbgeb
...

原文出處

151 - Power Crisis

由於紐西蘭今年冬天發生能源危機(因為久旱不雨，導致水庫水位太低)，所以必須實施一個非常態性的限電措施，就是讓每個地區公平地輪流斷電一段時間。全國被分成 N 個區域 (Auckland 編號為 1, 而 Wellington 編號為 13)，先隨機選定一個整數 m ，再從編號為1的地區開始限電，以此之後的第m個地區為下一個斷電的地方，若計算到最後一個編號則從頭開始循環，並拒除已經斷過電的地區，例如當 N=17, m=5，則各地區停電的順序為1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7。

本問題要求最後一個斷電的地區為編號13的Wellington地區(因為那是電場總部的所在地)，所以對於不同的 N 值必須小心地選擇 m 值使得編號13為最後停電的地區。

請寫出一個程式讀取 N 值，並計算達成條件要求的最小 m 值為何。

Input and Output

輸入會有許多列測試資料，每一列表示共有 N 個地區， ，當N=0時表示資料結束。

請在每一列輸出每組測試資料的最小m值為何。

Sample input

17
0

Sample output

7

原文出處

121 - Pipe Fitters

Background

Filters(一種程式，用於資料過濾並重新格式化輸出)是UNIX系統上的一個重要的程式類別，而管線(pipe)是作業系統裡的一個概念，能讓資料在行程(processe)間流通(並使多個filter能輕易地串在一起)。

本題討論如何使裝進容器內的管線(pipe)數量最大化，但這並非是一個裝箱問題 (bin packing problem)，而是一個pipe fitting problem。

The Problem

有一間工廠專門生產一種直徑固定的管線，所有的管線都被放在四方形的容器中儲存，而容器會有不同的大小。所有管線皆以列順序被儲存，所以每一列之間不會有多餘的空間(不過一列的最後可能會有多餘的空間)，一列中的每個管線都是緊密地靠在一起。如下面四方形的橫截面圖，管線會有兩種置放的方式，一種是格子狀，如左邊的兩個圖；另一種是斜著擺，如右邊的兩個圖。

注意，雖然從圖中不一定能明顯地看出來，但是必須要強調的是相鄰兩列之間不會有多餘的空隙，任兩列(或與箱子的底部)都是緊密接觸的。當把箱子裝滿之後可能會有多餘的空間，但還不足以多放進一根管線，這樣的空間一般都會用東西填充，好讓在運輸途中的管線不會滾來滾去。

The Input

輸入會給定一連串容器橫截面的長度與寬度，每一個橫截面的長寬會在一列的兩個數值中給定，並以空白字元隔開，長寬的單位大小等於管線的直徑。所有尺寸皆小於，注意與視為相同。

The Output

針對每一組容器截面的尺寸，你的程式必須輸出該容器最多可以放進幾根管線，數量必須是整數。如果產生最大數量的排列方式是以格子狀排列，則在數量的後面加上 grid，若是以斜偏的方式排列則請輸出 skew，若任兩種排列方式都能放進最大數量的管線，則請優先輸出 grid。

Sample Input

3 3
2.9 10
2.9 10.5
11 11

Sample Output

9 grid
29 skew
30 skew
126 skew

原文出處

119 - Greedy Gift Givers

The Problem

有一群會互相贈送禮物的朋友，每次收到與送出禮物的價值皆不同，本題要來計算每個人損益情形。

本題中每人都設定一筆買禮物的預算，預算會平均分配買等值的禮物送給他的朋友們。

然而，任何小團體中總有一些人比較慷慨(或是與其他的的關係比較好)，也總有一些人比較有錢。

給你一群朋友的資料，包含每人買禮物的預算，及禮物會送給那些朋友。你必須寫一個程式來計算每個人的損益情形。

The Input

輸入會有多組測試資料表示每個小團體，資料如下：

• 小團體的人數。
• 小團體中每人的名字。
• 接下來的每一列會有每位送禮人的名字、禮物的總預算、送禮的人數、送出禮物給那些朋友。

所有名字皆以小寫字元表示，每個團體最多不會超過10個人，而名字的長度最多不會超過12個字元，預算的數目為小於2000的非負整數。

輸入會有許多小團體的資料，並以EOF結束。

The Output

請依序在每一列輸出每人的姓名及其淨利(或淨損)，輸出的順序請依照他們在輸入中出現的順序。

不同團體之間必須有一空行格開。每個禮物的價值一定是整數，預算會平均分配買等值禮物送給朋友，預算會儘可能地花完除非有除不盡的餘數，剩餘的錢就當做自已的淨利留下來。

Sample Input

5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0
3
liz steve dave
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz

Sample Output

dave 302
laura 66
owen -359
vick 141
amr -150

liz -3
steve -24
dave 27

原文出處

117 - The Postal Worker Rings Once

Background

圖論是計算機科學的一個重要分支，至少可追朔到十八世紀尤拉(Euler)所解決著名的七橋問題(Seven Bridges of Königsberg)，許多最佳化問題都涉及到如何有效處理圖形問題。

本問題要求計算郵差徒步送信的最短路徑。

The Problem

給定數條街道的資訊(以十字路口連接不同道路)，你的程式必須計算走過全部的街道所需的最短距離，路徑的起點與終點必須一致。

你可以想像在現實世界中有一位郵差，他先把車開到十字路口之後再走路到各個巷弄把附近需要遞送的郵件一一送完，之後再走到車子所在的路口開往下個地點送信。

行經一條街道的距離直接等於街道的長度(不管該道路有沒有信要送，都必須走完整條道路的距離)。

本問題中，在路口交會的所有道路數目被稱做該路口的"層級"(degree)，最多只會有兩個路口的"層級"為奇數，其他所有路口皆為偶數，也就是只會有偶數條道路在此路口交會。

The Input

一組輸入資料最少會有一條以上的道路，每條道路都有其名稱，每條路一列，直到遇見名稱為"deadend"的輸入，注意deadend並不包含在該組道路裡面。路名的第一個字元與最後一個字元表示該街道兩端的路口，街道名稱的長度表示該街道的距離長度，所有路名皆以小寫字母表示。

例如，名稱為foo的道路表示它兩端的路口為 f 與 o，且長度為3，而名稱為computer的道路兩端路口為 c 與 r，長度為8。不會有路名的頭尾字元是相同的，且最多只會有一條道路直接連接任兩個路口。另外就如之前提及，所連接的道路數量為奇數的路口最多只會有兩個。所有的路口都是互相連通的。

The Output

針對每組道路資訊，請輸出郵差走過所有該組道路最少一次的最短路徑長度，請每組依序輸出。

Sample Input
one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend

Sample Output
11
114

---

原文出處

143 - Orchard Trees

果農在他的四方形果園內整齊地種滿果樹，我們可以假設每顆果樹在xy的整數位置上一顆顆地排列好，以左下角為坐標的原點，如下圖所示：

現在我們在果園內圍起一個三角形，三角形頂點的(x, y)位置皆在0.0到100.0的範圍內，而果樹只會種在整數位置1到99上，圖中顯示兩個可能的三角形位置。

請你寫一個程式計算三角形內有幾顆果樹，為了簡化問題，請假設果樹只有一個點的大小，而在三角形邊上的果樹視為在三角形內。

Input and Output

輸入的每一列會有六個浮點數，表示三角形三個頂點的(x, y)座標，其範圍介於 0.00 到 100.00 之間，最後會以六個0表示輸入結束。

請在每一列輸出每一個三角形內有幾顆果樹，請靠右對齊輸出四個字元寬的整數。

Sample input

1.5 1.5  1.5 6.8  6.8 1.5
10.7 6.9  8.5 1.5  14.5 1.5
0 0 0 0 0 0

Sample output

  15
  17

原文出處

156 - Ananagrams

許多填字遊戲的玩家很擅長分析回文構詞(anagrams)，即相同字母但不同排列順序的不同單字集合，例如：OPTS, SPOT, STOP, POTS 與 POST。然而並非所有單字都有這種特質，不論你怎麼排列也拼不出有意義的單字，這種單字我們稱之為ananagrams，例如QUIZ。

很顯然地，一個單字是否為ananagram取決於我們認識多少單字，你也許會認為ATHENE是一個ananagram，不過化學家們馬上可以找出另一個單字ETHANE(乙烷)。如果我們把所有英文單字都列入考慮的話，這樣會沒完沒了，所以我們就限縮可能的單字集合，例如限定與音樂相關的單字，這樣SCALE(音階)就是一個ananagram(LACES蕾絲不在集合內)，而NOTE(音符)有一個對應的單字TONE(音色)。

請你寫一個程式從一組單字集合內找出那些是ananagram。注意，只有一個字母的單字也算是ananagram，因為它們根本就沒辦法被重組。全部的單字不會超過1000個。

Input

輸入會有許多列，每一列有許多單字，一列的總長度不會超過80個字元，每個單字最多有20個字元，且全為小寫，單字不會被拆成兩列，單字之間最少會以一個空白字元隔開。注意，相同的單字若只有字母大小寫不同的差別，則把它們視為同一組回文構詞，例如 tIeD 與 EdiT 互為回文構詞，所以它們都不是ananagram。讀到 # 符號表示已檔案結束。

Output

請輸出所有ananagram單字，每列輸出一個。輸出時請按字典順序列出(區分大小寫)。最少會有一個ananagram單字。

Sample input

ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb  eye  Rides dealer  NotE derail LaCeS  drIed
noel dire Disk mace Rob dries
#

Sample output

Disk
NotE
derail
drIed
eye
ladder
soon

原文出處

165 - Stamps

Nova Mareterrania政府要求各式法院文件皆須貼上郵票，這樣政府才能從中抽一筆稅，現行的法規規定每一種文件上面的郵票數目都有其上限，此時政府需要知道應該發行幾種不同面額的郵票才能在郵票數目受限的情況下儘可能的產生最多組總面額值。郵票面額以1塊錢為單位。

經過研究，政府的數學家們得出一個公式：n(h,k)。h為文件上可以貼的最大郵票張數，k表示郵票共有幾種面額可供選擇，n為在h, k既定的情況下所產生的總價值由1開始連號到最大值n。例如當h=3, k=2且面額選定為$1 與 $4時，可以產生總價值 $1 ~ $6的組合(另有 $8, $9 與 $12 的組合)，然而，如果h, k值不變的情況下，面額選為$1與$3時，則可以組合出 $1 ~ $7 的組合($9也是一種組合)，$7是可產生連號的最大值，所以 n(3,2) = 7。

不幸的是，n(h,k)公式及其面額對照表不見了，雖然它被發表在政府某一份刊物上，但誰也記不起來到底是那一份刊物。而當初找出公式的三名研究員有兩名因為太過無聊而死了，第三位已經離職跑去當夜間燈塔看守人，因為這份工作比較有機會與人群接觸。

現在這份屎缺只好交給身為替代役男的你，看慣公務體系經常偽造假資料的你會懷疑公式其實從一開始就不存在，所以你決定寫一個程式找出當h, k給定的情況下最佳的面額組合 n(h,k)。

Input

輸入會有許多列，每一列有兩個整數h, k，檔案最後會以(0 0)結束。基於技術上的理由，h與k值的總合最多到9(因為總統打獵時不小心擦槍走火誤傷了自已的小指，大於9的數字他就不會算了)。

Output

對應每組(h, k)的資料輸出一列，該列前k個整數表示所選擇的k種郵票面額，每個整數佔3個字元寬，接下來請輸出一個空白，一個箭頭(->)與最大的n(h,k)值，n(h,k)值也佔3個字元寬。

Sample input

3 2
0 0

Sample output

  1  3 ->  7

原文出處