11876 - N + NOD (N)

考慮整數序列：

N₀ = 1
N_i = N_i-1 + NOD(N_i-1)- for i > 0

其中，NOD(x)表示能整除 x 的除數(因數)個數。所以序列的前幾項為1 2 4 7 9 12 18...。給定兩個整數A與B，請輸出序列中數值大小介於[A, B]之間的整數個數。

Input

輸入的第一列有一個整數T (T < 100000)表示測試資料的組數，每組資料有兩個整數A, B(1 <= A <= B <= 1000000)。

Output

請參考範例資料格式，輸出編號與答案。

Sample Input	Sample Output
3 1 18 1 100 3000 4000	Case 1: 7 Case 2: 20 Case 3: 87

---

原文出處

11889 - Benefit

兩個整數A, B的最小公倍數C，可用下列等式表示：LCM(A, B) = C。本題給定A, C，請你找出B。

Input

輸入的第一列為整數T(T <= 100000)表示測試資料的組數，每組資料一列包含兩個整數A, C(1 <= A, C <= 10,000,000)。

Output

每組測試資料一列，請輸出最小的整數B使得LCM(A, B) = C。若B不存在則請輸出"NO SOLUTION"。

Sample Input 

3
2 6
32 1760
7 16

Sample Output 

3
55
NO SOLUTION

---

原文出處

11879 - Multiple of 17

定理：若且唯若，移除一個大於等於10的整數 n 的最後一個位數 d，其值再減去5d之後，若為17的倍數，則 n 亦為17的倍數。

例如：34為17的倍數，因為3-20=-17為17的倍數；201非17的倍數，因為20-5=15非17的倍數。

給定一正整數 n，請你判斷 n 是否為17的倍數。

Input

最多有十組測試資料，每組一列為一個整數 n (1 <= n <= 10^100)，當 n = 0表示資料結束。

Output

若為17的倍數請輸出1，否則請輸出0。

Sample Input 

34
201
2098765413
1717171717171717171717171717171717171717171717171718
0

Sample Output 

1
0
1
0

---

原文出處

11878 - Homework Checker

本題要請你驗算小學生的加減法作業的答案，其等式為 a + b = c 或 a - b = c 兩者中的一種，其中a, b為給定的正整數，其值不大於100，而你必須驗算 c 的答案是否正確，c 的值為正整數且不超過200，若 c 為問號(?)表示沒有答案。

Input

輸入最多100列，每列有一個等式，請參考範列資料，每一列不會出現空白字元，且數值前面不會有多餘的零。

Output

輸出只有一列，為一個整數，表示答案正確的題數。

Sample Input 

1+2=3
3-1=5
6+7=?
99-0=99

Sample Output 

2

---

原文出處

11850 - Alaska

阿拉斯加高速公路由Dawson Creek到Delta Junction全長共1422英哩，Brenda女士想成為首位開電動車行駛整條阿拉斯加高速公路的人，她的電動車充一次電可以跑200英哩，除了她的起點：Dawson Creek有專門的充電站之外，沿著公路一路上能充電的地方並不多，本題要請你判斷她是否能開著她的電動車成功往返阿拉斯加高速公路。

Input Specification

輸 入有多組測試資料，每組資料的第一列有一個正整數 n，表示充電站的總數，接下來的 n 列表示充電站所在公路的位置，且一定包含起點Dawson Creek的充電站，數值大小介於0~1422表示距離起點的距離，不會有兩個充電站的位置一樣。當 n = 0表示測試資料結束。

Sample Input

2
0
900
8
1400
1200
1000
800
600
400
200
0
0

Output Specification

假如Brenda女士能成功完成她的旅程請輸出"POSSIBLE"，否則請輸出"IMPOSSIBLE"。每組輸出一列。

Output for Sample Input

IMPOSSIBLE
POSSIBLE

---

原文出處

11849 - CD

傑克與吉兒兩人想要賣出他們的CD光碟，他們決定賣出他們兩人皆擁有的CD光碟其中的一張，本題要請問他們兩人共會賣出多少光碟？

Input Specification

輸入有多組測試資料，每組的第一列有兩個非負整數N與M，其最大值為1,000,000，表示 他們兩人個自擁有的CD光碟總數，接下來會有N列，每列為一個整數，這N個整數為一組遞增序列，表示傑克所擁有的CD光碟名稱(編號)。再接下來會有M 列，每列為一個整數，這M個整數亦為遞增序列，表示吉兒擁有的CD光碟。表示編號的整數值不會大於1,000,000,000。當N, M皆為零表示測試資料結束。

