「指揮官！指揮官！趕快醒醒！」
「mmmm … 現在幾點了？」
「清晨四點零七分，我們剛收到國防部的緊急電報，請指揮官裁示。」

你不甘願的拿過電報，揉揉眼睛，看到上面寫著：

親愛的指揮官：

代誌大條了！昨天晚上俄羅斯瘋狂的 Boris 將軍伏特加喝多了，今天清晨時，原本要把鬧鐘按掉的，他 …
我直接說好了，現在正有好幾枚洲際飛彈朝你那邊飛去。更不幸的是，我們只知道飛彈的高度以及到達
的順序。趕快去處理吧！祝你好運！

P.S. Hilly 和 Bill 要我和你說嗨！

死啦！死啦！由於國防預算被刪減的緣故，你的愛國者反飛彈系統有嚴重的缺陷，發射的角度只能升不能降。也就是說，當你摧毀一枚來襲的飛彈之後，下一次你只能摧毀比上一枚飛得高的飛彈。例如：如果飛彈朝你飛來的高度分別是 1, 6, 2, 3, 5 (按照到達的順序)，若你攔截了前 2 枚，那後面那 3 枚將無法再攔截。因為 2, 3, 5 都比 6 小。你的任務就是要攔截最多的飛彈數。

俄羅斯戰術非常奇怪，他們的將軍都是對數學準確非常執著的人。所以他們的飛彈總是以一種特別的順序來發射，使得上面所描述的問題只會有一組解答。

Input

輸入的第 1 列有一個整數 N，代表以下有幾組測試資料。然後空一列。接下來的各列每列有一個整數，代表來襲飛彈的高度 (按照飛彈到達的順序)。測試資料間空一列，請參考 Sample Input。

Output

對每一組測試資料，請先輸出最多可以攔截幾枚飛彈。接下來的各列為所攔截到的飛彈的高度 (按照他們到達的順序)。測試資料間空一列，請參考 Sample Output。

Sample Input

2

1
6
2
3
5

3
7

Sample Output

Max hits: 4
1
2
3
5

Max hits: 2
3
7

假設我們有2塊背對背合在一起的玻璃。當一道光線射進此玻璃時，可能穿透或反射。若以 $n$ 代表一道光線射進此玻璃時反射的次數，$a_n$ 即是代即是表一道光線射進玻璃反射 $n$ 次的方法數，這個問題要請你求出 $a_n$。下圖展現出當 $n=0,1,2$ 的情形。

Input

每一列有 1 個整數 $n$ ($0\leq{n}\leq{1000}$)。

Output

每列測試資料輸出 $a_n$。

Sample Input

0
1
2

Sample Output

1
2
3

德國的農夫根據他們農場的條件被發給獎金。想像以下簡單的規則：你知道農場的大小也知道有多少動物住在裡面。在這裡我們並不去分別不同的動物有什麼不同之處 (雖然這跟現實有些不合)。除此之外，你還知道農夫使用環保設備及習慣的等級 (稱之環保等級)，這等級以大於 $0$ 的整數來表示。

農夫得到的獎金是根據以下的計算：首先算出每隻動物平均居住的空間，然後乘以該農夫的環保等級，這樣你就得到每隻動物可以領多少獎金。最後再把這個值乘以所有動物的數目，就可以算出該農夫可得到獎金的數目了。

Input

輸入的第一列有一個整數 $n$ ($n < 20$)，代表以下有幾組測試資料。每組測試資料的第一列有 1 個整數 $f$ ($0 < f < 20$) 代表在這組測試資料中有多少個農夫。接下來有 $f$ 列，每列有 3 個正整數，分別代表各農夫農場的面積，農場裡動物的數目，該農夫的環保等級。所有輸入的整數都不會比 $100000$ 大，也不會比 $0$ 小。

Output

對每組測試資料，請輸出一個整數，代表要發給農夫的獎金的總數。

Sample Input

3
5
1 1 1
2 2 2
3 3 3
2 3 4
8 9 2
3
9 1 8
6 12 1
8 1 1
3
10 30 40
9 8 5
100 1000 70

Sample Output

38
86
7445

排序在電腦科學中是一個重要的部分。已經有許多優秀的排序演算法被提出。在這個問題中我們將討論一種排序的方式，就是你只能交換相鄰的 2 個元素。如果你想一下的話，你會瞭解以這樣的方式總是可以將一些數字排序。(註：我們通常稱這種排序方式為 Bubble Sort)

給你一串整數，請你用上述的方法來將之由小到大排序。要請你求出最少要交換幾次。例如給你 “1 2 3”，那需要交換的次數為 0，因為已經排好了。如果給你 “2 3 1”，則最少需要交換 2 次才可排好序。(“2 3 1” -> “2 1 3” -> “1 2 3”)

Input

每組測試資料的第一列有 1 個整數 N (N <= 1000)。代表以下會有 N 個待排序的整數。接下來的 N 個整數，就是那些待排序的數。請參考 Sample Iutput

Output

如題目所述，請參考 Sample Output

Sample Input

3
1 2 3
3
2 3 1

Sample Output

Minimum exchange operations : 0
Minimum exchange operations : 2

