11524 - InCircle

如下圖所示，三角形的內切圓與三角形的三邊相切，內切圓的圓心被稱為此三角形的「內心」，該點亦為三角形的三個等分角的交點。

如上圖所示，內切圓分別與AB, BC, CA交於點P, Q, R，分別產生m1:n1, m2:n2, m3:n3的比率。本題給定這三個比率與內切圓的半徑，請你計算出三角形ABC的面積。

Input

輸入資料的第一列有一個整數N(0 < N < 50001)表示有幾組測試資料。每組測試資料有四列，第一列有一個實數 r (1 < r < 5000)表示內切圓的半徑，接下來有三列，每列有兩個實數，分別表示m1, n1, m2, n2, m3, n2 (1 < m1, n1, m2, n2, m3, n3 < 50000)。

                                                           

Output

請每組測試資料輸出一列實數，表示三角形ABC的面積，請輸出到小數點後四位，誤差只要小於0.005即可被接受，請用雙精度浮點數作計算。

Sample Input                               Output for Sample Input

2 140.9500536497 15.3010457320 550.3704847907 464.9681681852 65.9737378230 55.0132446384 10.7791711946 208.2835101182 145.7725891419 8.8264176452 7.6610997600 436.1911036207 483.6031801012 140.2797089713

400156.4075 908824.1322

---

原文出處

11519 - Logo 2

Logo是一種使烏龜移動的程式設計語言，lt 指令使烏龜左轉一特定角度，rt 指令使烏龜右轉一特定角度，fd 指令使烏龜前進一段距離，bk 指令使烏龜後退一段距離。例如：

fd 100 lt 120 fd 100 lt 120 fd 100

以上指令使烏龜前進100個單位長，左轉120度，再前進100個單位長，再左轉120度，最後再前進100個單位長，在此例中，烏龜行走的路徑呈現一個正三角形，最後回到原點。距離一定不會是負值。

不幸的是，程式碼中有一道指令的距離數字遺失了，本題請你找出該數字為何。假設程式最終都會讓烏龜回到一開始出發的位置。

Input Specification

輸入資料的第一列有一個整數表示測試資料的組數，每組測試資料的第一列有一個整數表示指令總數，接下來的每一列依序為各個指令，最多共有1000道指令，每組測試資料僅有一個數目欄位為" ? "，表示遺失數目的指令。

Sample Input

1
5
fd 100
lt 120
fd ?
lt 120
fd 100

Output Specification

請找出遺失的數值為何，並輸出此數值(必為整數)，使得烏龜能回到一開始出發的位置。若遺失數值的指令為 lt 或 rt，則該數值為介於 0 ~ 359 之間的整數(包含0與359)。我們保證每組測試資料一定有唯一一組解。

Output for Sample Input

100

---

原文出處

11515 - Cranes

起重機對於建造大樓是一個很有力的工具，工地上有愈多起重機則施工的速度會愈快，但是愈多起重機卻也增加潛在的危險性，當一台起重機在旋轉的時候，也許一個不小心就會撞到另一台起重機，甚至於導致起重機翻覆，這是一種極危險的情況。為了避免這種潛在的危險，我們規定所有起重機必須離得夠遠，使彼此之間不可能產生碰撞或接觸。這項工作規定限制了工地上起重機的數量，也限制了施工的速度。

工地上會標示起重機可以被放置的位置及該位置上起重機可活動的範圍 r，起重機可以在以 r 為半徑的圓內自由轉動。本題你請在遵守工作規定的情況下放置起重機，並使得所有被放置的起重機的活動面積最大化。

Input Specification

輸入資料的第一列有一個整數表示測試資料的組數，每組測試資料的第一列為整數C表示所有起重機可被放置的位置，位置數最多15個，接下來有C列，每列有三個整數 x, y, r，其值介於-10,000 ~ 10,000，(x, y)為起重機的位置，r 為該位置起重機機臂的長度。

Sample Input

1
3
0 0 4
5 0 4
-5 0 4

Output Specification

請對每組測試資料計算最大的起重機活動面積A，並輸出B值使得A = B x π。

Output for Sample Input

32

---

原文出處

11513 - 9 Puzzle

Alex有一個類似拼圖的小玩具，該玩具上有數字1~9分別對應到 3 x 3 的方格中，該玩具允許兩種移動方式：

• 在任一列的三個數字中，水平地向右循環移動一格。
• 在任一行的三個數字中，垂直地向上循環移動一格。

