Description

Given a string S, output the reverse of S.

Input

The input consists of many lines. Each line is a string S with length <= 1000000.
The string S does not contain any spaces.

Output

Output the the reverse of S. One in each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/114/11462.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/103/10327.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/113/11321.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/108/10810.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/107/10763.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 uva.onlinejudge.org/external/5/514.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://poj.org/problem?id=2431

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/5/540.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://poj.org/problem?id=2559

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/119/11988.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/119/11997.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/5/572.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/100/10004.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/116/11624.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/100/10067.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/105/10596.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/124/12442.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/103/10305.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/3/302.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/110/11060.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/110/11080.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/2/200.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 http://uva.onlinejudge.org/external/100/10054.html

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在科學實驗的過程中，量測溫度與溫差是很常見的工作，不過因為有華氏(度F)與攝氏(度C)兩種常見的溫度表示法，所以有時候會有點麻煩。兩者的轉換公式如下：

 本題會給定以攝氏表示的初始溫度C，與以華氏表示的溫差F，請你以攝氏溫度表示新的溫度為何。

Input

輸入第一列有一個整數 T (<= 100)表示測式資料的組數。每組資料有兩個整數 C 與 d ( 0 <= C, d <= 100)，C表示初始溫度(以攝氏溫度表示)，d表示溫差(以華氏溫度表示)。

Output

請以攝氏溫度為單位輸出新的溫度為何，請輸出到小數點後兩位。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一個範圍 a 到 b ，請你找出 a 與 b 之間所有奇數的和。

例如：範圍 [3, 9] 中所有奇數的和就是 3 + 5 + 7 + 9 = 24 。

Input

輸入的第一列有一個整數 T （1≦T≦100），代表以下有多少組測試資料。 每組測試資料為兩列，包含兩個數 a 與 b （0≦a≦b≦100）。

Output

每組測試資料輸出一列，內容為 a 及 b 間所有奇數的和。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

費曼 (Richard Phillips Feynman) 是一個有名的美國物理學家及諾貝爾物理獎得主。他主攻理論物理並倡導量子電腦。他曾訪問南美十個月，在那兒演講並享受熱帶生活。他的成名作「別鬧了，費曼先生」及「你管別人怎麼想」中也包含了他在赤道以南的經歷。

他一生的嗜好是解及建立謎題、鎖、及密碼。最近，曾在1949年接待費曼的一位南美老農夫找到一些據信屬於這位年輕物理學家的筆記。在這些有關介子及電磁學的筆記中，夾有一張餐巾紙，上寫有個簡單的謎題：「在一個 N ×N 的方格中含有幾個不同的正方形？」

下面重現了該餐巾紙上的圖，顯示 N=2 時答案為 5。

Input

輸入有若干筆測資，每筆一行，含有一個整數 N，代表方格的邊長 (1 ≤ N ≤ 100)。

輸入的結束以含有一個零的一行表示。

Output

對於每筆測資，你的程式須輸出該筆測資一共包含幾個不同的正方形於一行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在這個問題中，根據所給的振幅(Amplitude)及頻率(Frequency)，你的程式要產生這樣的波。

Input

輸入的第一列有一個整數n，代表有幾組測試資料。接下來每組測試資料有2列，各有1個正整數（A、F），A代表振幅（A<=9），F代表頻率。
第一列以及各組測試資料間皆有一空白行。請參考Sample input。

Output

每組測試資料請輸出F個波，每個波振幅的水平高度為A。波本身是以其"高度"的內容所組成。每個波之間以一空白行分隔開來。
測試資料間也以一空白行分開。
請參考sample output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

算一算每行有幾個字（word）。
Word的定義是連續的字元（letter: A~Z a~z）所組成的字。

Input

測試資料每筆一行，每行至少有一個字。

Output

輸出每一行的word數。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

世界聞名的黑社會老大Vito Deadstone要搬到紐約來了。在那裡他有一個大家族，並且他們都住在Lamafia大道上。因為Vito時常要拜訪所有的親戚，他想要找一間離他們最近的房子，也就是說他希望從他的家到所有的親戚的家的距離的和為最小。

他恐嚇你寫一個程式來幫助幫助他解決這個問題。

Input

輸入的第一列有一個整數代表以下有多少組測試資料。

每組測試資料一列，第一個整數 r（0 < r < 500），代表他親戚的數目。接下來的r個整數s₁,s₂,......s_r為這些親戚房子的門牌號碼（0 < s_i <30000）。注意：有些親戚的門牌號碼會相同。

Output

對每一組測試資料，輸出從他的新家到所有的親戚的家的距離的和為最小為多少。2個門牌號碼s_i、s_j的距離為s_i-s_j的絕對值。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在小學時我們都做過加法的運算，就是把2個整數靠右對齊然後，由右至左一位一位相加。如果相加的結果大於等於10就有進位（carry）的情況出現。你的任務就是要判斷2個整數相加時產生了幾次進位的情況。這將幫助小學老師分析加法題目的難度。

Input

每一列測試資料有2個正整數，長度均小於10位。最後一列有2個0代表輸入結束。

Output

每列測試資料輸出該2數相加時產生多少次進位，請參考Sample Output。注意進位超過1次時operation有加s

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

據說，90%的大學一年級新生期望他們自己的成績能在全班平均之上，請你來幫忙驗證看看他們有沒有達成目標。

Input

輸入的第一列有一個整數 C 代表以下有多少組測試資料。每組資料的第一個整數 N 代表班級總人數 ( 1 <= N <= 1000 )。接下來有N個以空白或換行來間隔的整數，代表每個學生的期末總成績 ( 0 <= 分數 <= 100 )。

Output

對每組測試資料輸出一列，算出有多少百分比的學生成績比全班平均高，請四捨五入到小數第三位。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

要計算一個圓的圓週長似乎是相當簡單的事，如果你知道直徑的話。但是如果你不知道直徑呢？

給你不共線的三個點的座標，你的任務是算出通過這三個點的唯一圓的週長是多少。

Input

每組測試資料一列，含有6個實數x₁,y₁,x₂,y₂,x₃,y₃，分別代表三個點的座標（此三個點不共線）。通過這三個點的唯一圓的直徑不會超過1百萬。

Output

對每一組測試資料，輸出通過這三個點的唯一圓的週長是多少，請輸出到小數點後2位。

圓週率PI的值大約是 3.141592653589793

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在很多電腦問題中，常常會把一個陣列的資料做一些搬動。也就是說陣列中的資料被重新排列。有一個排列陣列資料的方法是用另一個稱為索引陣列（index array）來完成的。假設x是要被重新排列的陣列，而x'是重新排列後的陣列，那麼應該有一個關係存在於x和x'之間，使得x'_i=x_pi，而索引陣列就是記載這個關係用的。

為了避免誤解題意，以第一組Sample Input, Sample Output說明：索引陣列為3 1 2，代表接下來的浮點數應該分別輸出於第3列、第1列、第2列。

Input

輸入的第一列有一個整數，代表以下有幾組測試資料。每組測試資料2列，第1列為索引陣列，包含了 1~n 的整數（以某一種排列方式出現），在這裡n就是陣列中資料的數目。第2列則包含了n個浮點數。測試資料間空一列。請參考Sample Input

Output

對每一組測試資料根據索引陣列的順序輸出浮點數，每一個浮點數一列，且浮點數的樣式必須和輸入的一樣。測試資料間亦請空一列。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

計算 R = B^P mod M
對相當大的B、P、M請寫一個有效率的演算法來。

Input

每筆測試資料有3行，各有1個整數分別代表B、P、M。
其中 0 <= B <= 2147483647 0 <= P <= 2147483647 1 <= M <= 46340

Output

輸出計算的結果，每筆測試資料一行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1/33=0.030303030303…為一個循環小數，在這裡03這2個數字會永遠循環下去(cycle length=2)。以下是幾個分數的十進位表示法

寫一個程式輸入分數的分子和分母然後算出其十進位小數表示法的循環節。在此我們定義循環節為最先出現之最小長度的不斷重 複數字串。所以，1/250=0.004000000…的循環節為（0），其cycle length=1。655/990=0.6616161616161616161…的循環節為（61），其cycle length=2。

Input

每組測試資料一列，包含有2個數x,y，分別代表分子和分母。x為非負整數，y為正整數，且x,y<=3000

Output

對每一組測試資料，輸出其十進位的表示法及循環節的長度。以刮號將循環節表示出來。如果循環節長度大於50，則只要輸出前50個，後面用...表示即可。每組測試資料後請輸出一空白列。詳細格式請參考Sample Output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

