990 - Diving for Gold

John是一位寶物獵人，他知道附近海域所有沉在海裡的金幣的位置及深度，及其金幣的數量，不過他只帶了一個氧氣桶過來，所需的氧氣量可能不夠讓他將所有的寶物全都打撈上來，請你幫忙計算他最多可帶回多少金幣，需符合下列限制條件：

• 金幣所在 n 個不同的位置，以{(d1, v1), (d2, v2), ..., (dn, vn)}表示這 n 個位置的(深度, 金幣的數量)，n 最大為30。
• 氧氧桶最多可使用 t 秒，t 最多1000秒。
• 每一次潛下水面，他可帶回所有沉在該位置的金幣。
• 下沉所需的時間為 w * di，w 為一常數，di 表示深度。
• 浮起所需的時間為 2w * di，w為一常數，di 表示深度。
• 輸入的所有數值皆為整數。

Input

輸入有多組測試資料，每組資料的第一列有兩個整數分別表示 t, w，第二列有一個整數為 n，接下來的 n 列，每列有兩個整數分別表示金幣所在的深度di及數量vi。
每組測試資料間有一空行隔開。

Output

請在每組測試資料的第一列輸出John可找到的所有金幣的數量，第二列輸出共需潛水幾次，之後的每一列輸出每次潛水的深度及帶回的金幣數量，其輸出順序需與輸入資料的金幣出現順序相同。
請在每組輸出資料間以一列空行隔開。

Sample input

210 4
3
10 5
10 1
7 2

Sample output

7
2
10 5
7 2

---

原文出處

941 - Permutations

本題討論重新排列一個字串的組合方式，例如給定字串"abc"，可重新排列得到{"abc", "acb", "bac", "bca", "cab", "cba"}，長度為3的字串共有3!種排列方式。

給定一個字串S(長度小於等於20，全為小寫字元，且每個字元皆不相同)，及一個整數N(0 <= N < 20!)，請找出第N個排列方式(以字典順序由小到大排列，且第一個為編號0)，例如：

當S="abc"，N=0，其結果為"abc"。

當S="abc"，N=5，其結果為"cba"。

當S="abc"，N=3，其結果為"bca"。

當S="cba"，N=3，其結果為"bca"。

注意字串S的字元不一定由小到大排列。

Input

輸入資料的第一列有一個整數表示測試資料的組數，每組資料兩列，第一列表示一個字串S，第二列表示整數N。

Output

請依題意輸出字串。

Sample Input

2
abc
3
abcde
119

Sample Output

bca
edcba

---

原文出處

929 - Number Maze

在一個二維陣列迷宮，每個項以一個0~9的數字表示，如下所示。經上、下、左、右的移動過程中將所經過的數字作加總，請你從左上角(起點)到右下角(終點) 的所有可能路徑中，計算其數字總和最小的值為何。下圖的最小路徑數值總和為：0 + 3 + 1 + 4 + 5 + 4 + 2 + 5 = 24。

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

Problem

本題請你計算從左上角到右下角的路徑之最小數值總和，迷宮大小為NxM(1 <= N, M <= 999)。

Input

輸入資料的第一列有一個正整數表示測試資料的組數，每組資料的第一列為整數N，第二列為整數M，接下來有N列，每列有M個以一個空白字元隔開的整數，表示二維陣列的數值。

Output

請對每組測試資料輸出最小數值總和。

Sample Input

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

Sample Output

24
15

---

原文出處

920 - Sunny Mountains

下圖為群山被陽光照射的示意圖，被陽光照射到地方以紅線表示，本題請你計算所有被照射到的長度。為了簡化問題，我們假設陽光與地面平行，並給定山峰與山谷的位置。




位置以(x, y)表示，且 0 <= x <= 30000, 0 <= y <= 8848，最左邊的點其x=0，最右邊的點其y=0，所有點的數量 n <= 100。

Input
輸入資料的第一列有一個整數 C (0 < C < 100)表示測試資料的組數。
每組測試資料的第一列為整數N，表示有N個點，接下來有N個點的位置(x, y)，分別表示山峰或山谷。

Output
請對每組測試資料輸出上圖中紅色線段的總長度為何，請輸出到小數點後兩位。

Sample Input
2
11
1100 1200
0 500
1400 100
600 600
2800 0
400 1100
1700 600
1500 800
2100 300
1800 700
2400 500
2
0 1000
1000 0
Sample Output
1446.34
1414.21