有一天該玩具上的所有數字被不小心撞壞掉落，雖然事後已經修復但其上的數字卻被隨意放置，本題請你找出最少的移動步驟使之可以回復到下圖的狀態：

1	2	3
4	5	6
7	8	9

當然並非一定可以回復到上圖的狀態。

Input

輸入有多組測試資料，每組資料三列，每列三個整數，並以一個空白字元隔開。測試資料的最後以一個0表示資料結束。

Output

請對每組測試資料輸出最少移動的次數，且輸出移動的步驟為何，每個步驟以兩個字元表示，第一個字元以H表示水平移動，以V表示垂直移動，第二個字元分別以1, 2, 3表示移動哪一列或哪一行。若無解請輸出"Not solvable"。

Sample Input

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

Sample Output

1 H1
3 V1V3H1
Not solvable

---

原文出處

11512 - GATTACA

給定一組DNA序列，請找出重複次數大於等於二的最長子序列，並輸出其重複出現的次數。

Input

輸入資料的第一列有一個整數T表示測試資料的組數(1 <= T <= 100)，每組測試資料一列，表示一組DNA序列S，其長度為 n (1 <= n <= 1000)。你可以假定S僅包含字元A, C, G, T。

Output

請對每組測試資料輸出在S之中重複出現次數大於等於兩次的最長子序列，並輸出其出現的次數，並以一個空白字元隔開。若有不同組最長子序列存在，請輸出字典順序最小的該組子序列。若沒有重複的子序列則請輸出"No repetitions found!"。

Sample Input 

6
GATTACA
GAGAGAG
GATTACAGATTACA
TGAC
TGTAC
TTGGAACC

Sample Output 

A 3
GAGAG 2
GATTACA 2
No repetitions found!
T 2
A 2

---

原文出處

11507 - Bender B. Rodríguez Problem

有一台鐵絲彎曲器可用來彎曲鐵絲，將一條筆直的鐵絲之一端置放在三維空間笛卡爾座標系的原點上(0, 0 , 0)，另一端延伸至 +x 軸上，鐵絲的長度為L(L >= 2)，故另一端點的位置為(L, 0, 0)，如下圖所示。

鐵絲彎曲器會依序從(L-1, 0, 0)到(1, 0, 0)的位置上每隔一單位距離彎曲鐵絲，彎區的方式如下：

• 對於(i, 0, 0)的位置上選擇不作彎曲。
• 對於(i, 0, 0)的位置上彎曲90度，使之平行於+y, -y, +z, -z。

例如當L=3，於(2, 0, 0)的位置上使之彎向+y軸，並於(1, 0, 0)的位置上使之彎向-y軸，如下圖所示：

依序給定一組彎區的方式，請你判斷鐵絲最未端所指的方向(上例即指向+x方向)。

Input
每組測試資料的第一列有一個整數L(2 <= L <= 100000)表示鐵絲的長度。第二列給定在L-1個點上的彎曲的方式，第 j 個彎曲方式(1 <= j <= L-1)對應於(L-j, 0, 0)位置上，每種彎曲方式如下：

• No 表示不作彎曲。
• +y 表示向 +y 軸作彎曲。
• -y 表示向 -y 軸作彎曲。
  
• +z 表示向 +z 軸作彎曲。
  
• -z 表示向 -z 軸作彎曲。

當 L = 0 表示測試資料結束。

Output 

請對每組測試資料輸出鐵絲最末端所指的方向(+x, -x, +y, -y, +z, -z)。

Sample Input 

3
+z -z
3
+z +y
2
+z
4
+z +y +z
5
No +z No No
0

Sample Output 

+x
+z
+z
-x
+z

---

原文出處

11536 - Smallest Sub-Array

考慮有N個整數元素的序列，其元素為：

X₁ = 1

X₂ = 2

X₃ = 3

X_i = (X_i-1 + X_i-2 + X_i-3) % M + 1         for i = 4 to N

找出兩個整數 a 與 b 使得子序列 (X_a X_a+1 X_a+2 ... X_b-1 X_b) 包含所有 [1,K] 的整數。若有多組可能的解請選擇(b-a)值最小的那一組。也就是說請你從原序列中找出最小的子序列使得該子序列包含1~K。

例如N=20, M=12, K=4，可得到序列：