摩斯電碼是一種不需使用慣用符號即可做長距離訊息傳送的工具。一組電碼由簡單的長音及短音信號聲所構成。其中短信號聲稱作dih，而長信號聲稱作dah。舉例來說，字母O的電碼即為dah dah dah（三長信號聲）。實際上，由於 電碼的設計上在兩個信號之間並沒有任何信號加以間隔，因此又有第三個符號，也就是靜音。電碼中兩個字母之間以一單靜音隔開，兩個單字之間則以一雙靜音隔開。

你現在被指派一個翻譯摩斯電碼的工作。關於信號已經被轉換成下面的方式：dih以一個點（.）來代替，dah以一個破折號（-）來代替，單靜音與雙靜音則分別由一個空格和二個空格來代替。

下表為摩斯電碼在題目中可能出現的字元，你的程式必須要能夠處裡這些字元。

Input

輸入的第一列有一個整數T(1 ≤ T ≤ 10)，代表有幾組測試資料。

接下來每組測試資料由一連串的點、破折號、空格所組成。每組資料的最大長度不超過2000。

Output

對每組測試資料輸出一段文字。首先輸出一列這是第幾組測試資料，緊接著一列輸出已經解碼的句子。

每組測試資料間請以一空白行隔開。句子一律以大寫字母印出。

請參考Sample Output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一連串的數字，請你找到第a 個數字連續加到第b 個數字的總和

Input

輸入第一行是k(k<100)，代表有k 組測資
每組測資第一行是n(n<10000) 與q(q<10000)，代表有n 個數字與q 個問題
接下來n 行每行有一個N_i(N_i < 1000)，表示第i 個數字
接下來q 行有兩個數字a ,b(1 ≤ a ≤ b ≤ n)，代表他的問題

Output

對於每個問題請輸出他的總和

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你兩個數字，請輸出他們的和

Input

輸入有多組問題，每組有兩個數字a ,b (−6 ∗ 10¹⁰⁰≤ a, b ≤ 6 ∗ 10¹⁰⁰)

Output

對於每組問題請輸出他的總和

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

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

1.該字串為一個空字串
2.如果Ａ和Ｂ都為正確的運算式，則ＡＢ也為正確的運算式，
3.如果Ａ為正確的運算式，則（Ａ）及〔Ａ〕都為正確的運算式。

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

Input

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

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

青蛙王國一年一度的運動會又開始了。最有名的遊戲是青蛙鐵人三項。青蛙鐵人三項其中一項是要比跳躍，該項目需要青蛙運動員跳過河。
這條河的寬度為L（1 <= L<=1000000000），有N（0<= N <=500000）個石頭從河的一邊到另一邊直線一字排開。青蛙只能藉由跳到石頭上慢慢跳到對岸，如果青蛙掉到水中，那他就出局了！
青蛙最多只能跳M次(1<= M <= N+1)，現在青蛙想要問：如果他們想要從河的一頭跳到另一頭，它們最少需要多少的跳躍力?(跳躍力為青蛙一次所能跳躍的最長距離)

Input

輸入有多組測資，每組測資第一行有三個正整數L,N,M
接下來的N行是第N個石頭到起始河岸的距離，另外兩個石頭不會出現在同樣的地方

Output

對於每組測資請輸出青蛙最少需要的跳躍力

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

不知道你們小時候有沒有玩過一筆畫，畫聖誕老人的房子的遊戲。畫出來的圖就像下面這樣：

經過這麼多年了，現在我們想要寫一個程式來知道如果我們從左下角開始畫起，共有多少種一筆畫聖誕老人房子的方法。下面的圖中的5個點用1到5來編號（從編號1開始畫起），箭頭代表一筆畫時筆的路徑。這個例子中的路徑為：153125432

Input

No input

Output

把所有可能的畫法按照數字大小由小到大排列好。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

為了呼應台灣電腦彩券的發行，我們再次推出跟組合有關的題目。你在買彩券的時候一定會挑你喜歡的數字吧！（雖然理論上不會增加你的中獎機率，但是你還是會選擇你的Lucky Number）我們的問題是：假設共有49個號碼，而你必須在你的 k （k>6）個Lucky Number中挑6個號碼作為一張彩券的數字組合。例如：你的Lucky Number的集合是{1,2,3,5,8,13,21,34}以就是說 k=8 ，那麼你就有C(8,6)=28種可能的彩券組合：[1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34].

你的任務是讀入k以及Lucky Number的集合，然後輸出所有可能的組合。

Input

每筆測試資料一行，每行的第1個整數代表 k（6

Output

對每一筆測試資料，輸出其所有可能的組合，每個組合一行。請注意輸出組合的順序需由小到大排列。測試資料之間請空一行。請參考Sample Output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

儲存一張圖的方式有許多種，比較常見的像是：adjacency matrix、adjacency lists。
adjacency matrix是用一個二維的陣列去紀錄一個node有沒有連到另一個node。但是有些時候一個node 連到的 node數量可能會過多，導致adjacency matrix的二維陣列無法存起來。例如，當node數大於100000時，adjacency matrix會達到10^10，記憶體會過大。這時候，我們就會改用adjacency lists去紀錄。
adjacency lists的紀錄方法是：對於每個node開一個link list，然後把有連線的node串在這條link list上。

Input

有多筆測資，測資第一行有兩個數字n,m