原文出處

967 - Circular

Problem

「循環質數」定義為一質數不斷將最左邊的位數搬移到最右邊，每一次搬移後所得到的數亦為質數。例如質數19937為循環質數，因為依序將每一位數循環後所得到的數值亦為質數：19937, 99371, 93719, 37199, 71993。本題給定一個數字區間，請你寫程式找出此區間內的所有循環質數。

Input

輸入有多組測試資料，每組測試資料一列，每列有兩個整數 i, j，所有整數皆小於1,000,000且大於等於100。你可以假定 i 小於等於 j，請你找出介於 i, j之間(包含 i, j)所有循環質數的個數。輸入的最後以一個 -1 表示測試資料結束。

Output

若該組測試資料區間內沒有任何一個循環質數，請輸出"No Circular Primes."，若有一個請輸出"1 Circular Prime."，超過一個則輸出"n Circular Primes."，其中 n 表示大於1的整數。

Sample Input

1000 1100

100 120

100 1000

-1

Sample Output

No Circular Primes.

1 Circular Prime.

12 Circular Primes.

---

原文出處

991 - Safe Salutations

Problem

本題請你計算在一個有 2n 個點的圓上，使每個點都與另外一個點連成線且不會使任兩線段交叉的組合共有幾種。下圖是當有6個點時，所有組合情形。

Input

每組測試資料為一個整數 n，且每組資料以空行隔開，n表示圓上點的"對數"(即共有2n個點)，1 <= n <= 10。

Output

請依題意輸出每組資料的所有組合總數，並以空行隔開每組輸出。

Sample Input

4

Sample Output

14

---

原文出處

974 - Kaprekar Numbers

有一種稱為Kaprekar numbers的數，該數的平方可以分解成兩個整數，這兩個整數的和等於原數值。例如55的平方為55^2=3025，拆開分解成30與25兩數使得30+25=55。另外還有一個規則：分解出來的兩個整數必需大於零，所以10並非一個Kaprekar number，因為若10^2=100且10+0=10，但是由於第二個整數為0，所以10並非Kaprekar number。

The Problem

給定一對整數，請你找出介於這兩個整數之間所有的Kaprekar numbers。

Input

輸入的第一列有一個整數N(1 <= N <= 1000)，表示有幾組測試資料。接下來有N列，每列有兩個以空白字元隔開的整數INF與SUP(2 <= INF <= SUP <= 40000)，請出找出介於區間[INF, SUP]內的所有Kaprekar numbers。

Output

請在每組輸出資料的第一列輸出case #NUM(NUM表示測試資料的編號)。

接下來請你由小到大依序列出介於該組區間內的所有Kaprekar numbers，每個數獨立一列。若找不到Kaprekar number請輸出"no kaprekar numbers"

每組測試資料之間請輸出一列空行。

Example Input

3
2 90
30 35
50 55

Example Output

case #1
9
45
55

case #2
no kaprekar numbers

case #3
55

---

原文出處

914 - Jumping Champion

我們定義一種稱為"jumping champion"的數：介於兩個整數之間所有質數集合中，任兩相鄰質數的差值中選擇出現次數最多的那組差值即為"jumping champion"。

例如，連續的質數序列：2 3 5 7 11，任兩相鄰的差分別為1 2 2 4，因為差值2出現了兩次為最多，所以jumping champion等於2。

Problem

給定一對整數分別表示上界與下界，請你計算介於之間質數集合的jumping champion值。

Input

輸入資料的第一列為整數T表示測試資料的組數。每組資料一列分別有兩個整數L與U(0 <= L <= U <= 1000000)，並以一個空白字元隔開，分別表示下界與上界。

Output

每組資料請輸出一列，分別有兩種輸出格式：

• "The jumping champion is NUM" - 如果存在jumping champion且其值為NUM，請輸出此格式。
• "No jumping champion" - 找不到jumping champion(若上下界之間的質數小於兩個，或是出現頻率最高的差值不只一個)。

Sample Input

3

2 11

2 5

30 50

Sample Output

The jumping champion is 2

No jumping champion

The jumping champion is 4

---

原文出處

902 - Password Search