{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.

包含{1 2 3 4}的最小子序列長度為13，以藍色字型標示如下：

{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.

Input

輸入資料的第一列有一個整數T(T < 100)表示測試資料的組數，每組資料有三個整數：N(2 < N < 1000001)，M(0 < M < 1001)，K(1 < K < 101) 。

Output

請每組測試資料輸出資料編號與最小子序列的長度，若找不到符合要求的子序列則輸出"sequence nai"。

Sample Input                               Output for Sample Input

2 20 12 4 20 12 8

Case 1: 13 Case 2: sequence nai

---

原文出處

11545 - Avoiding Jungle in the Dark

Pilgrim打算長途跋涉前往聖地朝聖，路上可能會經過危險的區域，事實上，他會經過兩種路段：平地與叢林。在平地上不論一天的任何時刻都是安全的，但必須避免在晚上經過或停留在叢林中。另外，他不能不眠不休地連續旅行超過16個小時，最多16小時之後就必須休息，他可以在任何他想休息的時候休息，甚至連續一直休息也無所謂，不過一但他決定要休息，就必需整整休息8個小時。

給定路徑的地圖，請你幫他計算到達目的地所需的最短時間。

Input

輸入資料的第一列有一個正整數T(<= 100)表示測試資料的組數，每組資料一列，長度介於2~1000之間，且一定是以S開始以D結束，分別表示旅程的開始與結束，介於其中僅包含字元 '.'(表示平地)或 '*'(表示叢林)，從一地到另一地剛好花上一個小時，且他只會前進不會後退。他一開始會在一地的最左邊，整整經過一個小時之後他會前進到下一塊地的最左邊。

Output

請每組測試資料輸出資料編號與到達目的地所須的最短時間，若無法到達目的地請輸出-1。旅途的第一天他位於S的位置且出發時刻為早上六點，晚上的時段定義為下午六點到早上六點。

Sample Input                              Output for Sample Input

3 S.......D S...****................***.D S***********.***********D

Case #1: 8 Case #2: 36 Case #3: -1

原文出處

11561 - Getting Gold

有一個文字介面的探險遊戲，玩家在迷宮中行走尋找寶物，同時避免掉進陷阱，遊戲在一個四方形的區域中進行，玩家對迷宮的環境所知有限。

玩家可在迷宮中上、下、左、右任意地行走，行經的路上有寶物就可以撿起來，若玩家所在的位置四週(上、下、左、右)有陷阱的話，可以感覺得到危險，但並不知道陷阱在哪個方向，也不知道四週有幾個陷阱。若試著要走到有牆壁的位置，玩家會發現牆壁無法前進而停留在原地。

本遊戲的目地是在保證安全的情況下取得最多的寶物。

Input

輸入有多組測試資料，每組資料的第一列有兩個正整數W與H，其值介於3~50之間，分別為迷宮的寬度與長度，接下來有H列，每列有W個字元組成該迷宮，每一個字元意義表示如下：

P	玩家一開始所在的位置
G	該位置有寶物
T	陷阱
#	牆面
.	一般的地板

一個地圖只會有一個 'P'，且地圖四週一定以牆避圍起來。

Output 

請每組測試資料輸出在不會有落入陷阱的風險的情況下，玩家最多可取得的寶物數量。

Sample Input 

7 4
#######
#P.GTG#
#..TGG#
#######
8 6
########
#...GTG#
#..PG.G#
#...G#G#
#..TG.G#
########

Sample Output 

1
4

---

原文出處

11569 - Lovely Hint

給定一段句子，請你從中選出字母重新排列後組成一個"lovely string"，一個lovely string定義如下：

1. 僅由大寫字母組成，且不能為空字串
2. 每個字母對應一個值，A為1，B為2，以此類推。
3. 從中任選兩個字母，第一個字母的值為V1，第二個為V2，皆滿足下列不等式：5 x V1 <= 4 x V2。

本題請你計算最長的lovely string有幾個字元，並計算最長且不同的lovely string共有幾個。

Input

輸入一開始給定測試資料的組數N(1 <= N <= 30)，接下來的N列每列有一個字串S，字串最長250個字元，且不會有小寫字母。

Output

請每組測試資料輸出最長的lovely string的長度，接著輸出能達到這樣長度的lovely string有幾個。

Sample Input

2
HELLO.
I AM JAY.

Sample Output

4 1
4 2

Explanation

第一組資料的lovely string為：EHLO。
第二組資料的lovely string為：AIMY, AJMY二種。

---

原文出處

11576 - Scrolling Sign

有一個電子廣告看板的寬度可以顯示 k 個字元，看板一開始沒有顯示任何字元，之後每隔一段時間所有字元會向左移動一個位置，同時一個新的字元會出現在看板最右端，而靠近看板最左端的字元會被擠出看板。

對於某些特定的單字，其相同字母可重複利用來組成另一個單字，例如一個有三個字元寬的廣告看版，我們可用CATED來分別顯示CAT ATE TED。
如果一個訊息可以顯示地愈快，就會有愈多人看完整段訊息，本題要求你找到捲動最少字元的方法來顯示一段訊息。連續兩個欲顯示單字的切換之間可以顯示其他不必要的單字，然而，單字的顯示順序必須與給定的順序一致。若相同的單字連續出現超過一次，則只需要顯示一次即可。

Input Specification

輸入資料的第一列有一個整數 n 表示測試資料的組數，接下來每組測試資料的第一列有兩個整數，k 表示看板可以顯示的字元數，w 表示訊息有幾個單字，且 1 <= k, w <= 100，接下來的 w 列每列均為長度為 k 的大寫單字。

Sample Input

2
3 2
CAT
TED
3 3
CAT
ATE
TEA

Output Specification

請每組測試資料輸出一個整數，表示能顯示整段訊息的最少字元長度。

Output for Sample Input

5
5

---

原文出處

11532 - Simple Adjacency Maximization

請你求出滿足下列兩個條件的最小N值。

1. N的二進制表示式有P個1與Q個0(包含前導的0)。
2. 在N的二進制表示式中，有最多個其鄰近最少有一個0的1。

Input

輸入資料的第一列有一個整數C表示測試資料的組數，每組測試資料有兩個非負整數P與Q(1 <= P+Q <= 50)。

Output

請每組測試資料輸出最小的N值。

Sample Input                            Output for Sample Input

3 4 3 1 1 3 2

45 1 13

---

原文出處

11525 - Permutation

給定N與K，請你從1 ~ K的整數序列中找出所有排列組合中的第N種組合，其組合序號以0開始，並按字典順序排列。由於N的值可能非常大，所以會給定K個非負整數S1, S2, ..., Sk，N的值可藉由下列公式求出：

 

Input

輸入資料的第一列為整數T(<= 10)表示測試資料的組數，每組資料兩列，第一列有一個整數K(1 <= K <= 50000)。下一列有K個整數S1, S2, ..., Sk(0 <= Si <= K-i)。

Output

請每組測試資料輸出1~K的所有排列組合中的第N個，輸出的K個整數必須以空白字元隔開。

Sample Input                            Output for Sample Input

4 3 2 1 0 3 1 0 0 4 2 1 1 0 4 1 2 1 0

3 2 1 2 1 3 3 2 4 1 2 4 3 1

---

原文出處

11538 - Chess Queen

西洋棋棋盤上有一個白色的皇后與一個黑色的皇后，彼此可以互相攻擊的位置是在同一列，或同一行，或是在對角線的位置上。假設這兩個皇后被放置在2x2的棋盤上，則共有12種可以互相攻擊的位置，如下： 

在2x2棋盤上兩個皇后可以互相攻擊的12種可能的位置。

本題給定棋盤的大小(NxM)，請你計算兩個皇后可以彼此相互攻擊的位置總數。

Input

輸入資料最多5000列，每列給定兩個非負整數N, M(0 < N, M <= 10^6)。當N=0, M=0時表示測試資料結束。

Output

請每組資料輸出一列，表示NxM棋盤上所有可能攻擊位置的總數，輸出值大小可用64位元有號整數表示。

Sample Input                              Output for Sample Input

2 2 100 223 2300 1000 0 0

12 10907100 11514134000

原文出處

11550 - Demanding Dilemma

本題給定所有節點及所有連接節點的邊，請你判斷該組資料是否是一組簡單的無向圖。

一個簡單的無向圖定義為一組有序對 G = (V, E)，其中V為一組非空集合的節點，且E為連接無序對(u, v)的邊，其中u與v屬於V，且u不等於v。在此我們先定義若S為一集合，則 |S| 定義為S的大小(元素個數)。一個關聯矩陣(incidence matrix) M 為一個 |V| x |E| 大小的矩陣，其中若元素M(i, j)為 1 則表示第 j 個邊關聯於第 i 個節點(邊一定關聯於兩個節點)，否則為0表示沒有關聯。

給定一個 n x m 的矩陣，請判斷該矩陣是否為一簡單無向圖G的關聯矩陣，其中G = (V, E)且 |V| = n，|E| = m。

Program Input

輸入資料的第一列為整數 t (1 <= t <= 41)表示測試資料的組數。每組測試資料的第一列為兩個整數 n (1 <= n <= 8), m (0 <= m <= n(n-1)/2)，接下來有 n 列，每列 m 個整數(0或1)，第 i 列的第 j 個元素即為M(i, j)。


Program Output

若該組輸入資料為某個簡單無向圖的關聯矩陣則輸出"Yes"，否則請輸出"No"。


INPUT

3
3 3
1 1 0
0 1 1
1 0 1
3 1
1
1
0
3 3
1 1 0
1 1 1
1 0 0

OUTPUT

Yes
Yes
No

---

原文出處

11565 - Simple Equations

有三個不相等的整數 x, y, z 滿足下列關係式：

• x + y + z = A
• xyz = B
• x² + y² + z² = C

給定A, B, C的值，請你求出 x, y, z。本題的進階版本請見acm 11571。

Input

輸入資料的第一列有一個整數N(< 20)表示測試資料的組數，接下來有N列，每一列有三個整數A, B, C(1 <= A, B, C <= 10000)。

Output

請每組測試資料輸出對應的 x, y, z 之值，若有多組可能的解，請輸出 x 值最小的解，若還有多組 x 值相同的解則選擇 y 最小的那組。若無解請輸出"No solution."。

Sample Input

2
1 2 3
6 6 14

Sample Output

No solution.
1 2 3

---

原文出處

11571 - Simple Equations - Extreme!!

本題為acm 11565的進階版本，若本題正確，則11565也會正確。

有三個不相等的整數 x, y, z 滿足下列關係式：

• x + y + z = A
• xyz = B
• x² + y² + z² = C

給定A, B, C的值，請你求出 x, y, z。

Input

輸入資料的第一列有一個整數N(< 250)表示測試資料的組數，接下來有N列，每一列有三個整數A, B, C(1 <= A, B, C <= 6 x 10^18 = 6000000000000000000)。

Output

請每組測試資料輸出對應的 x, y, z 之值，若有多組可能的解，請輸出 x 值最小的解，若還有多組 x 值相同的解則選擇 y 最小的那組。若無解請輸出"No solution."。

Sample Input

2
1 2 3
6 6 14

Sample Output

No solution.
1 2 3

---

原文出處

11579 - Triangle Trouble

給定許多邊長，請你從中找出三個邊組成一個最大的三角形，並輸出其面積。

輸入的第一個整數表示測試資料的組數，每組測試資料的一開始給定一個整數N(3 <= N <= 10,000)，表示接下來有N個實數 si 分別表示所有可能的邊長(0 < si <= 100,000)，每組資料可能會分成許多列。

請每組測試資料輸出最大可能的三角形面積(請四捨五入到小數點後兩位)，若該組資料無法組成任一個三角形則請輸出"0.00"。

Sample input

2
4 3.0 4.0 5.0 100.0
3 1.0 2.0 4.0

Sample output

6.00
0.00

---

原文出處

11582 - Colossal Fibonacci Numbers!

第 i 個費氏數列元素被遞迴地定義如下：

• f(0) = 0 且f(1) = 1。
• f(i+2) = f(i+1) + f(i)，對於所有 i >= 0。

本題請你計算費氏數列的元素值。

輸入的第一列為整數 t (t <= 10,000)表示測試資料的組數，接下來每組測試資料包含三個整數 a, b, n，其中 0 <= a, b <= 2^64 (a 與 b 不同時為0)，且 1 <= n <= 1000。

請每組測試資料輸出 f(a^b)除以 n 的餘數。

Sample input

3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000

Sample output

1
21
250

---

原文出處

11572 - Unique Snowflakes

艾蜜莉打算從事一項新的生意：將雪花裝箱販賣！她設計一組機器可以收集從天空飄落的雪花，並將雪花一片接著一片輸送到生產線裝箱，當箱子裝滿就可以封裝後出售。

她希望一個箱子裡面的雪花大小皆不相同，但是收集到的雪花大小很多都是一樣的，艾蜜莉想知道所有箱子裡面，裝最多種不同大小雪花的那一個箱子裡面最多裝了幾個。機器裝箱時會依序地把生產線上的雪花一一地裝進去，直到完成後再換另一個新的箱子重新裝起。

Input Specification

輸入的第一列有一個整數表示測試資料的組數，每組資料的一開始會有一個整數 n，而接下來會有 n 個整數，表示生產線依序送出的雪花大小，其值介於0~10^9，雪花的大小由整數值大小來表示。輸入資料最多不會超過一百萬片雪花。

Sample Input

1
5
1
2
3
2
1

Output Specification

請每組資料一列輸出一個整數，表示裝最多種不同大小的箱子內共裝了幾個。

Output for Sample Input

3

---

原文出處