n (1表示node數，其中node編號從0到n-1

m (1表示指令的數量。

接下來的m行，每行有一個指令：

1.      Connect a b : 將a可以連到 b，保證不會重複連線，且自己不會和自己連線

2.      Ask a b : 詢問a是否可以連到b，可以的話輸出”Yes”，反之輸出”No”

3.      Cut a b : 將a到b的連線剪斷，如果a到b本來沒有連線請輸出”Error”

連線都是單向的，a連到b不表示b可以連到a

Output

對於Ask, Cut指令請按照規則輸出

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在班上，有些人因為個性上比較接近，會常常聚在一起。此時，我們會將這幾個人歸為”同一掛”。若A跟B是同一掛、B跟C是同一掛，則A跟C也會是同一掛的。現在，給你目前班上有多少人，及這些”誰跟誰是同一掛”的關係。有了這些關係，你就知道班上有幾個小團體了（獨行俠自成一伙）。
但其實有時候小團體的數量並不是那麼重要。我們只在意這些小團體中的最大勢力，也就是人最多的小團體。因為他們在表決公共事務時，會佔優勢。現在，給你這些關係圖，請找出人最多的小團體有幾個。

Input

有多組測資。
每組測資第一行，有兩個整數：N, K，表示班上有N個人、K個關係(1<=N<=1000)
接下來K行，每行有兩個整數X,Y，表示X跟Y是同一掛的。(1<=X,Y<=N)
當N=0時，測資結束。

Output

對於每組測資，輸出一個整數表示有幾個最大勢力的小團體。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

看下面的五張 9 x 8 的圖案：
........ ........ ........ ........ .CCC....
EEEEEE.. ........ ........ ..BBBB.. .C.C....
E....E.. DDDDDD.. ........ ..B..B.. .C.C....
E....E.. D....D.. ........ ..B..B.. .CCC....
E....E.. D....D.. ....AAAA ..B..B.. ........
E....E.. D....D.. ....A..A ..BBBB.. ........
E....E.. DDDDDD.. ....A..A ........ ........
E....E.. ........ ....AAAA ........ ........
EEEEEE.. ........ ........ ........ ........
      1                     2                    3                     4                   5
現在，把這些圖案按照 1—5 的編號從下到上重疊，第 1 張在最下面，第 5 張在最頂端。如果一張圖案覆蓋了另外一張圖案，那麼底下圖案的一部分就變得看不見了。我們得到下面的圖案：
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
對於這樣一張圖案，計算構成這張圖案的矩形圖案從底部到頂端堆疊的順序。
下面是這道題目的規則：
1. 矩形的邊的寬度為 1 ，每條邊的長度都不小於 3 。
2. 矩形的每條邊中，至少有一部分是可見的。注意，一個角同時屬於兩條邊。
3. 矩形用大寫字母表示，並且每個矩形的表示符號都不相同。

Input

有多組測資。
每組測資第一行：
兩個用空格分開的整數，
圖案高度 H (3 <= H <=30) 和圖案寬度 W (3 <= W <= 30) 。
每組測資第二行到第 H+1行 有H 行，每行 W 個字母。

Output

按照自底向上的順序輸出字母。如果有不止一種情況，按照字典順序輸出每一種情況（至少會有一種合法的順序）。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

這個世界上有許多不同的宗教信仰。你想要知道你就讀的大學中，學生們到底信了多少種不同的宗教。

在你就讀的大學中共有 n 個學生 ( 0 < n <= 50000 )。顯然你不可能對每個人個別詢問他們的信仰，而且某些學生也不方便透露他們所信的宗教。而解決這些問題的一種可能的方法是詢問 m ( 0 <= m <= n(n-1)/2 )對學生他們是否信同一個宗教 (例如他們可能一起去某間教堂，會知道他們彼此信相同的宗教 )。由這些資料，即使你沒辦法知道每個人信哪個教，但是你可以估計出他們最多信了多少種不同的宗教。你可以假設每個學生最多信一個宗教。

Input

輸入中包含了許多的測試資料。每筆測試資料由一列包含兩個整數 n 及 m 作為開頭。接下來的 m 列每列包含了兩個整數 i 和 j，代表學生 i 和學生 j 信同一個宗教。這些學生編號為 1 到 n。

當 n = m = 0 的時候代表輸入結束。

Output

對於每筆測試資料，請先輸出測試資料的編號(由1開始)，然後輸出學生們最多信了多少種不同的宗教。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

有一個鎮有N個居民。當然其中有許多人是朋友的關係。根據有名的諺語：「我朋友的朋友也是我的朋友」，所以如果A和B是朋友，B和C是朋友，那麼A和C也是朋友。

你的任務是算出在這個鎮中最大的朋友集團為多少人。

Input

輸入的第一列有一個正整數，代表以下有多少組測試資料。

每組測試資料的第一列有2個正整數 N 和 M 。N代表鎮上居民的數目（1 <= N <= 30000 ），M 代表這些居民中朋友關係的數目（ 0 <= M <= 500000）。接下來的M列每列有2個整數A，B（ 1 <= A,B <= N , A不等於B），代表A，B為朋友關係。這M列中可能有的會重複出現。

請參考 Sample Input。

Output

對每組測試資料輸出一列，在這個鎮中最大的朋友集團為多少人。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

有一個叫做Flatopia的島國。這個島的土地非常非常的平坦，但是他們的高速公路系統卻非常的爛。政府已經在一些重要的城鎮之間建立一些高速公路，然而仍然存在著一些城鎮是高速公路無法到達的。所以現在他們政府想要新建一些高速公路連接各城鎮，使得任2個城鎮之間的來往都可以透過高速公路系統。

城鎮按照1到N來編號，並且給你每個城鎮的座標。每條高速公路僅連接2個城鎮。所有的高速公路（包含已存在及將新建的）都是雙向且是直線的，其長度為2城鎮座標的距離。高速公路可以自由的穿越其他城鎮，但是駕駛人僅能在這條高速公路的端點城鎮才能轉到另一條高速公路。

Flatopia政府想要以最低的花費來新建高速公路，使得任2個城鎮的交通往來都可以透過高速公路系統。由於土地非常非常的平坦，花費的金錢與新建高速公路的長度成正比。你的任務就是幫助他們找出該在哪些城鎮之間新建高速公路，並且使得花費最低。

Input

輸入的第一列有一個正整數代表以下有幾組測試資料。

每組測試資料的第一列有一個正整數 N（1 <= N <= 750），代表城鎮的數目。接下來有N列，按照城鎮的編號每列有2個整數代表各城鎮的座標（其絕對值都不大於10000）。然後有一列含有一個正整數 M（0 <= M <= 1000），代表已經存在的高速公路的數目數。再接下來有M列，每列有2個整數，代表此條已存在的高速公路是連接哪2個城鎮。任2個城鎮間最多只有1條高速公路連接。

第一列與第一組測試資料間有一空白列，測試資料間亦有一空白列。請參考Sample Input。

Output

對每一組測試資料，請輸出所要新建的高速公路，使得任2個城鎮的交通往來都可以透過高速公路系統，並且花費最低。輸出時每條高路公路一列，以高速公路的2端點城鎮編號代表。如果不需新建高速公路，也就是說所有的城鎮都已經相連了，請輸出：No new highways need

測試資料間請空一列。請參考Sample Output。另外，本問題答案不一定是唯一的，judge有特殊程式來判斷，所以你不需要擔心這些。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

請將輸入的整數依照大小排列。

Input

有多組測資。每組測資第一行，有一個整數N (1<=N <=10⁵)代表有幾個數字，接下來有
N 行，每行有一個整數Ai(-10¹⁰⁰<=Ai<=10¹⁰⁰)代表要排序的數字(不會有無效0 開頭或-0)

Output

對於每組測資請由小到大輸出所有數字，測資間請空一行

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

高中物理老師通常認為把問題隱藏在題目的文字中比單純計算要難得多，畢竟學生必須先看得懂題目才行！

所以他們不喜歡把題目出成像``電壓＝10伏特，電流＝5安培，請問電功率＝？"這種類型，而比較喜歡出成``你有一組電路，包含一個電壓＝10伏特的電池和一個燈泡。若現在有5安培的電流通過燈泡，請問燈泡的電功率是多少？"（由於本題Input與英文有關，茲將原文收錄如下：``You have an electrical circuit that contains a battery with a voltage of U=10V and a light-bulb. There's an electrical current of I=5A through the bulb. Which power is generated in the bulb?".）

然而超過半數的學生並不會把注意力放在那些文字上，他們只會設法從文字中找出已知條件：電壓＝10伏特，電流＝5安培。然後思索``我該用哪條公式？Ah, yes, P=I*V；所以P=10V*5A=500W。完成！"

OK,這個方法並不是每次都有用，所以通常這些學生在物理考試中得不到頂尖的成績，但至少這種簡單的演算法已足以獲得及格以上的成績。（遺憾但卻是事實）

現在我們要試試看電腦能不能通過高中物理考試，我們先來解決這個功率-電壓-電流(P-U-I type)的問題 ，也就是說題目給任兩個已知條件，你要求出第三個。

你的工作就是寫一支程式可以讀入一段題目的文字，並根據上面所描述的簡易演算法來求出答案。

Input

輸入檔的第一行會先告訴你有多少個題目要求答案。

每一個問題由一列包括兩個明確的已知條件和一些額外的文字組成。已知條件會以下列格式出現：I=xA 或 U=xV 或者 P=xW（x屬於實數）
在單位（A，V或W）前可能會帶有一個數量級單位：m(milli,10的-3次方)，k(kilo,10的3次方)或M(Mega,10的6次方)。總而言之，已知條件（data field）會遵守下列文法：

DataField ::= Concept '=' RealNumber [Prefix] Unit
Concept ::= 'P' | 'U' | 'I'
Prefix ::= 'm' | 'k' | 'M'
Unit ::= 'W' | 'V' | 'A'

額外說明 ：
等號不會出現在已知條件（data field）外的地方。
已知條件（data field）中不會出現空白字元。
已知條件可能給　電壓＋功率　或　功率＋電流　或　電流＋電壓　三種形式。

Output

對每個題目必須輸出三列：
第一列輸出``Problem #k"，k代表第幾題。
第二列輸出答案（試所求輸出電壓、功率或電流）並將數量級轉換為基本單位及兩位有效小數位數（見sample output）
第三列為空白行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Kerker想幫可愛的小妹妹挑一些幸運數字，你可以幫他把不幸的數字除掉嗎?
題目會給你一個數字N
請輸出
1. 大於0
2. 整數
3. 不可以被3或7整除
4. 小於N
的所有幸運數字

Input

有多筆測試資料，每組測試資料一行．
1 < N < 10000

Output

如題目敘述輸出所有可能的數字
一組測試資料輸出一行
數字間以一個空白隔開
輸出的每筆答案間以一個空行隔開

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Kerker正在教國小的小妹妹判斷三角形，你可以寫一個程式幫他判斷是哪種三角形嗎??

Input

第一行是測試資料的組數T，接下來有T筆測試資料
每筆測試資料佔一行，分別有3個整數 a,b,c代表三角形的三條邊．
a,b,c 屬於 32 bit signed number

Output

如果輸入的三條邊:
1. 不合法 : 請輸出 : Oh~NO!!
2. 正三角形 : 請輸出 : 3 equal
3. 等腰三角形 : 請輸出 : 2 equal
4. 可以組成三角形但不是等腰或正三角 : 請輸出 : OK!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

有一天，小明看著手邊兩堆長度分別相同的紅線，說：I want to play a game.
(謎：Play 啥米game?)
遊戲內容如下：
1. 從兩堆紅線各取一條放在桌上。
2. 比較兩條線，選較短的那邊，從與其組成相同的那堆裡取一條接上去。
3. 重複步驟2. 直到兩條紅線長度相等。
假設兩堆紅線的量和桌子的長度都是無限大，給定一開始兩堆紅線的單位長度，請寫一個程式判斷最後的紅線的長度。

Input

有多筆測試資料，每筆資料會有一行，包含兩個正整數m, n (1≦m, n≦10,000,000)，中間以空白隔開，分別代表兩堆紅線的單位長度。

Output

每筆測資一行，輸出最後的紅線的長度。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

一群螞蟻走在一條長度為 L 公分的繩子上，每隻螞蟻的速度為 1 cm/sec。當一隻螞蟻走到繩子的盡頭時，它馬上掉下繩子（再也爬不起來了）。當兩隻螞蟻在繩子上相遇時，馬上掉頭往另一個方向走去。我們知道每隻螞蟻在繩子上的位置，但不幸的是，我們並不知道每隻螞蟻開始時走的方向。

你的任務是算出最快和最慢可能需要多少時間，所有的螞蟻都掉出繩子外。

Input

輸入的第一列有一個整數，代表以下有多少組測試資料。
每組測試資料以2個整數 L, n 開始，L 代表繩子的長度（單位：cm），n 代表一開始時繩子上有多少隻螞蟻。接下來有 n 個整數代表這些螞蟻一開始在繩子上的位置（從繩子的左端算起），且這些位置並沒有一定順序。所有的這些數都不會超過 10000。

請參考Sample Input。

Output

對每組測試資料輸出一列，包含2個整數代表最快和最慢可能需要多少時間（秒），所有的螞蟻都掉出繩子外。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一個n x n 的矩陣A，請你快速地計算出A_a1a2與A_b1b2兩個元素所圍成的長方形內，質數元素的個數。

Input

有多筆測試資料，每筆資料會有多行，並以空行區隔。
第1行有兩個正整數n,q(n代表矩陣的大小、q表示針對這筆測試資料會問的問題數量)。
第2行到第n+1行中，每一行會有n個數字表示矩陣的那一列中的元素。
第n+2行到第n+q+1行中，每一行會有4個數字a1,a2,b1,b2。
當n與q均為0時，代表input結束。
1 < n <= 1000, 1 <= q <= 100000, 1 <= a1,a2,b1,b2 <= n
1 <= A_ij <= 1000
並且保證A_a1a2永遠在A_b1b2的左上方。

Output

對於每筆測資，先印出Case #之後(請參考sample output)，再對於每個問題，印出題目要求的個數。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

“每到夏天我要去海邊　海邊有個漂亮高雄妹
只打電話不常見面我好想念　不知她會在哪個海邊“

夏天終於到來了，於是搗蛋與他快樂的基礎班同學跑去海邊玩了。說到沙灘，就不免一定要玩一下沙灘躲避球。同學們為了報答搗蛋的大恩大德，於是決定不用躲避球玩躲避球而是用西瓜玩躲避球。只可惜搗蛋什麼都不會，偏偏閃麻煩的能力一流。以至於玩到天黑，西瓜都還砸不到搗蛋身上。
飯後，他們決定把這顆西瓜切來當點心。此時，搗蛋又有意見了。搗蛋表示：『切成兩塊，一塊我的，一塊你們自己分。而且這兩塊的重量一定要都是偶數。』
請你幫幫忙，檢查這顆西瓜是否可以達成超龜毛搗蛋的要求。

Input

有好幾組測試資料。
每一組測試資料有一個正整數w (1 ≤ w ≤ 1000000000)，代表西瓜的重量。

Output

如果可以將西瓜切成兩部分，並且兩部分的重量都是不為零的偶數，請輸出”YES”。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

某天，紅線與蛋糕在下圍棋，但是他們覺得一般的規則太複雜了，於是稍微修改了一下。修改後的規則如下：

1. 紅線為黑方，蛋糕為白方，一開始雙方為0分。
2. 接著給定一個m×n的棋局，上面有黑子和白子，遊戲進行Q個回合。
3. 每一個回合，紅線和蛋糕各選擇一個點，接著計算兩點圍成的矩形範圍內黑子的數量，當作分數加在紅線的總分上；範圍內白子的數量，當作分數加在蛋糕的總分上。
4. 遊戲結束後，分數比較高的人獲勝。

Input

有多筆測資，每筆測資有多行。
第1行有三個數字，分別代表m,n,Q。
第2行到第m+1行，每行有n個字元。這些字元代表棋局，’B’表示黑子，’W’表示白子，’.’表示沒有被任何一方佔據的格子。
第m+2行到第m+Q+1行中，每一行有4個數字a1,a2,b1,b2，表示紅線在該回合選了(a1,a2)，而蛋糕選了(b1,b2)。
當m,n,Q均為0時，測資結束。

1<=m,n<=1000。1<=Q<=1000000。
紅線與蛋糕所選擇的點一定在棋盤範圍內。
座標：棋盤左上角為(1,1)，右下角為(m,n)。

Output

對於每一筆測資，請輸出三行，第一行輸出Case#，第二行輸出紅線和蛋糕各得到了幾分，最後第三行再印出是誰獲勝，平手請輸出”Tie!”。(請參考sample output)。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

想必大家都知道，若N是一個完全平方數，則必定存在另一個數M使的
N = M*M．前幾個完全平方數為：1,4,9,16,25…

現在給你一個正整數A，想知道1~A之間(包含1和A)到底有多少個平方數呢?

這問題在A很小的時候，我們可以用prefix sum解決，我們可以先開一個大小為A的陣列，全部初始化為0，然後在完全平方數的地方擺上1，這時開始做prefix sum，就可以快速得到所有正整數<=A的答案了．
比如說 :
1 2 3 4 5 6 7 8 9 10 <-陣列編號
1 0 0 1 0 0 0 0 1 0 <-一開始只有完全平方數是1
1 1 1 2 2 2 2 2 3 3 <-做一次prefix sum
這時<=10的問題的答案我都可以O(1)直接輸出了!

但是，kerker又覺得這樣太快寫完的人會很無聊，所以！這邊的正整數A是大數!!!如果是大數的話你有更好的做法嗎??

Kerker給願意挑戰的人一個優惠，答案只需要第一個位數正確就可以了歐！比如說這組測資的答案是593個，那你只需要輸出500就可以了^.< (也就是第一個位數正確，其他位置為0)

Input

輸入有多組測資，每組測資一行．
每行包含一個正整數A．(1 <= A <= 10^1000)
當A=0時表示輸入結束．

Output

每組測資輸出一行，輸出1~A(包含)有多少完全平方數．
僅需最大位數正確即可!(但其他位數要為0!)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

大家都知道搗蛋是一個非常邪惡的桌遊玩家，這次他決定開發一個可以洗腦對手的工具，令對手不自覺的幫助搗蛋取得勝利。這個工具會在收到搗蛋以數字編輯成的指令後，經過一連串的分解，轉成只由0~3組成的數字，並灌輸至對手的腦波內，來達到控制思想的目的。
分解的過程如下：
1.將輸入的指令視為一個數字N
2.如果N是偶數，那麼將N分解成N/2-1和N/2+1。
是奇數，那麼將N分解成(N-1)/2和(N+1)/2。
3.持續重複分解的動作，直到要被分解的數小於或等於3。
4.最後將這些分解出來的數字依分解順序印出來，就可以得到控制對手所需要的數字了。
現在，請你幫助搗蛋完成分解的工作吧！





範例：

Input

會有多組測資，每組測資會有一行數字N。1<=N<=10000

Output

對於每筆測資，輸出可以控制別人思想的數字。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

現在百貨公司正在舉行小熊軟糖大拍賣，優惠方案非常簡單，用五個吃完的軟糖包裝紙就可以換到一個免費的小熊軟糖。當然，吃掉那些免費軟糖之後拿到的包裝紙如果夠多的話，就可以再拿去換免費的軟糖。舉例來說：如果我們買了21個軟糖，那麼吃掉這21個之後會得到21份包裝紙，我們可以用其中的20個包裝紙換到4個免費的軟糖；同樣的，再將這4個新的軟糖吃掉之後，我們便可以再得到4個包裝紙，這時候就有5個包裝紙，又可以再換到1個軟糖；所以我們總共可以吃到21+4+1=26個小熊軟糖~^o^~。
某天，YLC在逛街的時候，"不小心"看到了這家百貨公司，於是馬上就買了一大堆小熊軟糖(不愧是貪吃鬼XD)，你可以幫忙算算看她最多可以吃到幾個小熊軟糖嗎?
另外，為了方便大家計算，我們不考慮最後剩下4個包裝紙的時候，跟旁邊的人借一張，換完軟糖吃掉之後，再把包裝紙還回去的這種情況喔！
最後，由於YLC超愛軟糖，所以她購買的數量非常龐大喔！

Input

有多筆測資。每組測資只有一行，裡面只有一個整數N，代表YLC這次買了幾個小熊軟糖。1<=N<=10^200。數字不會有無效0開頭。

Output

對於每一筆測資，輸出YLC總共可以吃到幾個小熊軟糖！

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

蛋糕是個有條理(龜毛)的人，每次寫分數時都一定要寫得整整齊齊，連分線長度都要畫得跟數字長度一樣長，而且堅持把數字寫在分線的中間。給你分子和分母，你能幫助他輸出工工整整的分數嗎？

Input

第一列有一數字t, 代表測資數量。接下來t列，每列有兩個數字x,y，分別代表分子和分母。

t<=50

x,y為長度不超過15位數的非負整數，且開頭不會有多餘的0(不會出現00002, 034, 012...)

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We are trying to construct a labyrinth on a board of size m × n. Initially, on each square of the board we find a piece of thin plywood of size 1 × 1 with one of the following three patterns painted on it.

+---+ +---+ +---+
|   | |   | |   |
|   | |** | |***|
|   | | * | |   |
+---+ +---+ +---+
Type1 Type2 Type3

Now, your task is easy!!
You need to count how many number of type 2 in the labyrinth!

Input

The first line of input contains a number c giving the number of cases that follow. The test data for each case start with two numbers m and n giving the number of rows and columns on the board. The remaining lines form an ASCII rendition of the initial board with the pieces placed on squares. The characters used in the rendition are +, -, |, * and space. See the sample input for the format. The size of the input board will be such that m , n ≤ 64.

Output

For each case print in a single line how many number of type 2.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

遠通電收在國道上佈下了天羅地網，目的就是為台灣人民服務（？）。
但近來發現門架故障率越來越高，使得營收的一大部分都得拿去維修門架。
已知一個門架的維修的成本為維修總站與門架的距離平方，
亦即假如維修總站的所在位置為X_station，門架的位置為X_gate，
那麼此門架的維修成本將為(X_station-X_gate)²
不堪虧損的遠通拜託你幫他在國道上找尋一個地點設為維修總站，
使得所有門架的維修成本和為最小。

儘管你很不願意，但身為一個善良的工程師，還是幫幫可憐的遠通吧。

Input

輸入的第一列有一個整數 t (0 < t < 10) 代表以下有多少組測試資料。
每組測試資料一列，第一個整數 r（0 < r <= 1000000），代表門架的數目。接下來的r個整數g1,g2,......gr為這些門架在國道上的位置（0 <= gi <= 500）。
注意：同一個位置可能會有許多門架（重複扣款嘛）。

Output

單行輸出一個整數，代表最小的維修成本和。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

前年，NTHU派出了一些選手到越南參加ACM-ICPC預選賽，但是他們一群人卻不幸誤闖了地雷區，
導致他們都不敢隨意亂動，否則很可能會被炸死T_T。
好在你身處台灣，而且你掌握了那個地雷區中全部M個的地雷位置，
並且擁有地雷和選手們所在的座標位置。
現在，在2D座標軸上，給定你選手們和所有地雷的座標，請你按照順序，
將地雷離選手的距離遠到近排序，並輸出地雷的編號和座標。

Input

第一行有一整數T，代表測試資料的組數，每筆測資有多行。
對於每筆測資，第一行會有兩個整數x₀,y₀，代表NTHU選手的座標。
第二行有一個正整數M，表示地雷的總數量。
接下來M行，每行各有兩個整數x_i,y_i，代表第i個地雷的座標。
地雷的編號為1~M。

1<=M<=1000
-1000<=x_0~M,y_0~M<=1000

Output

對於每筆測資，按照題目要求輸出地雷標號與位置，輸出格式請參考sample output。
如果有兩顆地雷的距離相等，則先輸出編號較小的那一個。
每筆測資間請空一行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

設 A 為一個有 n 個數字的序列。
如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則稱他們為一個逆序數對

Input

多筆測資
每筆測資兩行
第一行為一正整數n
第二行n個數字，表示A序列
以EOF結束輸入

所有數字皆可存於32bit signed integer(ex: int in C++)
n<=10⁶

Output

每筆測資輸出一行一個數字：A的逆序數對的個數

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Kerker最喜歡小妹妹了>////<最近有個可愛的妹妹正在學分數，可是她常常在數字前面加上很多空白或是多餘的0，就連數字的中間也會有空白!例如把"3010"寫成"00 03 010"，只是碰到這麼可愛的妹妹，Kerker當然不忍心責備她，所以他要求你把幫小妹妹把數字寫成正常的樣子。

Input

第一列有一個數字t，代表測資數目。接著有t組測資，每組測資四列。第一列為分子，第二列為分線(長度至少為3)，第三列為分母，第四列為空白列。分子和分母的前後及中間都可能夾雜著多個0和空白，但至少會有一個數字，不會全部為空白。

第一和第三列只會出現數字和空白

第二列只會出現'-'

每列的長度(含數字、空白和'-')不超過100個字元

Output

每組測資輸出一列，格式為"分子/分母"，分子和分母前面不得有多餘的0和空白，後面也不得有多餘的空白。請參考sample output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We are trying to construct a labyrinth on a board of size m × n. Initially, on each square of the board we find a piece of thin plywood of size 1 × 1 with one of the following three patterns painted on it.

+---+ +---+ +---+
|   | |   | |   |
|   | |** | |***|
|   | | * | |   |
+---+ +---+ +---+
Type1 Type2 Type3

Now, your task is easy!!
You need to count how many number of type 3 in the labyrinth!

Input

The first line of input contains a number c giving the number of cases that follow. The test data for each case start with two numbers m and n giving the number of rows and columns on the board. The remaining lines form an ASCII rendition of the initial board with the pieces placed on squares. The characters used in the rendition are +, -, |, * and space. See the sample input for the format. The size of the input board will be such that m , n ≤ 64.

Output

For each case print in a single line how many number of type 3.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

遠通電收在國道上佈下了天羅地網，目的就是為台灣人民服務（？）。
但近來發現門架故障率越來越高，使得營收的一大部分都得拿去維修門架。
已知一個門架的維修的成本為維修總站與門架的距離平方，
亦即假如維修總站的所在位置為X_station，門架的位置為X_gate，
那麼此門架的維修成本將為(X_station-X_gate)²
不堪虧損的遠通拜託你幫他在國道上找尋一個地點設為維修總站，
使得所有門架的維修成本和為最小。

儘管你很不願意，但身為一個善良的工程師，還是幫幫可憐的遠通吧。

Input

輸入的第一列有一個整數 t (0 < t < 10) 代表以下有多少組測試資料。
每組測試資料一列，第一個整數 r（0 < r <= 1000000），代表門架的數目。接下來的r個整數g1,g2,......gr為這些門架在國道上的位置（0 <= gi <= 500）。
注意：同一個位置可能會有許多門架（重複扣款嘛）。

Output

單行輸出兩個整數，以空白分隔，分別代表最小的維修成本和以及維修總站所在的位置。
（如果有多個位置皆能最小化維修成本和，請輸出最小的那個）

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

有一天，呆羊不小心把M個圖釘灑到地上，
為了避免有人踩到圖釘，他必須把掉在地上的圖釘清理乾淨，
由於一個一個撿起來實在太慢了，所以他決定用一個強力磁鐵來吸住它們。
但是現在有個問題，由於圖釘實在太多了，
呆羊想知道圖釘們會以怎樣的順序接近他，以免被圖釘刺到。
現在，給定一個二維座標，以及呆羊和圖釘們的座標，請你寫一個程式，按照順序給出被磁鐵吸住的圖釘。

Input

第一行有一整數T，代表測試資料的組數，每筆測資有多行。
對於每筆測資，第一行會有兩個整數x₀,y₀，代表呆羊的座標。
第二行有一個正整數M，表示圖釘的總數量。
接下來M行，每行各有兩個整數x_i,y_i，代表第i個圖釘的座標。
圖釘的編號為1~M。

1<=M<=1000
-1000<=x_0~M,y_0~M<=1000
Hint:距離磁鐵較近的圖釘會先被磁鐵吸引。

Output

對於每筆測資，按照題目要求輸出圖釘的標號與位置，輸出格式請參考sample output。
如果有兩顆圖釘同時到達，那麼輸出編號較小的那一個。
每筆測資間請空一行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A 為一個有 n 個數字的序列。
現在你一次可以交換相鄰兩個數字
給一序列A，最少需要幾次交換呢？

Input

多筆測資
每筆測資兩行
第一行為一正整數n
第二行n個數字，表示A序列
以EOF結束輸入

所有數字皆可存於32bit signed integer(ex: int in C++)
n<=10⁶

Output

每筆測資輸出一行一個數字：將A排序好所需的交換次數

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1282 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=655 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

神魔之塔是近期內很有名的轉珠遊戲，身為重度玩家的 HappyStorm 自然擁有很多張卡片。

這天好奇的她想實作一個篩選排序系統讓自己能快速地找到想找的卡片。
為了簡化問題，一張卡片只會有以下五種屬性，分別為 "種族(race)", "卡號(id)", "血量(hp)", "攻擊力(atk)", "回復力(rec)"。
除了 "種族" 屬性為字串以外，其餘四個屬性皆為正整數。
Coding 不強的她拜託你幫忙把這個系統實作出來，在輸入篩選排序的條件下，印出所篩選出的卡片。

儘管你很不願意，但身為一個善良的工程師，還是幫幫可憐的 HappyStorm 吧。

Input

輸入的第一行有一個整數 t (0 < t <= 100) 代表以下有幾組測資。
每組測資的第一行有一個整數 n (0 < n <= 500) 代表HappyStorm的背包總共有幾張卡片。
接下來 n 行為卡片的屬性資料：
每行開頭有一個字串代表種族(保證只有以下五種："Elf", "Human", "Dragon", "God", "Beast")，
和四個正整數id (0 < id <= 500), hp, atk, rec (0 < hp, atk, rec <= 4000)分別表示卡號、血量、攻擊力、回復力。
接下來兩行分別說明要篩選的種族與屬性排序（皆由大排到小）的優先順序：
第一行有一個字串表示要篩選出的種族。
第二行有4個字串("ID", "HP", "ATK", "REC")代表排序的優先順序，放在愈前面的字串優先權愈高。

Output

對於每一筆測資請輸出"Case #"以及所篩選出的卡片，分行輸出。
若無符合篩選條件的卡片，請輸出"Cards not found"。
詳情請見sample input/output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一張長方形的紙, 依序做以下動作 :

1. 從目前的紙張裡剪掉一個最大的正方形
2. 變成一張比較小張的紙了
3. 如果這張紙還是長方形的話, 就回到步驟1繼續
4. 否則輸出最後的正方形的邊長

Input

這題的輸入很機車, 每個數字都會被放在ASCII構成的圍牆的框框內, 如下所示 : (以數字237458為例)

+---+---+---+---+---+---+
|2  |   |   |   |   | 8 |
|   |  3|   |4  | 5 |   |
|   |   | 7 |   |   |   |
+---+---+---+---+---+---+
數字會出現在圍牆內的某個位置, 一個邊長會由一串圍牆所組成, 因此一張紙(一個testcase)會由兩串圍牆所組成!!

輸入的每行長度都不會超過55個字元.
輸入內不會有無意義的空行.

Output

然後請輸出最後的正方形的邊長, 輸出時也需要把數字放入圍牆內, 但為了讓kerker方便檢查大家的數字, 數字都必須放在每一道牆的正中間, 如下所示 : (以數字237458為例)

切勿輸出開頭的0!
+---+---+---+---+---+---+
|   |   |   |   |   |   |
| 2 | 3 | 7 | 4 | 5 | 8 |
|   |   |   |   |   |   |
+---+---+---+---+---+---+

並且請在測資間空行!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給首項，公比，項數

你會求等比級數和嗎？

由於數字可能很大，所以只要你算出這個和除以m的餘數

Input

多筆測資

每筆一行四個整數，分別為首項a、公比r、項數n、和除數m

1 ≤ a,r,m ≤ 2³¹-1

1 ≤ n ≤ 10¹⁵

以EOF結束

Output

對每筆冊資輸出一行一個整數，即答案

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

蛋糕最喜歡吃蛋糕，所以他舉辦了一個蛋糕大賽，有上千名參賽者參加，現在終於進行到最後一個階段了!!兩位參賽者在爭奪冠軍寶座!!!
蛋糕請來了一群評審投票給這兩位參賽者，支持參賽者A的人在牌子上寫0，支持參賽者B的人在牌子上寫1。蛋糕想要知道第i位評審和第j位評審間(包含i和j)是否都將票投給了相同的參賽者。
你的任務是快速地給予蛋糕答覆，如果寫出一個有效率的程式，蛋糕或許會願意分你一片冠軍蛋糕。

Input

第一列有一個數字T，代表總共T組測資。
每組測資的第一列是由0和1組成的字串，長度為N，代表第1位到第N位評審投的票。
每組測資的第二列為一個數字Q，代表蛋糕有有Q個問題，接下來的Q列，每列有兩個數字a, b，請判斷第a位評審到第b位評審(包含)是否都將票投給了同一位參賽者。

T<=25
1<=N<=500000
1<=Q<=10000
1<=a<=b<=N
所有數字皆為正整數

Output

針對每組測資，第一列請先輸出"Case x:"(x是case number)，接下來輸出Q列，針對這組測資的Q個問題作回答，答案只會是Yes或是No。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

世界上有許多有錢人，比如巴菲特、祖柏克等等。
雖然你並不是有錢人中的一員，
但你是一個管理全人類資產資料庫的工程師，
現在Time時代週刊的記者們為了百大富翁排行榜，
並須向你詢問一些有錢人擁有多少資產。
由於人類的總數量實在太多了，
所以你決定寫一個程式幫助解決問題。

Input

題目有多筆測資。
每一筆測資有多行。
第1行會有兩個正整數N,Q，
N代表你的資料庫中的資料總數，Q代表時代周刊要詢問的問題數量。
第2行到第N+1行，每行有兩個字串S與P，資串間以空白區隔
S代表人名，P表示他所擁有的資產數量。
資產的格式為"XMYKZ"，其中X,Y,Z為三位整數。
ex: 100M000K000表示資產為100百萬即1億
001M200K500表示是財產為1百萬200千500即120萬500元
之後會有Q行，每一行會有一個字串Name，代表記者欲詢問的人，
記者所詢問的人一定存在於你的資料庫名單中。

1<=N,Q<=50000
1<=strlen(S)<=20，並且人名只由小寫英文字母'a'~'z'組成，並且不重複。
X,Y,Z為三位數整數，會有零開頭。

Output

對於每筆測資請輸出Q+1行
第1行輸出 "----Report x----"，其中x為第幾組測資。
之後對於每一個詢問，輸出一個字串與一個數字，
即該人的人名，以及他所擁有的資產。
注意資產不得印出多餘的0。
Hint:O(N*Q)的做法會TLE!!!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

龍族拼圖是近期內很有名的轉珠遊戲，身為重度玩家的 HappyStorm 自然擁有很多張卡片。

這天好奇的她想實作一個篩選排序系統讓自己能快速地找到想找的卡片。
為了簡化問題，一張卡片只會有以下五種屬性，分別為 "種族(type)", "卡號(id)", "血量(hp)", "攻擊力(atk)", "回復力(rec)"。

除了 "種族" 屬性為字串以外，其餘四個屬性皆為正整數。
Coding 不強的她拜託你幫忙把這個系統實作出來，在輸入篩選排序的條件下，印出所篩選出的卡片。

儘管你很不願意，但身為一個善良的工程師，還是幫幫可憐的 HappyStorm 吧

Input

輸入的第一行有一個整數 t (0 < t <= 100) 代表以下有幾組測資。
每組測資的第一行有一個整數 n (0 < n <= 500) 代表HappyStorm的背包總共有幾張卡片。
接下來 n 行為卡片的屬性資料：
每行開頭有一個字串代表種族(保證只有以下五種："AttackType", "BalanceType", "Dragon", "Demon", "God")，
和四個正整數id (0 < id <= 500), hp, atk, rec (0 < hp, atk, rec <= 4000)分別表示卡號、血量、攻擊力、回復力。
接下來兩行分別說明要篩選的種族與屬性排序（皆由大排到小）的優先順序：
第一行有一個字串表示要篩選出的種族。
第二行有4個字串("ID", "HP", "ATK", "REC")代表排序的優先順序，放在愈前面的字串優先權愈高。

Output

對於每一筆測資請輸出"Case #"以及所篩選出的卡片，分行輸出。
若無符合篩選條件的卡片，請輸出"Cards not found"。
詳情請見sample input/output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Kerker正在教小妹妹最簡分數, 給你一個分數, 請問分子分母要同除哪個數才能變最簡分數呢??

請你幫幫kerker吧!!!

Input

但是這題的輸入很機車, 每個數字都會變成相等數量的’*’被放在ASCII構成的圍牆的框框內, 如下所示 : (以數字237458為例)

+---+---+---+---+---+---+
|*  | * |** | * |* *|***|
| * | * | **|** |***| **|
|   | * |***| * |   |***|
+---+---+---+---+---+---+
圍牆內的’*’的位置是隨機的, 但是’*’的數量一定就是那個位置的數字!

一個數字(分子分母)會由一串圍牆所組成, 因此一個分數(一個testcase)會由兩串圍牆所組成!!

輸入的每行長度都不會超過55個字元.
輸入的第一串圍牆為分子, 第二個圍牆為分母.
輸入內不會有無意義的空行.

Output

然後請輸出要除哪個數字才能變成最簡分數, 輸出時也需要把數字放入圍牆內, 但為了讓kerker方便檢查大家的數字, ‘*’都必須從最左上角開始放, 第一橫排放完後才可以放到下一排(由左而右, 由上到下), 如下所示 : (以數字237458為例)

切勿輸出開頭的0!
+---+---+---+---+---+---+
|** |***|***|***|***|***|
|   |   |***|*  |** |***|
|   |   |*  |   |   |** |
+---+---+---+---+---+---+

並且請在測資間空行!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A和B是兩種細菌，這兩種細菌每天會增長，不過由於互利共生，AB細菌增長的量會跟彼此相關，公式如下

a(t) = 2*a(t-1) + b(t-1)

b(t) = 1*a(t-1) + 3*b(t-1)

a(t), b(t)分別表示時間t, A細菌和B細菌的數量

給時間0兩細菌的數量，求時間t的兩細菌的數量

對了，由於數量可能太大，你只要輸出數量除以1000000007的餘數就好

Input

多筆測資

每筆冊資一行三個整數，分別為時間0時, A細菌的數量a, B細菌的數量b, 第三個整數為時間t

以EOF結束

0 ≤ a,b ≤ 2³²-1

0 ≤ t ≤ 10¹⁵

Output

每筆測資一行
時間t的兩細菌的數量(mod 1000000007) 以一個空白格開

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

大家有玩過21點紙牌遊戲吧？這個遊戲改良版叫做"K點遊戲"，規則是玩家可以從一疊牌中取走連續的x張牌(玩家自己決定 x，0 <=x <=牌的數目)，不一定要從第1張開始拿，也就是玩家可以從第i張開始，拿到第i+x-1張，最後將手上的牌的點數加總，總和最接近K且大於K的人就獲勝了。蛋糕有透視能力，他知道前方這疊牌從上到下分別是多少點。將牌的點數告訴你，你能幫蛋糕計算他可以得到最好的結果是什麼嗎？

Input

有多組測資。
每組測資第一列有兩個正整數N, K，N代表這疊牌的數量。接下來會有N個整數，代表N張牌的點數。
1<=N<=2000
-1000000<=K<=1000000
-500<=牌的點數<=500

Output

對每組測資，若不論從這疊牌的那張開始取，不論取幾張，點數和都無法超過K，請輸出"Cake will lose QAQ"。
否則，請輸出一個整數，代表蛋糕在這疊牌中可以得到的最好的點數和。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

世界上有許多有錢人，比如巴菲特、祖柏克等等。
雖然你並不是有錢人中的一員，
但你是一個管理全人類資產資料庫的工程師，
現在Time時代週刊的記者們為了百大富翁排行榜，
並須向你詢問擁有至少一定財產數量的人有多少。
由於人類的總數量實在太多了，
所以請你決定寫一個程式幫助你解決問題。

Input

題目有多筆測資。
每一筆測資有多行。
第1行會有兩個正整數N,Q，
N代表你的資料庫中的資料總數，Q代表時代周刊要詢問的問題數量。
第2行到第N+1行，每行有兩個字串S與P，資串間以空白區隔
S代表人名，P表示他所擁有的資產數量。
資產的格式為"XMYKZ"，其中X,Y,Z為三位整數。
ex: 100M000K000表示資產為100百萬即1億
001M200K500表示是財產為1百萬200千500即120萬500元
之後會有Q行，每一行會有一個數字Profit，代表記者所詢問的財產，
記者所詢問的財產數量並不一定會剛好是某個人的財產。

1<=N,Q<=50000
1<=strlen(S)<=20，並且人名只由小寫英文字母'a'~'z'組成，並且不重複。
X,Y,Z為三位數整數，會有零開頭。
0<=Profit<=999999999

Output

對於每筆測資請輸出Q+1行
第1行輸出 "----Report x----"，其中x為第幾組測資。
之後對於每一個詢問，輸出兩個數字，
第一個數字為記者詢問的財產，
第二個數字代表有多少人的財產大於等於詢問的數量，
Hint:O(N*Q)的做法會TLE!!!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在HappyStorm的衣櫥裡，有著各式各樣的襪子。
身為襪控的她，每天最快樂的事就是把玩她收藏的襪子。
有一天，她發現一件驚人的事情：有些襪子不見了！！！

兩隻同樣的襪子一起不見或許還有可能騙過HappyStorm，
但如果只有一隻不見，身為專業襪控的HappyStorm可是會為此感到難過的。

傷心欲絕的HappyStorm想請你幫忙找出不成對的襪子。
儘管你很不願意，但身為一個善良的工程師，還是幫幫可憐的HappyStorm吧。

Input

輸入的第一行有一個整數 t (0 < t <= 10) 代表以下有多少組測試資料。
每組測試資料的第一行有一個整數 n (0 < n < 1000000)，代表HappyStorm的衣櫥裡總共有幾隻襪子。
接下來的 n 行，每行包含兩個以空白分隔的字串name, size，分別代表襪子的型號以及尺寸(襪子無左右之分)。
其中：
name 為長度固定為3且只由小寫字母(a-z)所組成的字串。
size 由小到大只會出現 {"S", "M", "L", "X", "XL"} 這五種。

註：正常的襪子是沒有X的，但身為一個專業襪控，總是能收集到一些奇行種。

Output

對於每一組測試資料請輸出"Case #"，
以及那些不成對的襪子。
對於那些襪子，
請分行並按照襪子型號的字典序(由小到大)再來是襪子的尺寸(由小到大)輸出。

如果所有襪子都成對請輸出單行 "Socks fine"。

詳情請見Sample input/output



Hint: O(nlgn)會TLE

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在心跳加速空間裡，有很多個勇者，每個勇者都能夠召喚數量不等的守護騎
士。而這些勇者因為打敗大邪神油膩膩及妖神頌五力而被國王阿拉拉可拉拉
優酪乳三世給予不同的等級，分別為等級1到等級N ，每個等級都會有一個
勇者。

不同的勇者之間會互相的溝通，當等級 i 的勇者要和等級 j 勇者溝通的時
候，若存在一個等級 k 的勇者， 介於 i, j 之間，且這個等級 k 勇者擁有比
等級 i 的勇者或等級 j 的勇者的守護騎士多的時候，這個等級 k 的勇者就會
去阻止他們的溝通。
給定各個等級勇者的守護騎士數量。請問能夠互相溝通的配對 共有幾
組。

選自NPSC2009

Input

輸入檔第一行有一個數字表示測資有幾組。
之後每組測資有 2 行，第一行有一個整數 N 代表勇者的
等級為 1~N，第二行有 N 個數字，第 i 個數字 Ai 代表等級 i 的勇者所擁有的
守護騎士的數量。
1<=N<=10⁶
0<=Ai<=2³¹-1

測資較大請使用scanf instead of cin

Output

每組測資輸出一行表示能夠互相溝通的勇者配對共有幾組。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

蛋糕這學期開了一門神奇的課程，評分方式完全看個人運氣(噢終於不用寫code了!)。蛋糕準備了一疊N張上面標有整數的紙牌，編號1~N，每個人可以任意挑選兩個數字A和B(A<=B)，第A張牌到第B張牌的總和(包含A和B)就是你的得分。可是蛋糕如果直接把這個成績交給學校，他一定會被解聘QQ所以他想出了一個評分方式:大家排隊依序選好A和B之後，如果你的得分比K個以上(含)在你後面選牌的人大，那你就可以得A+，否則將會被當掉。

可能你是一個運氣很背猜拳從來沒贏過的人，在這種評分方式下有99.99999%的機率會被當;可能你是排在隊伍最後的人，不管得到多高的分數，100%會被當；可能蛋糕非常陰險讓所有人分數都一樣，這樣全班都會被當。

蛋糕很好心的想拯救大家，所以他給你們一個機會。如果你能寫出一個程式快速地告訴他全班有幾個人能夠得到A+，雖然他還是不會讓你過，但他會願意幫你簽二退單。

唉，終究還是得寫code。

Input

有多組測資，每組測資第一列為三個正整數N, Q, K。N代表牌的數量，接下來N個整數代表第1張牌到第N張牌上面的點數。
接著會有Q列，每列有兩個數字A,B，分別代表第1個學生到第Q個學生選的數字。

1<=N<=1000000
1<=Q<=1000000
1<=K<=Q
1<=A<=B<=N
-100<=牌的點數<=100

Output

針對每組測資輸出一個整數，代表可以得到A+的人數。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

「鹿茸是鹿耳裡的毛。」

經過媒體的宣傳之後，鹿茸的價格不斷水漲船高。
價格也飆升到難以置信的地步。

一支鹿的價值衡量是由鹿的耳朵裡有幾根毛來決定的。
由於品質控管好到一毛不差的地步。
如果一支鹿的耳朵裡有k根毛，
另外一個耳朵裡也一定會是剛好k根毛，
那麼那頭鹿的價值將會是2*k^k。

許多農場主人紛紛開始擔心自己所獲得的利益會多到難以計算，於是來找你幫忙。
儘管你很不願意，但身為一個善良的工程師，還是幫幫憂心忡忡的農場主人們吧。

Input

輸入的第一行有一個整數 t (0 < t <= 10) 代表以下有多少組測試資料。
每組測試資料的第一行有一個整數 n (0 < n <= 1000)，代表農場總共有幾頭鹿。
接下來的一行，包含 n 個以空白分隔的正整數 q_i (0 < q_i < 2147483647)，分別代表每頭鹿的品質(一個耳朵裡有幾根毛)。

Output

對於每一組測試資料請輸出"Case #"，
以及農場所能產出的價值和，即所有鹿的價值總和。

由於答案可能很大，所以你只要算出答案除以 100000007 的餘數即可。

詳情請見Sample input/output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

其實YLC是一個魔女，昨天她收到秘密任務，
前往異世界消滅怪物。
在異世界的路途上，YLC會遇到許多怪物，
而怪物必須藉由消耗一顆魔法石產生的魔法來消滅。
但由於YLC的口袋很小，只能攜帶一定顆數的石頭，
所以無法一次攜帶大量魔法石消滅全部的怪物。
好在她的夥伴蛋糕及紅線，
每隔一段時間就會傳送一顆魔法石，
而這時候YLC就可以決定是否要拿走那顆魔法石。
由於每顆魔法石的重量都不一樣，
且YLC的口袋只能容納一些魔法石
所以她的策略如下：
1. 收到蛋糕和紅線傳來魔法石時
    A. 口袋還有空間，直接帶上收到的魔法石
    B. 口袋沒空間時，如果口袋中最重的魔法石比收到的重，
         那麼就把最重的那顆丟掉，換成收到的魔法石
         (由於YLC很懶，所以如果口袋中最重的魔法石和收到的等重，
         那麼她會選擇無視收到的魔法石以省事)
2. 遭遇怪物時
    A. 口袋中還有石頭時，就用掉最重的石頭來消滅怪物。
    B. 沒有石頭時，就逃跑略過這隻怪物。
現在，按照時間順序告訴你YLC遇到的怪物及收到的魔法石順序，
並輸出詳細的過程。

Input

第一行有一個正整數T，代表測資的數目。
每組測資有三行。
第一行有三個正整數B,C,N，分別代表YLC最多可以帶著的魔法石顆數、
一開始YLC攜帶的石頭數量、沿路上發生的事件總數量。
第二行有C個正整數，每個整數代表一開始YLC口袋中石頭的重量。
第三行有N個的整數，按照順序代表遭遇的事件，
如果數字是正的，就代表是蛋糕和紅線傳來的魔法石。
如果數字是0，代表YLC遇到了怪物。

1<=C<=B<=100000
0<=N<=500000
0<=N_i<=100000

Output

對於每組測資，先輸出一行"Case #x:"，x代表第幾組測資。
之後請輸出N行，每一行輸出第N_i個事件發生時，YLC做了甚麼事。
若YLC收到魔法石並且直接拿走時，輸出"Take y"，
若YLC丟棄口袋中的魔法石與收到的魔法石做交換時，輸出"Throw z, take y"，
若YLC選擇不將收到的魔法石帶上，輸出"Ignore y"。
若YLC遇到怪物，而身上有魔法石時，輸出"Use y to defeat monster"，
若YLC遇到怪物，而身上沒有魔法石時，輸出"No stones, YLC flees"
其中y代表收到的魔法石的重量，z代表丟棄的魔法石的重量。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

蛋糕最近非常愛玩2048這個遊戲。
這個遊戲的目標是藉由按下鍵盤上的上下左右鍵，
來移動畫面中4x4棋盤的方塊組合出2048。
現在，他給你4x4棋盤中每個方塊的數字，
請你寫一個模擬器，告訴他按下了某個方向鍵後，
棋盤會變成甚麼樣子。

而移動時，每個方塊中的數字會一直沿著輸入的方向移動，
直到不能再移動為止。(見圖1-1,1-2)

而當兩個相同的數字碰觸時，
那麼他們就會合併並且相加。
(見圖2-1中的64及32經過操作後合併為2-2中的128及64)

而一些特殊狀況的規則說明如下，
1.如果有三個相同數字被擠到同一個邊上時，
則只有最靠邊的兩個數字會合併。(見圖3-1中的16)

2.如果有四個相同的數字被擠到同一個邊上，
那麼他們會分為兩組分別合併。(見圖4-1中的2)

Input

第一行會有一個正整數T，代表測資的數量。
每組測資有5行，前4行中每一行會有4個數字，
用來表示棋盤目前的情況。
數字只會有0,2,4,8,16,32,64,128,256,512,1024這11種。
其中0代表該格子是空的(即沒有數字佔據該格)
第5行則有'v','<','^','>'其中一個符號，表示蛋糕按下了哪一個方向鍵。
(v,<,^,>分別代表下,左,上,右)

Output

對於每一組測資輸出18行。
第一行輸出"Case #x:"，x代表測資數量。
之後請按照sample output的格式輸出數字。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你N個正整數, x[1]~x[N], 你可以做以下操作
操作 : 選出一組(x[i],x[j]) {i != j && x[i]>x[j]}, 然後令x[i] = x[i]-x[j];
目標 : 使最後的總合x[1]+x[2]+…x[N]越小越好!
操作的次數沒有限制!
Sorce : codeforces #228

Input

輸入有多筆測資.
每筆測資第一行為正整數N (1<=N<=1000)
接下來一行則會有N個正整數, 分別代表x[1]…x[N](1<=x[i]<=1000)

Output

每筆測資輸出一行一個數字 : 最小可能的總和.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一張圖以及一面鏡子, 你能輸出鏡中的影像嗎?
鏡子會用*表示, 並且保證鏡子一定是垂直放置的!

Ex1 :
輸入一張圖片以及鏡子 :
2222 *
   2 *
   2 *
2222 *
2    *
2    *
2222 *

輸出相對應的倒影 :

2222 * 2222
   2 * 2
   2 * 2
2222 * 2222
2    *    2
2    *    2
2222 * 2222


Ex2 :
輸入 :
1234 *
     *
5678 *

輸出 :
1234 * 4321
     *
5678 * 8765

Input

輸入有多筆測資, 每筆測資間用換行隔開.
每筆測資的字串長度最多100, 並且不會超過100行.
影像只會包含以下字元 : [a-z,A-Z,0-9,space]
因此*字元只會出現在鏡子上!

Output

輸出時, 測資間也請用換行隔開.
並請不要輸出結尾空白!!!
Ex : (空白用_代替)
輸入 :
_2__*
_2__*

輸出 : (正確)
_2__*__2
_2__*__2

輸出 : (錯誤)
_2__*__2_
_2__*__2_

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

一群螞蟻走在一條長度為 L 公分的繩子上，每隻螞蟻的速度為 1 cm/sec。當一隻螞蟻走到繩子的盡頭時，它馬上掉下繩子（再也爬不起來了）。當兩隻螞蟻在繩子上相遇時，馬上掉頭往另一個方向走去。我們知道每隻螞蟻在繩子上的位置，但不幸的是，我們並不知道每隻螞蟻開始時走的方向。

你的任務是算出最快和最慢可能需要多少時間，所有的螞蟻都掉出繩子外。

Input

輸入的第一列有一個整數，代表以下有多少組測試資料。
每組測試資料以2個整數 L, n 開始，L 代表繩子的長度（單位：cm），n 代表一開始時繩子上有多少隻螞蟻。接下來有 n 個整數代表這些螞蟻一開始在繩子上的位置（從繩子的左端算起），且這些位置並沒有一定順序。所有的這些數都不會超過 10000。

請參考Sample Input。

Output

對每組測試資料輸出一列，包含2個整數代表最快和最慢可能需要多少時間（秒），所有的螞蟻都掉出繩子外。

Sample Input  Download

Sample Output  Download