Sample Input

3 3
1
2
3
1
2
4
0 0

Output Specification

每組測試資料請輸出一列，表示兩人共賣出CD光碟總數的整數。

Output for Sample Input

2

---

譯者本題一直處於Sent to judge的狀態，原因不明
原文出處

11839 - Optical Reader

本題要模擬單選題的電腦閱卷，單選題考試卷的題目會有五個選項(A, B, C, D, E)，考生必需從中選擇一個答案畫在答案卡上。

在答案卡上每題有五格，電腦閱卷時會掃描五格的灰階值，0表示全黑，255表示全白。如果考生在某一格上用鉛筆正確地塗滿，則該格的灰階值為 0 (全黑)，若該格留白則灰階值為 0 (全白)。理想上，若某一題五格的灰階值分別為(255, 0, 255, 255, 255)則表示考生選擇了答案B。但是現實上每一格的灰皆值總是有高有低，所以我們把所有灰階值分類為兩種，若小於等於127則視為黑色，若大於127則視為白色。

通常答案卡上的答案不見得都被正確地劃記，有可能同一題被填入兩個以上的答案，也有可能一個答案也沒有，這種情況被視為沒有答案。

請你寫一個程式判斷每一題所選擇的答案為何。

Input

輸入有許多組測試資料，每一組的第一列有一個整數N(1 <= N <= 255)，表示題目的個數。接下來有N列，每列有五個整數分別表示A, B, C, D, E的灰階值(0 <= A, B, C, D, E <= 255)。
當N=0表示測試資料結束。

Output

每組測試資料請輸出N列，分別表示每題的答案，如果答案被正確填寫的話，請輸出答案為何(請輸出A, B, C, D, E其中一個)，否則請輸出 '*' (星號)。

Sample Input 

3
0 255 255 255 255
255 255 255 255 0
255 255 127 255 255
4
200 200 200 0 200
200 1 200 200 1
1 2 3 4 5
255 5 200 130 205
0

Sample Output 

A
E
C
D
*
*
B

---

原文出處

11834 - Elevator

本題請你判斷兩個圓形是否可以放進一個矩形內，下圖(a)是可行的例子，下圖(b)是不可行的例子。

Input

輸入包含許多組測試資料，每組測試資料一列分別包含四個整數L, C, R1, R2，分別表示矩形的寬度(1 <= L <= 100)，矩形的長度(1 <= C <= 100)，及兩個圓形的半徑(1 <= R1, R2 <= 100)。以四個0表示測試資料結束。

Output

若兩個圓形可放進矩形內請輸出'S'，否則請輸出'N'，每組測試資料輸出一列。

Sample Input 

11 9 2 3
7 8 3 2
10 15 3 7
8 9 3 2
0 0 0 0

Sample Output 

S
N
N
S

---

原文出處

11831 - Sticker Collector Robot

機器人競技賽在RoboLand是一種很受歡迎的運動，這項運動在大小為N*M的四方型場地舉行，場地中有些位置是空的，有些位置上有貼紙，也有些用來撐起屋項的柱子。這項運動的一開始機器人會站在場地中某個位置，並以一連串指令決定行進的路徑，指令共有三種：'D'指令表示右轉90度，'E'指令表示 左轉90度，'F'指令表示進行一格。當機器人站在有貼紙的位置上時，它會把貼紙收集起來，而地上的貼紙一個位置最多只有一張，被取走後該位置就不會有貼 紙了。如果機器人向前進的位置上有柱子或是將要離開場地的話，它不會前進也不會轉動方向。
給定場地的相關資訊，包含場地大小與貼紙、柱子的位置，及一連串的指令，請你寫一個程式計算機器人一路上共收集了幾張貼紙。

Input

輸入有許多測試資料，每組資料的第一列有三個整數N, M, S(1 <= N, M <= 100, 1 <= S <= 50000)，分別表示場地的列數、行數，與機器指令的個數。接下來的N列每列有M個字元表示整個場地的地圖，最上方一列是北方，最左邊一行是西方。

地圖上每個字元表示如下：

• '.' -- 空的格子。
• '*' -- 有貼紙的格子。
• '#' -- 有柱子的格子。
• 'N', 'S', 'L', 'O' -- 分別表示機器人一開始所在位置及其面對的方向(分別表示北方、南方、東方、西方)。

