11384 - Help is needed for Dexter

有一個電腦遊戲，當按下一個按鈕後，電腦會隨機選擇一個數字N，接下來會在螢幕上顯示數字1~N共N個不同的數字，你可以從中選擇任意多個數字，並將所選擇的數字減去一個正整數(你可以自由選擇該正整數，並不限定是否出現在螢幕上)，你的目標是要使全部N個數字全變為零。

例如當N=3，螢幕會顯示三個數字：1, 2, 3，你選擇1與2分別減掉1，些時螢幕上會顯示：0, 1, 3，你再選擇1與3減掉1，此時變為0, 0, 2，你再選擇2減掉2，最後，共執行三次步驟後使得所有數字皆變為零。

給定正整數N，你必須計算使得所有N個整數皆變為零的最少步驟為何。

Input and Output:

輸入的每一列會有一個整數N(1 <= N <= 1,000,000,000)，請輸出對應的最少步驟次數。

SAMPLE INPUT	OUTPUT FOR SAMPLE INPUT
1 2 3	1 2 2

---

原文出處

11385 - Da Vinci Code

本題會給你一些費氏數列(Fibonacci series)的前幾項，及一個加密後的密文，請你利用本題提供的方法進行解密。直接以一個例子解釋。每組資料會有兩列，第一列為解密的鑰匙，是由費氏數列的某些項所組成的數個整數，第二列為欲解密的密文。例如：      13 2 89 377 8 3 233 34 144 21 1      OH, LAME SAINT! 解密後為：      THE MONA LISA 費氏數列的特性為可利用前兩項的和來得到第三項，得到數列 1, 2, 3, 5, 8, 13, 21... 解密的原則為先把解密的鑰匙中，每一項的值找出該值在費氏數列中是第幾項，例如13是費氏數列的第六項，2為第二項，89為第十項，以此類推。第一個數值13為費氏數列的第六項，就把第一個大寫字母O搬到位置六的地方，第二個數值2為費氏數列的第二項，就把第二個大寫字母H搬到位置二的地方，以此類推得到THE MONA LISA。請注意只有大寫字母才需要解碼，請忽略其他字元。 在費氏數列中未出現的項，請將其對應的位置上填上空白字元，例如上例中缺少費氏數列的第四、第九項(5, 55)，所以在對應的位置上是空白字元。但空白字元只限於出現在字串中。
Input
輸入資料的第一列為整數T，表示測試資料的組數，接下來每組測試資料有三列，第一列為整數N，表示第二列有N個取自於費氏數列的整數，每個整數將以空白字元隔開。第三列為欲解密的字串。
Output
請輸出每組測試資料解密後的字串。注意其僅包含大寫字元。
Constraints
輸入的費氏數列，其值必小於2^32。 輸入字串長度最多100個字元。
Sample Input	Output for Sample Input
2 11 13 2 89 377 8 3 233 34 144 21 1 OH, LAME SAINT! 15 34 21 13 144 1597 3 987 610 8 5 89 2 377 2584 1 O, DRACONIAN DEVIL!	THE MONA LISA LEONARDO DA VINCI
原文出處

11360 - Have Fun with Matrices

給定大小為 N x N 的矩陣，矩陣元素為整數，其值介於0~9之間，請你對矩陣作運算後輸出。本題所定義的矩陣運算如下：

row a b

將第 a 列與第 b 列作交換。

col a b

將第 a 行與第 b 行作交換。

inc

將所有矩陣元素值加1後，再除以10取餘數。例如9+1=10，除以10取餘數得到0。

dec

將所有矩陣元素值減1後，再除以10取餘數。例如0-1=-1，除以10取餘數得到9。

transpose

轉置，也就是將矩陣的橫行寫成縱列，縱列寫成橫行。

Example:

1 2 3                             1 4 7

4 5 6       -> 轉換過後 ->         2 5 8

7 8 9                             3 6 9

Input

輸 入一開始會給定整數T(T < 50)表示測試資料的組數，每組測試資料會給定正整數N(N < 10)表示矩陣的大小，矩陣元素即為接下來的N列中的N個數字，每個數字介於0~9之間[0, 9]。再接下來會有整數M(M < 50)，表示接下來會出現的指令總數。你可以假設row a b, col a b中1 <= a, b <= N且 a!=b。

