Problem 7 (排序 16%)
排序在電腦科學中是一個重要的部分，在這個問題中將限定使用一種排序方式，就是你只能交換相鄰的2個元素。將數列由小到大排序，並計算出最少要交換幾次才能排好。例如給你1 2 3，那需要交換的次數為0，因為已經排好了。例如給你2 3 1這個數列，第一次交換1跟3變成2 1 3，第二次交換2跟1變成1 2 3，因此最少需要交換2次才可排好。
輸入說明：輸入之奇數列為下一行數列中的個數，偶數列為數列資料，代表一組測試資料。每個數字與數字間的區隔為一個空白符號，當奇數列為0時表示結束。(請參照輸入範例)
輸入範圍：每個數列最少有2個數字，最多不超過100個。每個數列中的數字皆大於0，小於1000，且不重覆。
輸入範例：test7.txt
3
1 2 3
3
2 3 1
0
輸出說明：對每一組輸入資料，輸出最少需要交換的次數。(請參照輸出範例)
輸出範例：result7.txt
0
2
2011年10月17日 星期一
96模擬 Problem 6 (排列組合
Problem 6 (排列組合 17%)
請設計一個程式，可以將一組數字、字母或符號進行排列，以得到不同的組合順序，例如123這三個數的排列組合有：123、132、213、231、312、321六組；或是ABC這三個字母的排列組合有：ABC、ACB、BAC、BCA、CAB、CBA六組。
輸入說明：第一列為要排列的列數，第二列及以後為一組由數字、字母或符號組成的字串。(請參照輸入範例)
輸入範圍：每個數字、字母或符號皆為一個字元，每組最少為3個字元，最多不超過10個，且不重覆。
輸入範例：test6.txt
2
213
ABC
輸出說明：輸出不同的組合順序，順序規則如下：請按照字典排序，由左到右，由上到下，由小到大排列。(請參照輸出範例)
輸出範例：result6.txt
123
132
213
231
312
321
ABC
ACB
BAC
BCA
CAB
CBA
請設計一個程式，可以將一組數字、字母或符號進行排列，以得到不同的組合順序，例如123這三個數的排列組合有：123、132、213、231、312、321六組；或是ABC這三個字母的排列組合有：ABC、ACB、BAC、BCA、CAB、CBA六組。
輸入說明：第一列為要排列的列數，第二列及以後為一組由數字、字母或符號組成的字串。(請參照輸入範例)
輸入範圍：每個數字、字母或符號皆為一個字元，每組最少為3個字元，最多不超過10個，且不重覆。
輸入範例：test6.txt
2
213
ABC
輸出說明：輸出不同的組合順序，順序規則如下：請按照字典排序，由左到右，由上到下，由小到大排列。(請參照輸出範例)
輸出範例：result6.txt
123
132
213
231
312
321
ABC
ACB
BAC
BCA
CAB
CBA
2011年10月12日 星期三
96模擬 Problem 3 (積木方塊
Problem 3 (積木方塊 13%)
3歲的小明喜歡玩他的方塊積木，他總是把方塊疊在一起，形成高度不一的方塊堆。然後他說：這是一面牆。5歲的姊姊小美聽到了就跟小明說：真正的牆高度應該要一樣才行。小明聽了覺得有道理，於是決定要搬動一些方塊使所有方塊堆的高度一樣。如下圖。由於小明是個懶惰的小孩，他想要搬動最小數目的方塊，以達成這個目的，你能幫助他嗎？
(請參照 前‧積木方塊 的文章)
輸入說明：輸入檔案中包含好幾組資料，每組資料有2列，第一列有一個數字n，代表有幾堆方塊。第二列有n個數字，分別代表這n堆方塊的高度hi。令1 n 50、1 hi 100。方塊的總數一定可以整除堆數n，也就是說，一定可以使所有的方塊堆同樣高度。如果輸入的n=0，代表輸入結束。(請參照輸入範例)
輸入範例：test3.txt
6
5 2 4 1 7 5
3
1 1 1
0
輸出說明：對每一組輸入資料，輸出需搬動方塊的最小數目，以使所有的方塊堆成同一高度。(請參照輸出範例)
輸出範例：result3.txt
5
0
3歲的小明喜歡玩他的方塊積木，他總是把方塊疊在一起，形成高度不一的方塊堆。然後他說：這是一面牆。5歲的姊姊小美聽到了就跟小明說：真正的牆高度應該要一樣才行。小明聽了覺得有道理，於是決定要搬動一些方塊使所有方塊堆的高度一樣。如下圖。由於小明是個懶惰的小孩，他想要搬動最小數目的方塊，以達成這個目的，你能幫助他嗎？
(請參照 前‧積木方塊 的文章)
輸入說明：輸入檔案中包含好幾組資料，每組資料有2列，第一列有一個數字n，代表有幾堆方塊。第二列有n個數字，分別代表這n堆方塊的高度hi。令1 n 50、1 hi 100。方塊的總數一定可以整除堆數n，也就是說，一定可以使所有的方塊堆同樣高度。如果輸入的n=0，代表輸入結束。(請參照輸入範例)
輸入範例：test3.txt
6
5 2 4 1 7 5
3
1 1 1
0
輸出說明：對每一組輸入資料，輸出需搬動方塊的最小數目，以使所有的方塊堆成同一高度。(請參照輸出範例)
輸出範例：result3.txt
5
0
96模擬 Problem 1 (最大公約數
Problem 1 (最大公約數 12%)
利用歐基里德輾轉相除法寫一個程式。輸入兩個正整數，輸出其最大公約數。輸入數值的大小限制於3到1000之間。
輸入說明：每一列由二個數字所組成，為一組測試資料。每個數字與數字間的區隔為一個空白符號，當為0 0時表示結束。(請參照輸入範例)
輸入範例：test1.txt
78 64
26 39
0 0
輸出說明：對於每組測試資料，輸出最大公約數。(請參照輸出範例)
輸出範例：result1.txt
2
13
利用歐基里德輾轉相除法寫一個程式。輸入兩個正整數，輸出其最大公約數。輸入數值的大小限制於3到1000之間。
輸入說明：每一列由二個數字所組成，為一組測試資料。每個數字與數字間的區隔為一個空白符號，當為0 0時表示結束。(請參照輸入範例)
輸入範例：test1.txt
78 64
26 39
0 0
輸出說明：對於每組測試資料，輸出最大公約數。(請參照輸出範例)
輸出範例：result1.txt
2
13
2010年10月29日 星期五
戰艦謎題
內容 ：
在一個2x2的格子圖形中，有三艘各佔一個格子的戰艦，戰艦的位置均在格子的範圍內。三艘戰艦重量皆不同，從1噸到3噸各有一艘，因為大霧瀰漫不知正確位置，僅知道每一列與每一行的總重量，請問聰明的你，知道每一艘戰艦的正確位置嗎？
舉例來說，如果我們知道每一列與每一行的總重量如下圖：
囗囗５
囗囗１
４２
那麼這個戰艦謎題的一組正確答案如下圖：
３２５
１０１
４２
注意：我們給的輸入資料不一定只有一組正確答案，這時候你只需輸出其中一組正確答案即可。此外，我們給的輸入資料有可能沒有正確的答案，這時候只需輸出"No solutions."即可。
輸入說明 ：
總共有四個整數，每個數值間以一個空白字元隔開，這些數字個值均介於0到5之間。前2個整數依序表示每一列(row)的總重量，接下來的2個整數依序表示每一行(column)的總重量。
輸出說明 ：
請輸出4個整數，分成兩列，每列含有2個整數，整數中間以一個空白隔開，表示2x2的格子中，停在每個位置的戰艦重量。其中以0表示沒有戰艦。(範例一就是上圖的例子)如果沒有解答請輸出 "No solutions."
範例輸入 ：
輸入範例一：
5 1 4 2
輸入範例二：
3 3 1 5
輸入範例三：
3 2 3 4
範例輸出 ：
輸出範例一：
3 2 1 0
輸出範例二：
0 3 1 2
輸出範例三：
No solutions.
在一個2x2的格子圖形中，有三艘各佔一個格子的戰艦，戰艦的位置均在格子的範圍內。三艘戰艦重量皆不同，從1噸到3噸各有一艘，因為大霧瀰漫不知正確位置，僅知道每一列與每一行的總重量，請問聰明的你，知道每一艘戰艦的正確位置嗎？
舉例來說，如果我們知道每一列與每一行的總重量如下圖：
囗囗５
囗囗１
４２
那麼這個戰艦謎題的一組正確答案如下圖：
３２５
１０１
４２
注意：我們給的輸入資料不一定只有一組正確答案，這時候你只需輸出其中一組正確答案即可。此外，我們給的輸入資料有可能沒有正確的答案，這時候只需輸出"No solutions."即可。
輸入說明 ：
總共有四個整數，每個數值間以一個空白字元隔開，這些數字個值均介於0到5之間。前2個整數依序表示每一列(row)的總重量，接下來的2個整數依序表示每一行(column)的總重量。
輸出說明 ：
請輸出4個整數，分成兩列，每列含有2個整數，整數中間以一個空白隔開，表示2x2的格子中，停在每個位置的戰艦重量。其中以0表示沒有戰艦。(範例一就是上圖的例子)如果沒有解答請輸出 "No solutions."
範例輸入 ：
輸入範例一：
5 1 4 2
輸入範例二：
3 3 1 5
輸入範例三：
3 2 3 4
範例輸出 ：
輸出範例一：
3 2 1 0
輸出範例二：
0 3 1 2
輸出範例三：
No solutions.
2010年10月28日 星期四
最長共同字串
內容 ：
序列1:
序列 2:
給你2個字串，請你輸出他們的最長共同子字串（longest common subsequence）的長度。例如：給你以下2個字串：
abcdgh
aedfhr
他們的最長共同子字串為adh，長度為3。
輸入說明 ：
輸入含有多組測試資料。每一組測試資料2列，分別代表這2個字串（最多1000個字元）。
輸出說明 ：
每組測試資料輸出他們的最長共同子字串（longest common subsequence）的長度。
範例輸入 ：
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn
範例輸出 ：
4
3
26
14
序列1:
序列 2:
給你2個字串，請你輸出他們的最長共同子字串（longest common subsequence）的長度。例如：給你以下2個字串：
abcdgh
aedfhr
他們的最長共同子字串為adh，長度為3。
輸入說明 ：
輸入含有多組測試資料。每一組測試資料2列，分別代表這2個字串（最多1000個字元）。
輸出說明 ：
每組測試資料輸出他們的最長共同子字串（longest common subsequence）的長度。
範例輸入 ：
a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn
範例輸出 ：
4
3
26
14
Lotto
內容 ： 正體->简体
為了呼應台灣電腦彩券的發行，我們再次推出跟組合有關的題目。你在買彩券的時候一定會挑你喜歡的數字吧！（雖然理論上不會增加你的中獎機率，但是你還是會選擇你的Lucky Number）我們的問題是：假設共有49個號碼，而你必須在你的 k （k>6）個Lucky Number中挑6個號碼作為一張彩券的數字組合。例如：你的Lucky Number的集合是{1,2,3,5,8,13,21,34}以就是說 k=8 ，那麼你就有C(8,6)=28種可能的彩券組合：
[1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34].
你的任務是讀入k以及Lucky Number的集合，然後輸出所有可能的組合。
輸入說明 ：
每筆測試資料一行，每行的第1個整數代表 k（ 6 < k < 1 3 ） 。 接下來的k個整數代表Lucky Number的集合，此集合已經按數字由小到大排好。k=0代表輸入結束。
輸出說明 ：
對每一筆測試資料，輸出其所有可能的組合，每個組合一行。請注意輸出組合的順序需由小到大排列。測試資料之間請空一行。請參考Sample Output。
範例輸入 ：
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0
範例輸出 ：
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
為了呼應台灣電腦彩券的發行，我們再次推出跟組合有關的題目。你在買彩券的時候一定會挑你喜歡的數字吧！（雖然理論上不會增加你的中獎機率，但是你還是會選擇你的Lucky Number）我們的問題是：假設共有49個號碼，而你必須在你的 k （k>6）個Lucky Number中挑6個號碼作為一張彩券的數字組合。例如：你的Lucky Number的集合是{1,2,3,5,8,13,21,34}以就是說 k=8 ，那麼你就有C(8,6)=28種可能的彩券組合：
[1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34].
你的任務是讀入k以及Lucky Number的集合，然後輸出所有可能的組合。
輸入說明 ：
每筆測試資料一行，每行的第1個整數代表 k（ 6 < k < 1 3 ） 。 接下來的k個整數代表Lucky Number的集合，此集合已經按數字由小到大排好。k=0代表輸入結束。
輸出說明 ：
對每一筆測試資料，輸出其所有可能的組合，每個組合一行。請注意輸出組合的順序需由小到大排列。測試資料之間請空一行。請參考Sample Output。
範例輸入 ：
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0
範例輸出 ：
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
電費系統
內容 ： 正體->简体
假設你身為一個台電工程師，你正要為 GOGO 百貨的電梯設計一套電費計算系統，來計算GOGO 百貨的電梯每天所耗的電費是多少。已知電梯所耗的電力會和它所運作的樓層成正比，但是電梯下樓比上樓要省電。所以想請你根據下面這個規則，設計一套電費計算系統。
(1) 電梯上樓時，每經過一個樓層，要花電費 20 元。
(2) 電梯下樓時，每經過一個樓層，要花電費 10 元。
(3) 你可以假設電梯停在某一個樓層時不會耗電。
舉例來說：今天有一個電梯從2 樓到8 樓再到5 樓，則所耗的電費為：從2樓到8 樓，所耗的電費是(8-2) x 20 = 120 元。電梯從8 樓到5 樓，所耗的電費是(8-5) x 10 = 30 元。所以總共花了150 元。
輸入說明 ：
輸入檔中會有多筆資料，第一行是一個整數 N(1
輸入測資中的電梯樓層最高不會超過 101 樓。
輸出說明 ：
請根據電梯上下運作的樓層，計算出在一日中電梯運作所花的電費。（為了節能減碳，每日電費最高不會超過10,000 元。）
範例輸入 ：
3
2 8 5
7
2 9 7 3 4 6 1
0
範例輸出 ：
150
310
假設你身為一個台電工程師，你正要為 GOGO 百貨的電梯設計一套電費計算系統，來計算GOGO 百貨的電梯每天所耗的電費是多少。已知電梯所耗的電力會和它所運作的樓層成正比，但是電梯下樓比上樓要省電。所以想請你根據下面這個規則，設計一套電費計算系統。
(1) 電梯上樓時，每經過一個樓層，要花電費 20 元。
(2) 電梯下樓時，每經過一個樓層，要花電費 10 元。
(3) 你可以假設電梯停在某一個樓層時不會耗電。
舉例來說：今天有一個電梯從2 樓到8 樓再到5 樓，則所耗的電費為：從2樓到8 樓，所耗的電費是(8-2) x 20 = 120 元。電梯從8 樓到5 樓，所耗的電費是(8-5) x 10 = 30 元。所以總共花了150 元。
輸入說明 ：
輸入檔中會有多筆資料，第一行是一個整數 N(1
輸入測資中的電梯樓層最高不會超過 101 樓。
輸出說明 ：
請根據電梯上下運作的樓層，計算出在一日中電梯運作所花的電費。（為了節能減碳，每日電費最高不會超過10,000 元。）
範例輸入 ：
3
2 8 5
7
2 9 7 3 4 6 1
0
範例輸出 ：
150
310
科學記號
內容 ： 正體->简体
科學上採用的數字常寫成 a × 10n 的形式﹐其中 1 ≤ a < 10﹐n 是整數﹐
例如：(一) 光速是每秒 300,000,000 公尺﹐若取一位有效數字，
記為 3 × 108 公尺／秒。
(二) 電子的質量是0.000,000,000,000,000,000,000,000,000,909 公克，
若取二位有效數字，記為 9.1 × 10-28 公克。
輸入說明 ：
輸入檔中有多筆測試資料。每筆測試資料第一行有一個正整數 N, （1 ≦ N ≦ 100），代表有N筆測試資料。
接下來，有N行，每行有二個數字，第二數字表示取幾位有效數字。
須四捨五入!
輸出說明 ：
對於每筆測資，輸出一行此筆資料的科學記號。
範例輸入 ：
2
300,000,000 4
0.000,000,000,000,000,000,000,000,000,909 2
範例輸出 ：
3.000x10(8)
9.1x10(-28)
科學上採用的數字常寫成 a × 10n 的形式﹐其中 1 ≤ a < 10﹐n 是整數﹐
例如：(一) 光速是每秒 300,000,000 公尺﹐若取一位有效數字，
記為 3 × 108 公尺／秒。
(二) 電子的質量是0.000,000,000,000,000,000,000,000,000,909 公克，
若取二位有效數字，記為 9.1 × 10-28 公克。
輸入說明 ：
輸入檔中有多筆測試資料。每筆測試資料第一行有一個正整數 N, （1 ≦ N ≦ 100），代表有N筆測試資料。
接下來，有N行，每行有二個數字，第二數字表示取幾位有效數字。
須四捨五入!
輸出說明 ：
對於每筆測資，輸出一行此筆資料的科學記號。
範例輸入 ：
2
300,000,000 4
0.000,000,000,000,000,000,000,000,000,909 2
範例輸出 ：
3.000x10(8)
9.1x10(-28)
2010年10月26日 星期二
隔熱紙
內容 ：
喵嗚建設公司最近由北到南蓋了一整排共n棟的大樓，且每棟大樓是緊緊貼在一起的
而喵嗚建設公司希望能夠帶給住戶舒適的住宅環境，因此決定在東面窗上貼滿隔熱紙
然而預算有限，不能有任何隔熱紙被浪費，又切割隔熱紙是一向充滿麻煩的工程
你可以幫喵嗚建設公司算出至少要幾張矩形的隔熱紙才能貼滿整排大樓的東側嗎？
輸入說明 ：
第一行有一個正整數 n(n<=100000)，代表有幾棟大樓
接下來n行每行有兩個正整數(<=1,000,000,000)，依序代表每棟大樓的寬度及高度
輸出說明 ：
輸出最少所需要的隔熱紙數
範例輸入 ：
5
1 2
1 3
2 2
2 5
1 4
範例輸出 ：
4
喵嗚建設公司最近由北到南蓋了一整排共n棟的大樓，且每棟大樓是緊緊貼在一起的
而喵嗚建設公司希望能夠帶給住戶舒適的住宅環境，因此決定在東面窗上貼滿隔熱紙
然而預算有限，不能有任何隔熱紙被浪費，又切割隔熱紙是一向充滿麻煩的工程
你可以幫喵嗚建設公司算出至少要幾張矩形的隔熱紙才能貼滿整排大樓的東側嗎？
輸入說明 ：
第一行有一個正整數 n(n<=100000)，代表有幾棟大樓
接下來n行每行有兩個正整數(<=1,000,000,000)，依序代表每棟大樓的寬度及高度
輸出說明 ：
輸出最少所需要的隔熱紙數
範例輸入 ：
5
1 2
1 3
2 2
2 5
1 4
範例輸出 ：
4
畢業旅行
內容 ：
多年來友情的羈絆，終於將在這畢業的季節開花結果。
這幾天，班上同學們無時無刻都熱烈討論著畢業旅行的地點。
小明說，如果要去六福村，可以順便去小人國；
小美說，如果去了恆春的話，墾丁就在幾十公里外了，一定也要去玩；
小華表示，小鬼湖跟大鬼湖好像很近，似乎都是很有趣的地方。
身為班長，聽到同學這麼多「去了哪裡也可以去哪裡」的資訊後，
你決定要為班上的同學們，找到一個能玩最多景點的畢業旅行。
輸入說明 ：
有多組測試資料，以 EOF 結束。
每組測試資料的第一行有兩個正整數 n (n<=1000000) 和 m (m<=100000)，
表示景點有 n 個，編號為 0 ~ n-1。
接下來有 m 行，每行有兩個整數 a 和 b (0<=a,b
輸出說明 ：
輸出一個數字，表示畢業旅行最多可以玩的景點數量。
範例輸入 ：
6 4
0 1
2 3
1 3
5 4
1000000 0
1000000 1
0 999999
範例輸出 ：
4
1
2
多年來友情的羈絆，終於將在這畢業的季節開花結果。
這幾天，班上同學們無時無刻都熱烈討論著畢業旅行的地點。
小明說，如果要去六福村，可以順便去小人國；
小美說，如果去了恆春的話，墾丁就在幾十公里外了，一定也要去玩；
小華表示，小鬼湖跟大鬼湖好像很近，似乎都是很有趣的地方。
身為班長，聽到同學這麼多「去了哪裡也可以去哪裡」的資訊後，
你決定要為班上的同學們，找到一個能玩最多景點的畢業旅行。
輸入說明 ：
有多組測試資料，以 EOF 結束。
每組測試資料的第一行有兩個正整數 n (n<=1000000) 和 m (m<=100000)，
表示景點有 n 個，編號為 0 ~ n-1。
接下來有 m 行，每行有兩個整數 a 和 b (0<=a,b
輸出說明 ：
輸出一個數字，表示畢業旅行最多可以玩的景點數量。
範例輸入 ：
6 4
0 1
2 3
1 3
5 4
1000000 0
1000000 1
0 999999
範例輸出 ：
4
1
2
2010年10月25日 星期一
Find the Telephone
內容 ： 正體->简体
有些地方會用對應的字母來代替數字使得電話號碼更好記。如此一來 MY LOVE 就代表 69 5683。這不是萬靈丹，因為有的電話號碼並不能構成一個字或片語，而且 1 和 0 沒有對應的字母。
請讀入一個字串並依據下表轉成電話號碼。字串由大寫字母 (A-Z)、連字號(-) 和數字 1 和 0 所組成。
請讀入一個字串並依據下表轉成電話號碼。字串由大寫字母 (A-Z)、連字號(-) 和數字 1 和 0 所組成。
| 字母 | 數字 |
| ABC | 2 |
| DEF | 3 |
| GHI | 4 |
| JKL | 5 |
| MNO | 6 |
| PQRS | 7 |
| TUV | 8 |
| WXYZ | 9 |
輸入說明 ：
輸入含有若干字串。每個字串單獨在一行，有 C 個字元，1 ≤ C ≤ 30 。輸入以 EOF 作為結束。
輸出說明 ：
對於每個字串，請輸出相對應的電話號碼。
範例輸入 ：
1-HOME-SWEET-HOME
MY-MISERABLE-JOB
範例輸出 ：
1-4663-79338-4663
69-647372253-562
No Problem
內容 ：
最近程式競賽非常頻繁。儘管對參賽者來說這是好事，對出題者來說卻適得其反。目前出題者尚能維持一個題庫並說：「沒有問題！」但是如果繼續這樣下去不知道還能維持多久。
給你一年中每個月所出的題目數量及每個月所需要的題目數量。如果某個月需要 N 個題目，而當時的題庫數量不足，那麼該月的所有比賽均取消。請寫個程式來判斷是否有足夠的題目來辦比賽。記住，如果某個題目是在 X 月出的，該題目必須在 X+1 月或其後的月份才能使用。
給你一年中每個月所出的題目數量及每個月所需要的題目數量。如果某個月需要 N 個題目，而當時的題庫數量不足，那麼該月的所有比賽均取消。請寫個程式來判斷是否有足夠的題目來辦比賽。記住，如果某個題目是在 X 月出的，該題目必須在 X+1 月或其後的月份才能使用。
輸入說明 ：
每筆測資的第一行有一個整數 S (0≤S≤100)，表示年初已有的庫存題目數量。第二行有 12 個以空白隔開的整數，依序表示一到十二月每個月所出的題目數量。第三行也有 12 個以空白隔開的整數，依序表示每個月比賽所需要的題目數量。這些整數會介於 0 到 20 之間 (含)。負數代表輸入的結束。
輸出說明 ：
對於每筆測資，印出一行 "Case X:"，X 代表測資編號。然後印出 12 行，如果 i 月 (1≤i≤12) 有足夠的題目，則在第 i 行印出"No problem! :D" (沒有問題)，否則印出 "No problem. :(" (沒有題目)。
範例輸入 ：
5
3 0 3 5 8 2 1 0 3 5 6 9
0 0 10 2 6 4 1 0 1 1 2 2
-1
範例輸出 ：
Case 1:
No problem! :D
No problem! :D
No problem. :(
No problem! :D
No problem! :D
No problem! :D
No problem! :D
No problem! :D
No problem! :D
No problem! :D
No problem! :D
No problem! :D
提示 ：雖然這個題目最好用「陣列」來解，但是不用陣列也可以解，只是程式碼會重覆且冗長。Fibonacci numbers
內容 ： 正體->简体
費氏數列的處理，一向都是相當地費事。當然今天也不例外。各 位應該有聽說過費式數列，或許沒有聽過以費式數列為基底的數字表示法吧！費氏數列基本上就是 (1,1,2,3,5,8,...)，定義第零項、第一項都是1，自第二項起，每一項的數值皆等於前兩項的和。接下來我們來考慮費氏進位制：
說得單純一些，就是我們考慮將一個正整數 X 表示成費氏數列當中某些不重複項的和。例如
35 = 1 + 34 = 1 + 13 + 21 = 1 + 5 + 8 + 21 = 1 + 2 + 3 + 8 + 21
看起來有很多種表示法對吧？但若我們規定「選出來的數字不能有相鄰的項」，那麼一切就會變得簡單些了，例如：
35 = 1 + 34
30 = 1 + 8 + 21
28 = 2 + 5 + 21
12 = 1 + 3 + 8
7 = 2 + 5
巧合的是，可以證明恰好只有一種這樣的表示方法。
我們可以用類似二進位數的方法來表達這樣的一個正整數在「費氏進位制」底下長的樣子。
不過，現在費事的地方來了，我們要怎麼樣對兩個「費氏進位」的數字作加法呢？
這就是你的工作，給你兩個以費氏進位制 的數字，你必須把他們加起來，並且用費氏進位制表示出來。
說得單純一些，就是我們考慮將一個正整數 X 表示成費氏數列當中某些不重複項的和。例如
35 = 1 + 34 = 1 + 13 + 21 = 1 + 5 + 8 + 21 = 1 + 2 + 3 + 8 + 21
看起來有很多種表示法對吧？但若我們規定「選出來的數字不能有相鄰的項」，那麼一切就會變得簡單些了，例如：
35 = 1 + 34
30 = 1 + 8 + 21
28 = 2 + 5 + 21
12 = 1 + 3 + 8
7 = 2 + 5
巧合的是，可以證明恰好只有一種這樣的表示方法。
我們可以用類似二進位數的方法來表達這樣的一個正整數在「費氏進位制」底下長的樣子。
不過，現在費事的地方來了，我們要怎麼樣對兩個「費氏進位」的數字作加法呢？
這就是你的工作，給你兩個以費氏進位制 的數字，你必須把他們加起來，並且用費氏進位制表示出來。
輸入說明 ：
每兩行為一組測資，每個長度不會超過100個，每組測資以空白隔開
輸出說明 ：
請輸出結果，並每兩組之間空一行隔開
範例輸入 ：
10010
1
10000
1000
10000
10000
範例輸出 ：
10100
100000
100100
Number Transformation
內容 ：
給你一個數字S，你可以將A轉換成B藉由加上一個X，X是一個A的質因數(1跟A不考慮進去)，現在你的工作就是找出最少需要轉換次數把S轉換成T
EX: 6 12
6->9->12 2次
6->8-> 10->12 3次
EX: 6 12
6->9->12 2次
6->8-> 10->12 3次
輸入說明 ：
每組測資都有兩的數字S (1<=S<=100) & T (1<=T<=1000)，
兩個0代表結束，不用輸出任何數字 。
兩個0代表結束，不用輸出任何數字 。
輸出說明 ：
對於每個一個測資，除了0 0以外 ，請應出 “Case X: Y”，X從1開始算起，Y為S轉換到T的最小次數，若是無法轉換成功請書出-1
範例輸入 ：
6 12
6 13
0 0
範例輸出 ：
Case 1: 2
Case 2: -1
2010年10月22日 星期五
棒球九宮格
內容 ：
小明很喜歡棒球。某天晚上跟媽媽到家裡附近逛夜市，突然發現多了一個棒球九宮格的遊戲攤位(如圖一)。遊戲規則如下：一開始九宮格內會分別擺上一個木板，玩家站在距離九宮格板數公尺外，總共可以丟出九顆球。被命中的格子裡的木板會倒下；若球丟出範圍外，或是剛好丟在九宮格的框架上，則所有格子都會維持原樣。一旦將球丟出去，可用的球數就減少一，直到將九顆球丟完為止。
九顆球都丟完之後，夜市的老闆會根據倒下的格子來檢查連成幾條線，以決定獎品的好壞。依照老闆的規定，只要以下其中一組格子裡的木板同時倒下，則算連成一線：｛1,2,3｝、{4,5,6}、{7,8,9}、{1,4,7}、{2,5,8}、{3,6,9}。舉例來說，若2、3、5、7、8、9這六個格子中的木板都倒下，則2、5、8連成一線，且7、8、9也連成一線，總共連成兩條線。(請注意，依規則3、5、7不算連成一線。)此外，老闆也會根據丟到的格子號碼，計算"加碼積分"，提供額外的獎賞，詳細規則如下：丟到5號得2分，丟到{2、4、6、8}中的任一號碼得5分，丟到{1、3、7、9}中的任一號碼得8分。例如若2、5、8、9這四格被丟中，則加碼積分為20分。請注意，重複丟到的號碼只算一次分數。
請寫一個程式來模擬玩棒球九宮格的遊戲。為了方便貣見，我們將用二維座標來定義九宮格的位置，如圖二所示。每一格都是相同大小的正方形，7號格左下角的座標為(0,0)，3號格右上角座標為(30,30)。在模擬的過程中，會提供每一顆球丟在九宮格上的座標位置。為了簡化問題，若某顆球丟在九宮格上的座標位於某一格內，則判斷打到該格；如果座標位於某一格的邊上，則判斷為打到框架，沒有任何格子被打到。舉例來說，假設一顆球丟到座標位置為(7,13)的地方，由於落在4號格之內，判定打到4號格；假設有另一顆球打在(10,2)(或(10,20))的座標位置，則因為落在框架上，沒有任何格子被打到。當然如果座標落在九宮格外的區域，也沒有任何格子被丟中。
九顆球都丟完之後，夜市的老闆會根據倒下的格子來檢查連成幾條線，以決定獎品的好壞。依照老闆的規定，只要以下其中一組格子裡的木板同時倒下，則算連成一線：｛1,2,3｝、{4,5,6}、{7,8,9}、{1,4,7}、{2,5,8}、{3,6,9}。舉例來說，若2、3、5、7、8、9這六個格子中的木板都倒下，則2、5、8連成一線，且7、8、9也連成一線，總共連成兩條線。(請注意，依規則3、5、7不算連成一線。)此外，老闆也會根據丟到的格子號碼，計算"加碼積分"，提供額外的獎賞，詳細規則如下：丟到5號得2分，丟到{2、4、6、8}中的任一號碼得5分，丟到{1、3、7、9}中的任一號碼得8分。例如若2、5、8、9這四格被丟中，則加碼積分為20分。請注意，重複丟到的號碼只算一次分數。
請寫一個程式來模擬玩棒球九宮格的遊戲。為了方便貣見，我們將用二維座標來定義九宮格的位置，如圖二所示。每一格都是相同大小的正方形，7號格左下角的座標為(0,0)，3號格右上角座標為(30,30)。在模擬的過程中，會提供每一顆球丟在九宮格上的座標位置。為了簡化問題，若某顆球丟在九宮格上的座標位於某一格內，則判斷打到該格；如果座標位於某一格的邊上，則判斷為打到框架，沒有任何格子被打到。舉例來說，假設一顆球丟到座標位置為(7,13)的地方，由於落在4號格之內，判定打到4號格；假設有另一顆球打在(10,2)(或(10,20))的座標位置，則因為落在框架上，沒有任何格子被打到。當然如果座標落在九宮格外的區域，也沒有任何格子被丟中。
輸入說明 ：
輸入總共有9行。每一行有兩個整數x和y (-20 <= x,y <= 50，x與y由一個空白隔開)，代表球的座標。
輸出說明 ：
請輸出丟出9顆球之後，根據夜市老闆的規則總共連成幾條線；另外請根據丟到的格子號碼，算出加碼積分。
範例輸入 ：
輸入範例1：
7 13
10 2
5 8
-9 19
11 35
3 23
18 0
0 18
40 22
輸入範例2：
12 22
15 11
3 20
3 22
33 27
28 28
16 5
22 -5
35 35
範例輸出 ：
輸出範例1：
1 21
輸出範例2：
2 28
遊園接駁車
內容 ：
某一遊樂園分為水上樂園與探索樂園，旅客玩完水上樂園之後，接著便排隊搭乘單人客車進入探索樂園遊園。每部車只可搭載一名旅客進入探索樂園，旅客先到先搭車；如果某單人客車已經準備好要搭載旅客，但是此時並沒有等待中的旅客，那麼該輛車就必須等待。若旅客等待客車的時間超過 30 分鐘(包含30分鐘)就會放棄搭乘而離開園區。現在有一個由若干個旅客所組成的旅行團同時來到園區，請問在已知下列三個條件
(1) 該旅行團的旅客數量 (10<=m<=60)
(2) 該旅行團的個別旅客待在水上樂園的分鐘數 (1<=t<=60)
(3) 個別旅客環繞探索樂園的分鐘數 (1<=T<=60)
請撰寫程式計算至少需要幾部單人客車，才能滿足該旅行團所有的旅客，不讓旅客等超過30分鐘。 (m，t，T 皆為整數 )請輸出至少需要單人客車的數量 ?
輸入說明 ：
第一行為該旅行團人數，接下來每一行都有兩筆數據，第一筆代表個別旅客待在水上樂園的分鐘數，第二筆代表個別旅客環繞探索樂園的分鐘數。（輸入順序未必按照旅客待在水上樂園的分鐘數排列）
輸出說明 ：
至少需要單人客車的數量。
範例輸入 ：
11
5 30
40 30
35 5
15 10
30 20
10 40
45 5
50 5
5 10
35 5
50 30
5
10 20
20 30
10 45
10 50
15 30
範例輸出 ：
2
3
網路設計
內容 ：
某一城市欲建立都會網路，以使每一區公所均可連線到其他各區公所（可能直接連線或透過其他的區公所間接連線）。假設任兩個區公所之間的佈線成本為已知；每一條網路線均為雙向傳送。請寫一程式，印出哪些區公所之間需要施工佈線，以找出此城市使用最低成本完成此都會網路之佈線架構。
輸入說明 ：
第一列有兩個正整數n及m，其中n代表區公所個數(n<=10)，區公所代碼為W1、W2、W3…Wn。m代表有m個可能的佈線連結兩區公所。其後有m列，每一列之資料依序為兩區公所代碼，及連接此兩區公所之佈線成本。各項資料之間以一個空白分隔；佈線成本為一正整數。
輸出說明 ：
印出二列。第一列為佈線架構，印出數組資料，每一組資料為兩個區公所代碼，代表此兩個區公所需要施工佈線，每一組資料包含在一對括號之中。第二列為佈線總成本。各項資料之間以一個空白分隔。
範例輸入 ：
7 11
W1 W2 1
W1 W4 4
W2 W3 2
W2 W4 6
W2 W5 4
W3 W5 5
W3 W6 6
W4 W5 3
W4 W7 4
W5 W6 8
W6 W7 3
範例輸出 ：
(W1 W2) (W1 W4) (W2 W3) (W4 W5) (W4 W7) (W6 W7)
17
2010年10月19日 星期二
笑點在哪
內容 ：
對現代人而言，幽默感是社交生活非常重要的元素。
但時常我們講了一些自以為幽默的話，卻反而遭人白眼，這就是缺乏笑點 （ Ha-Ha point ） 的緣故。
至於笑點如何產生呢？
其實每個人的心中都有所謂的梗 （ pioneerLike ） ，當兩個人的梗交會時，我們就稱那個交點為笑點。（只有端點接觸也算交會）
現在給你N個同學（編號為 1 ~ N ）的梗，並有一些詢問，請你對於每個詢問，計算出笑點在哪。
但時常我們講了一些自以為幽默的話，卻反而遭人白眼，這就是缺乏笑點 （ Ha-Ha point ） 的緣故。
至於笑點如何產生呢？
其實每個人的心中都有所謂的梗 （ pioneerLike ） ，當兩個人的梗交會時，我們就稱那個交點為笑點。（只有端點接觸也算交會）
現在給你N個同學（編號為 1 ~ N ）的梗，並有一些詢問，請你對於每個詢問，計算出笑點在哪。
輸入說明 ：
第 1 行有一個整數 N ( N <= 1000 )，代表共有幾個同學。
以下 N 行，每行有 4 個整數，x1、y1、x2、y2，代表梗是由 ( x1 , y1 ) 到 ( x2 , y2 ) 的線段，這 N 行依序代表 1 ~ N 號同學的梗。
再來 1 行有 1 個整數 Q ( Q <= 10000 ) ，代表共有幾個詢問。
以下 Q 行每行有 2 個整數 a 和 b ，代表詢問同學 a 和同學 b 的笑點(兩個人的梗的交點就是笑點。)，這 Q 行每行代表 1 個詢問。
所有的輸入都在 int 的範圍內。
以下 N 行，每行有 4 個整數，x1、y1、x2、y2，代表梗是由 ( x1 , y1 ) 到 ( x2 , y2 ) 的線段，這 N 行依序代表 1 ~ N 號同學的梗。
再來 1 行有 1 個整數 Q ( Q <= 10000 ) ，代表共有幾個詢問。
以下 Q 行每行有 2 個整數 a 和 b ，代表詢問同學 a 和同學 b 的笑點(兩個人的梗的交點就是笑點。)，這 Q 行每行代表 1 個詢問。
所有的輸入都在 int 的範圍內。
輸出說明 ：
請針對每個詢問輸出笑點的座標，四捨五入到小數後3位。
如果詢問中 2 位同學的梗沒有交會，請輸出 "no humor" 。
如果詢問中 2 位同學有無限多個笑點，請輸出 "HAHAHAHAHA!" 。
輸出皆不含引號。
如果詢問中 2 位同學的梗沒有交會，請輸出 "no humor" 。
如果詢問中 2 位同學有無限多個笑點，請輸出 "HAHAHAHAHA!" 。
輸出皆不含引號。
範例輸入 ：
5
3 10 1 1
3 2 -2 2
1 1 -3 4
5 -2 -3 4
3 10 3 2
4
1 2
2 3
3 4
4 5
範例輸出 ：
1.222 2.000
-0.333 2.000
HAHAHAHAHA!
no humor
大朋友下樓梯
內容 ：
傳說，有個遊戲叫做大朋友下樓梯，這個遊戲有三種難度，簡單中等困難。
三種難度的差別是，簡單的難度大朋友一次只能下樓梯 1格
中等的是則是，大朋友一次可以下樓梯 1格或 2格
困難的比較具有挑戰性，大朋友一次可以下 1格、 2格或 3格
現在我們想知道，大朋友有幾種下樓梯的方法可以走到地下k樓
對了，有一個限制是，大朋友不能上樓梯只能下樓梯
三種難度的差別是，簡單的難度大朋友一次只能下樓梯 1格
中等的是則是，大朋友一次可以下樓梯 1格或 2格
困難的比較具有挑戰性，大朋友一次可以下 1格、 2格或 3格
現在我們想知道，大朋友有幾種下樓梯的方法可以走到地下k樓
對了，有一個限制是，大朋友不能上樓梯只能下樓梯
輸入說明 ：
給定兩個正整數 t, k ， t代表遊戲難度，值為1~3 分別代表，簡單中等困難。
k則是一個負數，代表地下k樓（0>k>-20）
包含多筆測試資料。
k則是一個負數，代表地下k樓（0>k>-20）
包含多筆測試資料。
輸出說明 ：
輸出大朋友走到地下K層後的方法數。
範例輸入 ：
1 -1
1 -2
2 -1
2 -2
2 -3
2 -4
3 -1
3 -2
3 -3
範例輸出 ：
1
1
1
2
3
5
1
2
4
訂閱：
文章 (Atom)