給你 2 個字串 $s$、$t$，請你寫一個程式判斷是否 $s$ 是 $t$ 的子字串。也就是說當你移走 $t$ 字串中的某些字元後，剩下的字串就是 $s$。

Input

每筆測試資料一列。每列有 2 個字串，$s$ 及 $t$，以空白分隔。

Output

對每一列輸入，請輸出是否 $s$ 是 $t$ 的子字串。

Sample Input

abc abc
sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

Sample Output

Yes
Yes
No
Yes
No

我們有很多隻烏龜，每隻烏龜有不同的重量及力量 (單位：公克)。烏龜的力量指的是烏龜負重的能力 (包含他自己的體重)。例如：有隻烏龜重 300g，力量為 1000g，那麼這隻烏龜背上所能負載的重量最多為 700g。現在，我們想要將烏龜疊在一起，越多隻越好，但是每隻烏龜都必須能負載位於其上的烏龜們的重量。也就是說沒有烏龜會被壓死。

Input

每一列有 2 個整數分別代表各烏龜的重量及力量，最多有 5607 隻烏龜。

Output

輸出只有一個整數，就是最多共可以有幾隻烏龜疊在一起？

Sample Input

300 1000
1000 1200
200 600
100 101

Sample Output

3

Peter 有 $n$ 支紙煙，他一支一支的抽並且把煙屁股留起來。當他有 $k$ 支煙屁股 ($k > 1$) 時他可以把它們捲成一支新的紙煙。

請問 Peter 共可以抽幾支紙煙？

Input

每筆測試資料一列。每列有 2 個整數 $n,k$。

Output

對每一列輸入，請輸出 Peter 共可以抽幾支紙煙。

Sample Input

4 3
10 3
100 5

Sample Output

5
14
124

以下這個由 Lothar Collatz 定義的演算法可以產生一連串數列：

Step 1:
任選一個正整數 A 作為這個數列的第一項。
Step 2:
如果 A = 1 則停止。
Step 3:
如果 A 為偶數，則 A = A/2 然後重新回到 Step 2。
Step 4:
如果 A 為奇數，則 A = 3 * A + 1 然後重新回到 Step 2。

這個演算法已經被證明當首項小於等於 $10^9$ 時這個數列最終都會在 Step 2 停止，但是有些 A 值在這個數列中會超出許多電腦的整數上限。在這個問題中我們想要計算這個數列的長度，而數列的終止有兩種情況：

1. 最終會在 Step 2 停止或是
2. 某一項會在 Step 4 超出一個特定的上限。

Input

輸入包含許多組待測資料，每一列代表一組待測資料，每組待測資料包含兩個正整數，第一個數為首項 A，第二個數為這個數列的上限 L，無論 A 或 L 都不會大於 2,147,483,647 (32 位元有號整數的最大值)，且首項 A 總是小於上限 L。當輸入為兩個負數時代表輸入結束。

Output

對每組待測資料必須輸出它為第幾組 (從 1 開始)，一個冒號，首項 A 的值，上限 L 的值，以及此一數列的項數。(請參考 sample output)

Sample Input

3 100
34 100
75 250
27 2147483647
101 304
101 303
-1 -1

Sample Output

Case 1: A = 3, limit = 100, number of terms = 8
Case 2: A = 34, limit = 100, number of terms = 14
Case 3: A = 75, limit = 250, number of terms = 3
Case 4: A = 27, limit = 2147483647, number of terms = 112
Case 5: A = 101, limit = 304, number of terms = 26
Case 6: A = 101, limit = 303, number of terms = 1

在本題中，題目會先給你一個包含小括號 () 及中括號 [] 的字串。當字串符合下列條件時我們稱他為正確的運算式：

1. 該字串為一個空字串
2. 如果 A 和 B 都為正確的運算式，則 AB 也為正確的運算式，
3. 如果 A 為正確的運算式，則 (A) 及 [A] 都為正確的運算式。

現在，請你寫一支程式可以讀入這類字串並檢查它們是否為正確的運算式。字串的最大長度為 128 個字元。

Input

輸入的第一列為正整數 n，代表接下來有 n 列待測資料。

Output

檢查每列待測資料，如果正確輸出 Yes，否則輸出 No。

Sample Input

3
([])
(([()])))
([()[]()])()

Sample Output

Yes
No
Yes

給你一個金額 ($n$ cents)，請你回答共有多少種硬幣組合的方式。例如：$n=11$，那麼你可以有以下 4 種硬幣的組合：

1. 1 個 10 cent 的硬幣加上 1 個 1 cent 的硬幣
2. 2 個 5 cent 的硬幣加上 1 個 1 cent 的硬幣
3. 1 個 5 cent 的硬幣加上 6 個 1 cent 的硬幣
4. 11 個 1 cent 的硬幣

p.s 美國的零錢共有以下 5 種硬幣以及其面值：

• penny, 1 cent
• nickel, 5 cents
• dime, 10 cents
• quarter, 25 cents
• half-dollar, 50 cents

請注意：$n=0$ 我們算他是有一種方式。

Input

每組測試資料 1 列，有 1 個整數 $n$ ($0\leq{n}\leq{7489}$)，代表零錢的總金額 (單位：cent)。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。

Sample Input

0
17 
11
4
1000
2000
7489

Sample Output

1
6
4
1
801451
11712101
2146113925