Output

請依範例資料格式輸出每組測試資料的編號與轉換後的矩陣，請在每組輪出資料後輸出一列空行(包含最後一組資料)。

Sample Input	Output for Sample Input
2 4 1234 5678 1234 5678 1 transpose 3 000 111 000 2 row 1 2 inc	Case #1 1515 2626 3737 4848 Case #2 222 111 111

原文出處

11310 - Delivery Debacle

Wolfgang Puck有兩個特別的習慣：

• 他只切兩種形狀的蛋糕，單位面積為一的正方形，與單位面積為三的L形。
• 他只將蛋糕放入特定大小的盒子內，盒子的的長度不固定，但是寬度一定是2。

他想知道將蛋糕放入盒子內共有幾種擺放方式。

左圖為兩種形狀的蛋糕。右圖為將蛋糕擺放進2x6的盒子內的其中一種方式。

 

將蛋糕放入2x2盒子內的所有可能方式。

Input

輸入一開始會有一個整數 t 表示測試資料的組數，接下來有 t 個整數 n (1 <= n <= 40)表示盒子的長度。

Output

針對每組測試資料，輸出將蛋糕擺放進2 x n大小的盒子內的所有可能方式總數，輸出值一定會小於10^18。

Sample Input

2

1

2

Output for the Sample Input

1

5

---

原文出處

11321 - Sort! Sort!! and Sort!!!

本題請你對一個陣列作排序，給定陣列大小為N，及正整數M，請你依陣列元素取M的模數(value Mod(M)，即對M取餘數)大小，由小到大依序排序所有陣列元素，若取模數後其值大小相同，在此情況下分三種情況進行討論：

• 若兩個元素值分別為一個奇數與一個偶數，則將奇數排在偶數前面。
• 若兩個元素皆為奇數，則較大的奇數將排在較小的奇數前面。
• 若兩個元素皆為偶數，則較小的偶數將排在較大的偶數前面。

負數取模數的方式將以C語言取餘數的方式為準，其餘數不會大於0，例如 -100 MOD 3 = -1, -100 MOD 4 = 0。

Input

輸入有20組測試資料，每組資料一開始有兩個整數N(0 < N <= 10000)與M(0 < M <= 10000)，接下來會有N列整數，每個整數皆能以32位元的有號整數來表示。當N = 0 且 M = 0 時表示測試資料結束。

Output

請毎組測試資料輸出N+1列，第一列請輸出N與M的值，接下來的N列請分別輸出排序後的陣列元素。最後也請把兩個0印出在最後一列。

Sample Input                      Output for Sample Input

15 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0

15 3 15 9 3 6 12 13 7 1 4 10 11 5 2 8 14 0 0

---

原文出處

11371 - Number Theory for Newbies

對於任意正整數，將該數的每個位數重新排列組合後，所得到的新數值與原數值的差必為9的倍數，例如給定數值123，重新排列後產生321，兩者之差為321 - 123 = 198 = 9 x 22。


你無需提出數學證明，只需要利用此特性來處理本問題。

Input and Output

輸入資料的每列都有一個正整數 n ( <= 2000000000)。請你將 n 的每個位數重新排列組合後找出兩個整數 a 與 b 使得 a-b 最大化，且 a 與 b 皆不能將可能出現的零排在最前面。輸出的格式請參考範例資料。

Sample Input

123
2468
1230

Sample Output

321 - 123 = 198 = 9 * 22
8642 - 2468 = 6174 = 9 * 686
3210 - 1023 = 2187 = 9 * 243

---

原文出處

11340 - Newspaper

報紙文章的稿費是以文章中所出現的字元來計算，不同的字元所值的稿費並不相同，本題請你計算文章的稿費。

INPUT:

第 一列有一個整數N(0 < N <= 5)表示測試資料的組數。每組測試資料一開始會給定一整數K(0 < k <= 100)表示接下來會有K列，每一列表示一個字元的價值(以1分 = 0.01元為單位)，如果字元未出現在這K列中，表示這些字元的價值為0。接下來會有一個整數M(0 < M <= 150000)，表示接下來出現的文章的列數，每列不超過10000個字元。輸入的檔案大小約7MB。

OUTPUT:

請輸出每組測試資料文章的價值，輸出至小數點下兩位。