每組資料的最後一列為一字串，表示給機器人的指令，所有字元只會有'D', 'E', 'F'三種字元。

Output 

請在每一列輸出每組測試資料的答案，也就是機器人一路上所收集的貼紙數目。

Sample Input 

3 3 2
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0

Sample Output 

0
1
3

---

原文出處

11827 - Maximum GCD

                       

給定N個整數，請你從這些整數中的任意兩個整數的選擇中，找出最大的GCD(最大公因數)。

Input

輸入的第一列為一個整數N(1 < N < 100)表示測試資料的組數。接下來的N列每列有M(1 < M < 100)個正整數，請從中找出最大的GCD。

Output

請從每組測試資料中的任意兩個整數的選擇中，找出最大的GCD(最大公因數)。

Sample Input	Output for Sample Input
3 10 20 30 40 7  5 12 125 15 25	20 1 25

---

原文出處

11804 - Argentina

阿根庭足球隊教練馬拉度那正在嘗試一種新的陣型，一般都是以4-4-2或4-3-3來安排前鋒、中堅、後衛的陣容，不過今年有點例外，用5-5陣型，只分為前鋒與後衛。

你要寫一個程式幫助教練分派每位球員的攻擊/守備位置。

教練會給你十位球員的資料，上面除每位球員的姓名外，還會有每位球員的攻擊、防禦能力值，你的任務是要找出哪五位應該擔任攻擊位置，哪五位又應該擔任守備位置。

選取的原則如下：

• 先選擇讓5位攻擊型球員的攻擊能力值總合最大化。
• 若不只一種組合，則從中選擇讓5位守備型球員的守備能力值總合最大化。
• 若又不只一種組合，請選擇球員姓名字典順序最小者。
  

Input

輸入的第一列為一整數T(T < 50)表示測試資料的組數。每組測試資料有10列，每一列為球員的姓名與攻擊、守備能力值。球員姓名最長20個字元，只會出現小寫字母。攻擊、守備能力值是介於[0, 99]的整數。

Output

請每組測試資料輸出三列，第一列輸出測試資料的序號，第二列輸出5位攻擊型球員的姓名，第三列輸出守備型球員的姓名，格式請參考下列範例。每列5位球員的姓名請依字典順序列出。

Sample Input	Sample Output
1 sameezahur 20 21 sohelh 18 9 jaan 17 86 sidky 16 36 shamim 16 18 shadowcoder 12 9 muntasir 13 4 brokenarrow 16 16 emotionalblind 16 12 tanaeem 20 97	Case 1: (emotionalblind, jaan, sameezahur, sohelh, tanaeem) (brokenarrow, muntasir, shadowcoder, shamim, sidky)

---

原文出處

11875 - Brick Game

在某個小鎮上流行著一種遊戲，遊戲中每一隊的隊員數目一定是奇數，且人數最少一位、最多不超過10位，而隊員的年紀必需介於11~20歲，且不會有任兩位隊員的年紀相同。每一隊都有一個隊長，由於年紀差異的關係，隊員與隊員之間的溝通多少會有代溝，年紀差異愈大代溝就愈大，為此，他們選擇隊長的原則是：年紀比隊長大的人數會等於年紀比隊長小的人數。

本題會給你所有隊員的年紀，請你找出隊長的年紀為何。

Input

輸入一開始會有一個表示測試資料組數的整數T(T <= 100)。

接下來會有T列，每列代表一組測試資料，每組測試資料的第一個整數N(1 < N < 11)表示隊員的總數。接下來會有N個以空白字元隔開的整數代表每位隊員的年紀，年紀介於11~20歲之間，此N個數必定是以嚴格遞增或嚴格遞減的順序排列。

Output

請輸出資料格式"Case x: a"，x表示測試資料的編號，a表示隊長的年紀。

Sample Input	Sample Output
2 5 19 17 16 14 12 5 12 14 16 17 18	Case 1: 16 Case 2: 16

---

原文出處

11824 - A Minimum Land Price

 ACM -ICPC主辦單位想在泰國普吉島買地蓋大樓，不過普吉島的地價連年不斷攀升，每年以指數遞增。假如第 i 塊地一開始的地價為Li，則 t 年後會漲到 2x(Li)^t，每塊地的地價不會都一樣。ACM-ICPC每年只能買一塊地，你必須幫助主辦單位以最便宜的價格買到所有土地，預算上限為 5,000,000百萬泰銖。