能夠順利傳遞加密訊息對於二次世界大戰的同盟國來說格外重要，訊息必需以密碼加密後傳遞，如果選用固定的密碼勢必會增加被破解的可能性，因此最好能時常更換密碼，這就表示新的密碼必需透過某種機制來傳遞，其中一種傳遞密碼的機制是把密碼嵌入訊息中，密碼本身會隨著訊息一起傳送出去，訊息接收者在已知密碼長度的情況下，尋找藏在訊息中的密碼。

長度為N的密碼可介由從訊息中尋找出現頻率最高且長度為N的子字串得到，找出密碼後，再把訊息中與密碼相同的片段刪除，再用密碼解密剩下的訊息。

Problem

本題會告訴你密碼的長度，請你從一段訊息中找出該密碼。例如假設密碼長度為3(N = 3)，且訊息為baababacb，則密碼為aba，因為它出現了兩次，而其他長度為3的子字串只出過一次(baa, aab, bab, bac, acb)。

Input

輸入包含多組測試資料，每組資料一列，資料開頭會有一個整數N(0 < N <= 10)表示密碼的長度，接著會有一串全為小寫字母的訊息。

Output

找出每組測試資料的密碼後，請分別在每一列印出密碼。

Sample Input

3 baababacb

Sample Output

aba  

---

原文出處

948 - Fibonaccimal Base

著名的費氏數列(Fibonacci sequence) 的前兩項為 0 與 1，之後的每一項為其前兩項的和，例如第三項為第一、二項的和(1=0+1)，第四項為第二、三項之和(3=1+2)。

i	0	1	2	3	4	5	6	7	8	9
Fib(i)	0	1	1	2	3	5	8	13	21	34

Figure 1 - 費氏數列前十項

在現實世界中不難發現費氏數列的縱跡，它有其重要的地位。另外，你可知所有正整數都可以用費氏數列中取部份項的和來表示嗎？說的再更精確一點：所有正整數都可以用費氏數列中取部份"不重複"的項來表示。例如，13可以下列不同的組合來表示{13}，或{5, 8}，或{2, 3, 8}，而17則可用{1, 3, 13}或{1, 3, 5, 8}來表示。由於所有正整數都可以用不重複的費氏數列的項次來表示，所以就可以把費氏數列的項次當作是"基底"(base)來編織出所有的正整數。但是由上面的列子可知其表示式可能不只一種，解決之道很簡單，就是規定任兩個被選中的項次不能在數列中相鄰，如此可保證所有正整數都只有唯一一組表示方式，這種限制規定是基於任兩個相鄰的項的和就等於下一個項次。

 現在我們已知任一正整數的這種費式數列基底表示法，我們以17為例來說明，17=1+3+13，表示17要取三項：1的項、3的項、13的項，而不取2的項、4的項、5的項及其他項。所以17=100101，如下圖：

17 =	1	0	0	1	0	1
13+3+1 =	13	8	5	3	2	1

Figure 2 - 17的費式數列基底表示法

The Problem

給你一個以十進位為基底的值，請你寫出該值以費式數列為基底的表示式。

Input

第一列有一個整數N表示測試資料的組數，1 <= N <= 500。接下來有N列，每一列有一正整數，其值小於100,000,000。

Output

請以下列的格式輸出答案。

Example Input

10
1
2
3
4
5
6
7
8
9
10

Example Output

1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)

---

原文出處

900 - Brick Wall Patterns

假如你想用磚塊砌一面牆，考慮長度為寬度兩倍的磚塊(定義磚塊的寬度為1，長度為2，本題不需要考慮磚塊的厚度)，而牆的高度很低，等於磚塊的長度(2)，你可以用不同的磚塊排列方式把牆砌起來，所有可能的排列方式取決於牆的長度，考慮下圖說明：

• 若牆的長度為1，則只有一種排列方式。
• 若牆的長度為2，則有兩種排列方式，兩塊都直的擺或兩塊都橫著擺。
• 長度為3的牆則有3種排列方式。

若牆的長度為4可以有幾種排列方式？若為5又有幾種排列方式？

Problem

你必須寫一個程式計算當牆的長度給定之後，決定共有多少種排列方式。

Intput

你的程式會從輸入中讀取一連串的正整數，每個正整數一列表示牆的長度，最大值為50，並以0表示輸入結束。

Output

對應輸入中每列牆的長度，請輸出共有幾種排列方式。

Sample Intput

1
2
3
0

Sample Output

1
2
3

原文出處