SAMPLE INPUT:

1
7
a 3
W 10
A 100
, 10
k 7
. 3
I 13
7
ACM International Collegiate Programming Contest (abbreviated
as ACM-ICPC or just ICPC) is an annual multi-tiered competition
among the universities of the world. The ICPC challenges students
to set ever higher standards of excellence for themselves
through competition that rewards team work, problem analysis,
and rapid software development.
From Wikipedia.

SAMPLE OUTPUT:

3.74$

---

注意：本題中定義的"字元"是以unsigned char來表示，也就是說會有256個字元，如果宣告成char會有問題。
原文出處

11369 - Shopaholic

琳賽是購物狂，每當有買二送一的活動時，她就像得了失心瘋一樣想把整間店都買下來。你已經放棄對於她這種疾病的治療，你唯一能做的是幫她節省荷包。

通常這種買二送一的活動會是買三件送你其中一件，且送的那件一定都是三件中最便宜的。例如買七件物品到櫃台結帳時，其價格為400, 350, 300, 250, 200, 150, 100，總共要付前5件的錢，並享折扣250(150+100)。但是只要分三次到櫃台結帳，第一次買400, 300, 250，享250元折扣，第二次買350, 200, 100，享100元折扣，第三次買150元物品，沒有折扣，三次共可折350元(250+100)。



你要幫琳賽算算最多可以享受到多少折扣。

Input 

輸入的第一列會有一個整數 t (1 <= t <= 20)表示測試資料的組數，每組資料兩列，第一列有一個整數表示琳賽想買的數量 n，1 <= n <= 20000，接下來的 n 個整數為所有物品的價格pi，1 <= pi <= 20000。

Output 

請你算算透過這種策略可以幫她省掉最多多少折扣。

Sample Input 

1 
6 
400 100 200 350 300 250

Sample Output 

400

---

原文出處

11364 - Parking

麥可去逛街的時候會把車停在街上的某處，然後到處去採購，請你幫麥可決定他應該把車停在何處才能使得逛完後回到車上的移動距離最小。

他逛的是一條筆直的大街，街上商店的位置以整數來表示，他把車停在某一位置上後會開始到他想去的店逛，等所有店都逛完了再提著他所採購的所有物品回到他的車上去。

Input 

第一列的整數 t 表示測試資料的組數(1 <= t <= 100)。接下來的 t 組資料各有兩列，第一列為一個表示商店數量的整數 n (1 <= n <= 20)，下一列有 n 個數表示商站的位置，所有位置 xi，0 <= xi <= 99。

Output 

請幫麥可選擇最佳的停車位置後，輸出麥可移動的最小距離。

Sample Input 

2 
4 
24 13 89 37 
6 
7 30 41 14 39 42

Sample Output 

152
70

---

原文出處

11388 - GCD LCM

給你兩個未知數的最大公因數(GCD)與最小公倍數(LCM)，請你求出這兩個未知數為何。
Input
輸入的第一列有一個整數T表示測試資料的組數，接下來的T列每列有兩個整數表示G與L。
Output
每組測試資料對應一列輸出，請輸出兩個正整數 a 與 b (a <= b)，且a, b的最大公因數為G，最小公倍數為L，由於可能會有許多可能的解，所以請輸出 a 最小的那組，如果無解則請輸出-1。
Constraints
T <= 100 G, L < 2^31
Sample Input	Output for Sample Input
2 1 2 3 4	1 2 -1

原文出處

11332 - Summing Digits

對於所有正整數 n，我們定義一函數 f(n) 為 n 的每一個十進位數字的總合，若再把f(n)代入函數中可得最到 n, f(n), f(f(n)), f(f(f(n)))...最後得到僅有一位數字的值，並定義該值為 g(n)

例如，當 n = 1234567892. 則:

f(n) = 1+2+3+4+5+6+7+8+9+2 = 47
f(f(n)) = 4+7 = 11
f(f(f(n))) = 1+1 = 2

所以, g(1234567892) = 2.

輸入的每一行會有一個正整數 n，其值最大到2,000,000,000，你必須輸出g(n)。輸入是以0值做為結束，該值不需要輸出。

Sample input

2
11
47
1234567892
0

Output for sample input

2
2
2
2

---

原文出處