例如，我們想買3塊地，一開始的價格分別是7, 2, 10百萬泰銖，則買價可能會是：

            (2 x 7) + (2 x 2^2) + (2 x 10^3) = 2022 百萬泰銖

Input

輸入的第一列有一個表示測試資料組數的整數T (1 <= T <= 10)，接下來會有多個整數Li表示土地的價格(單位:百萬泰銖)，每組測試資料最多有40筆土地價格，並以 0 表示每組測試資料的結束。

Output

請輸出購買全部土地的最低價格，若總價超過預算5,000,000百萬泰銖，請輸出"Too expensive"。

Sample Input	Output for Sample Input
3 7 2 10 0 20 29 31 0 42 41 40 37 20 0	134 17744 Too expensive

---

原文出處

11830 - Contract Revision

好幾年以來，所有ACM的合約都是由老式打字機打出來的。

最近，有一位ACM的會計師發現打字機有一個按鍵，而且是數值按鍵打不出字，有打就好像沒打一樣，他知道這樣會造成合約的數值表示出現問題。基於會 計上的需要，他想要知道原始合約的數值資料(他有手寫的原稿)經由該台打字機所打出來的值是多少。例如如果壞掉的數值按鍵為5，而原始合約內容寫的是 1500，則最後會打出100的數值，因為5印不出來。會計師想知道的是印錯的數值"大小"是多少，而非印出什麼值，例如5000，壞的打字機印出來的雖然是000，但是你要告訴會計師的數值是0，而非000。

Input

輸入會有許多測試資料，每一列有兩個整數D與N(1 <= D <= 9, 1<= N <= 10^100)，分別表示壞掉的數值按鍵與合約上的原始數值(由於高通膨的關係，該數值可能會是天文數字)。以空白字元隔開的兩個分別為0的整數，表示測試資料結束。

Output

請輸出用壞掉的打字機所印出來的數值大小是多少？

Sample Input 

5 5000000
3 123456
9 23454324543423
9 99999999991999999
7 777
0 0

Sample Output 

0
12456
23454324543423
1
0

---

原文出處

11877 - The Coco-Cola Store

三瓶可樂飲料的空瓶可以換一瓶全新的可樂，本題會給你空瓶的數量 n，請問最多可以換幾瓶可樂來喝？
你可以跟飲料店先借一個空瓶，例如當你有兩個空瓶，可以先借一個，有了三個空瓶可以換一瓶可樂，再把剩下的空瓶還回去。

Input

最多有十組測試資料，每個測試資料有一個整數 n (1 <= n <= 100)表示空瓶數目。當 n = 0表示測試資料結束。

Output

針對每組測試資料，請輸出你可以喝幾罐飲料。

Sample Input 

3
10
81
0

Sample Output 

1
5
40

---

原文出處

11854 - Egypt

給定三角形的三邊，請判斷該三角形是否為直角三角形。

The Input

每組輸入資料有三個正整數表示三角形的邊長，邊長皆小於30000。最後輸入以0 0 0 表示資料結束。

The Output

若為直角三角形請輸出"right"，否則請輸出"wrong"。

Sample Input

6 8 10
25 52 60
5 12 13
0 0 0

Output for Sample Input

right
wrong
right

原文出處

11805 - Bafana Bafana

美式足球教練想要他的隊員進行傳球練習，他要求所有N位隊員圍成一個圓圈圈，每人依位置依序付予一個編號1~N，1號球員把球傳給他右邊的隊員，也就是2號球員，2號傳給3號，以此類推。第N號再傳回給1號。

球一開始會在K號球員手上，練習會在第P次傳球後結束，本題請你找出球最後傳給了第幾號球員。

Input

輸入一開始給定一個整數T(T <= 1000)表示測試資料的組數，每組測試資料有三個整數N(2 <= N <= 23)，K(1 <= K <= N)，P(1 <= P <= 200)。

Output

請依下列輸出資料的格式，輸出球最後傳到誰手上。

Sample Input	Sample Output
3 5 2 5 6 3 5 4 1 3	Case 1: 2 Case 2: 2 Case 3: 4

---

原文出處

11810 - Gentle ping, to the old King

戰事將起，亞拉岡將如何應付

你們一定聽過托爾金的著名小說"魔戒"，就如你所知道的一樣，魔戒最終被佛羅多(Frodo Baggins)投入末日火山(mountain of doom)而被摧毀，因此邪惡的索倫(Sauron)得不到魔戒終於潰不成軍。擊退索倫中土終於恢復了和平，亞拉岡(Aragorn)登基成為國王，從此過著幸福快樂的日子。

然而這並不是故事真正的結束，擊敗索倫並非戰勝了邪惡取得最終的勝利，因為索倫的主子，邪惡的黑暗君主魔茍斯(Morgoth)，將從黑暗深淵中復活。

索倫死後多年，亞拉岡已經年邁，而他的兒子艾達瑞安(Eldarion)成為新的國王。和平的日子持續不了多久，有一天他們發現黑暗君主魔茍斯已經蘇醒，並計畫統治世界。整個中土世界即將狼煙再起。

艾達瑞安與老臣們商討許多阻止魔茍斯的計劃，他們有中土世界的地圖，所以他們知道中土世界內有許多領地，各領地之間有多條道路相互連接，他們知道每條聯絡道路的旅程有多久，從一領地到另一領地之間有一到多種路途程的選擇，每一領地都可藉由聯絡道路通往其他所有的領地。

這就是為什麼他們會如此害怕魔茍斯大軍的原因，因為一旦魔軍佔領了任一領地之後就可以肆無忌憚地侵略所有其他的領地，為了阻擋魔軍的去路，他們派來佇守各個道路的軍隊數量將十分可觀。

艾達瑞安與他的父親都是極重視榮譽的男人(man of honor)，所以他並不希望任一領地疏於防備，但是他的軍隊數量比魔茍斯的軍隊還少，這使他居於劣勢。如果他都把軍隊派佇到各個聯絡道路的話，他也許會有勝算，但將會有不少領地被攻佔。如果他們選擇派軍隊佇守各個領地的話，萬一有任何領地被攻陷，那其他領地就更危險了，因為魔軍可以利用沒有守備的道路來調度軍隊，更有甚者，箝制各領地之間的溝通並一一擊破。又如果艾達瑞安同時派軍隊防守各道路與各領地的話，會因為各據點兵力太少而無力抵抗魔苟斯的大軍。

經過漫長的討論，始終找不到兩全之計，所以艾達瑞安向他的父親亞拉岡尋求協助，亞拉岡花了一天的時間思考，隔天告訴艾達瑞安他的計劃，計劃是在讓軍隊調度不受影響的情況之下(各領地之間皆可出兵到其他任一領地)，維持最少的聯絡道路，其他多餘的道路會被摧毀，因為他們有很多投石機可以不費吹灰之力就把道路截斷。

然後，他們還需要選出最先可能被攻擊的領地，這些領地會由作戰經驗豐富的亞拉岡來選出，並稱這些領地為"主要領地(prime territories)"。所有軍隊只會被派佇到這些主要領地，當任一領地遭受攻擊的時候(不論是否是主要領地)，該領地上的傳訊者會到各個有兵力佇守的主要領地尋求協助，傳訊者會隨機地並且一一地選擇各主要領地進行通報，直到所有主要領地都出兵相助，傳訊者總是會選擇尚未被通報的主要領地尋求協助。因此，到達一個領地的"途程時間(the estimated time)"被定義為所有主要領地到達該領地所需時間之總合，而"總途程時間(total estimated time)"定義為所有領地的"途程時間"之總合。你可以忽略傳訊的時間。

現在，他們決定採用亞拉岡的主意，所以他們要留住使總途程時間最小的道路，而你是其中一位參謀，你對地圖瞭若指掌，現在你必須找出最小的總途程時間。記住，中土世界的存亡就掌握在你的手中。

Input

輸入資料的第一列為T(<=100)，表示有幾組測試資料。每組測試資料以一列空行開頭，接著下一列有三個整數 n (2 <= n <= 16), m 及 k (1 <= k <= n)，n是領地個數，m是道路個數，k是主要領地個數，領地的編號為從0到(n-1)。下一列共有k個以空白隔開的整數，每個整數用來表示主要領地的編號。再接下來的m列每列有三個整數u, v (0 <= u, v < n , u != v) 及 w (1 <= w <= 1000)

，表示有一條聯絡領地u到領地v的雙向道路，並且該道路的途程時間為w分鐘。你可以假定所有的道路都是有效的，不會出現重複的道路，且任兩個領地之間的道路最多只會有一條。

Output

針對每組測試資料，印出測試資料編號與最小總途程時間(the minimum Total estimated time)。

Sample Input	Sample Output
2 3 2 1 0 0 1 2 1 2 5 3 3 2 0 2 0 1 2 1 2 5 0 2 50	Case 1: 9 Case 2: 21

---

原文出處