Description
Alex has a puzzle her father gave her last Christmas. It has nine numbered squares arranged in a 3×3 matrix (three rows and three columns) and it's mechanically designed to allow the following types of movements:
- A horizontal right move shifts one position to the right each of the squares in the corresponding horizontal row (circularly).
- A vertical up move shifts one position upwards each of the squares in the corresponding vertical column (circularly).
Alex's troublemaker little brother Jim snuck last night into his sister's bedroom and somehow tore the puzzle apart and put it back together. However, when Jim assembled the puzzle back, he might have done it in a configuration different from the original configuration of the puzzle.
The next morning, when Alex found her puzzle had been scrambled, she called you to help her to reset her puzzle to its original configuration (shown below) as quickly as possible, so her father won't realize that the puzzle was torn and scrambled. Of course, you should do it using only valid movements, as above described.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Your task is to write a program that, given a configuration, finds a way to set the puzzle to its original configuration spending the minimum possible number of moves to accomplish it, if the given puzzle is solvable. If this is not the case, the program should point it out.
Input
The problem input consists of several cases, each one defined by three lines that describe a puzzle configuration. That is, lines correspond to a top-down description of the rows of the given configuration, and each line consist of three digits, separated by one blank character.
The end of the input is indicated by a line with a number 0.
Output
For each puzzle in the input, you must print a line containing S , the minimum number of moves required to set the puzzle to its original configuration, followed by a space and 2*S characters indicating any sequence of S moves that solves the puzzle.
A move is described by two characters: the first one must be H or V (H specifies a horizontal move, and V a vertical move), and the second one must be 1, 2, or 3 to indicate the row or the column to move.
If the puzzle is not solvable, you must output a line with the text ``Not solvable''.
Hint: Consider each state as a node of the graph, transistion is an edge of graph.
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
費曼 (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
世界聞名的黑社會老大Vito Deadstone要搬到紐約來了。在那裡他有一個大家族，並且他們都住在Lamafia大道上。因為Vito時常要拜訪所有的親戚，他想要找一間離他們最近的房子，也就是說他希望從他的家到所有的親戚的家的距離的和為最小。
他恐嚇你寫一個程式來幫助幫助他解決這個問題。
Input
輸入的第一列有一個整數代表以下有多少組測試資料。
每組測試資料一列，第一個整數 r（0 < r < 500），代表他親戚的數目。接下來的r個整數s1,s2,......sr為這些親戚房子的門牌號碼（0 < si <30000）。注意：有些親戚的門牌號碼會相同。
Output
對每一組測試資料，輸出從他的新家到所有的親戚的家的距離的和為最小為多少。2個門牌號碼si、sj的距離為si-sj的絕對值。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
要計算一個圓的圓週長似乎是相當簡單的事，如果你知道直徑的話。但是如果你不知道直徑呢？
給你不共線的三個點的座標，你的任務是算出通過這三個點的唯一圓的週長是多少。
Input
每組測試資料一列，含有6個實數x1,y1,x2,y2,x3,y3，分別代表三個點的座標（此三個點不共線）。通過這三個點的唯一圓的直徑不會超過1百萬。
Output
對每一組測試資料，輸出通過這三個點的唯一圓的週長是多少，請輸出到小數點後2位。
圓週率PI的值大約是 3.141592653589793
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在很多電腦問題中，常常會把一個陣列的資料做一些搬動。也就是說陣列中的資料被重新排列。有一個排列陣列資料的方法是用另一個稱為索引陣列（index array）來完成的。假設x是要被重新排列的陣列，而x'是重新排列後的陣列，那麼應該有一個關係存在於x和x'之間，使得x'i=xpi，而索引陣列就是記載這個關係用的。
為了避免誤解題意，以第一組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
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
為了呼應台灣電腦彩券的發行，我們特別推出跟組合有關的題目。以台灣的彩券來說，從46個球中取出6個，共有C(46,6)=9366819種組合。（中特獎的機率：1/936681989，夠低了吧！）給你：
5 <= N <=100, and 5 <= M <=100, and M <= N
我們可以根據下面的公示算出從N個東西中取出M個東西的組合數：
你可以假設你的答案C不會超出 long int 的範圍。
Input
每筆測試資料一行，有2個正整數 N,M。 N=0，M=0代表輸入結束。
Output
以下列的格式輸出：
N things taken M at a time is C exactly.
請參考Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
.gif){kind=small}
Description
令b0, b1, b2, ......, bn為一整數序列，其中b0大於等於0，其他數皆大於0。我們定義n階層的連續分數為：
以簡寫 [b0; b1, b2, ......, bn]來表示。舉例說明：對n=3的連續分數的簡寫 [2;3,1,4] 表示以下的式子：
寫一個程式讀入最後的分數的分子及分母，輸出此連續分數的簡寫。為了確保唯一性，bn > 1。
Input
每組測試資料一列，有2個整數a,b，分別代表分數的分子及分母（a,b > 0）。
Output
對每組測試資料，請輸出對應的連續分數的簡寫。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在19世紀末,德國數學家 George Cantor 爭論說正分數Q+的集合和正整數N的集合相等, 指他們都是無限,而且一樣大. 為了證明這事實,他找出存在於N到 Q+間的對映關係.這對映是要利用一個 N x N 平面的遊走去證實:
Cantor 對映如下(PS: 1對映1/1,2對映2/1,3對映1/2.....如圖):
問題
寫出一個程式找出第 i 個Cantor fraction如上面的對映關係.
Input
這輸入由許多行正整數所組成.
Output
輸出由每一行輸入所產生,它表示第 i 個分數,以著分子和分母由(/)做分割.這分數不用被化簡到最簡形式.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
你認為email的PGP加密法不夠安全，所以你決定在你的信件以PGP加密前先把明文轉為Pig Latin以加強安全性。
Input
你必須寫支可以讀入任意行的文字並以Pig Latin的文法輸出的程式。文字的每一行包含一或更多個單字。一個單字的定義是一系列連續的``字母"（大寫 或/和 小寫）。單字必須以下列規則轉換為Pig Latin（沒有任何單字會以它們在input中的樣子輸出）：
1.以母音（大小寫的a,e,i,o,u）為首的單字必須在它們後面加上字串``ay"（不含引號）。例如：``apple"變成``appleay"。
2.以子音（除了大小寫的a,e,i,o,u外的所有字母）為首的單字必須先把第一個字母移到最後面，然後在單字後頭也加上字串``ay"。例如：``hello"變成``ellohay"。
3.不可以改變字母的大小寫。
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Hangman Judge是一個猜英文單字的小遊戲（在電子字典中常會看到），遊戲規則如下：
答案單字寫在紙上（每個字元一張紙），並且被蓋起來，玩家每次猜一個英文字元（letter）。
如果這個英文字元猜中（在答案的英文單字中有出現），被猜中的字元就被翻開。例如：答案是book，如果你猜o，book中的兩個o就會被視為已猜中。
如果這個英文字元未出現在答案的單字中，就會在hangman的圖中多加一劃。要完成hangman圖共需7劃，如下圖。注意：同一個猜錯的字元只能再圖上畫一劃，例如：答案是book，第一次你猜a（未猜中）會在圖上畫一劃，但第二次以後再猜a並不會再多畫。
如果在hangman圖完成之前，玩家已猜中所有答案中的字元，則玩家贏（win）。
如果玩家尚未猜中所有答案中的字元而hangman圖完成了，，則玩家輸（lose）。
如果玩家在還沒輸贏的情況之下就不玩了，那我們說玩家膽小放棄了（chicken out）.
┬─┬─ │ Ｏ │／│＼ │ │ │ ／＼ ┌┴┐ │ └─┬ └───┘
你的任務就是要寫一個程式根據答案及玩家輸入的猜測來判斷玩家是贏、輸、或放棄。
Input
會有好幾組測試資料，每一組有3列。第一列為一個數字n，代表第幾回合，第二列為這一回合的答案，第三列為這一回合玩家輸入的猜測。如果 n = -1代表輸入結束。
Output
請輸出每一回合及遊戲結果。遊戲結果只有三種可能：
You win.
You lose.
You chickened out.
請參考sample output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
本題請你將 (a+b)k 乘開，寫出等式：
(a+b)k = x1ak + x2ak−1b + x3ak−2b2 + … + xk+1bk
其中 x1 … xk+1 為二項式係數，即 xi = Cki .
Input
輸入 資料的第一列為一整數T(T <= 100)表示測試資料的組數。每組資料一列，其格式為(a+b)^k，其中 a 與 b 為變數名稱，變數名稱以'a' ~ 'z'的小寫字母所組成，且 k (1 <= k <= 50)為其次方。每列的長度不會起過100個字元。
Output
請每組資料輸出格式"Case N: T"，其中N表示測試資料編號(由1開始)，T表示乘開的式子。你不應該輸出係數或指數上多餘的1。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
摩斯電碼是一種不需使用慣用符號即可做長距離訊息傳送的工具。一組電碼由簡單的長音及短音信號聲所構成。其中短信號聲稱作dih，而長信號聲稱作dah。舉例來說，字母O的電碼即為dah dah dah（三長信號聲）。實際上，由於 電碼的設計上在兩個信號之間並沒有任何信號加以間隔，因此又有第三個符號，也就是靜音。電碼中兩個字母之間以一單靜音隔開，兩個單字之間則以一雙靜音隔開。
你現在被指派一個翻譯摩斯電碼的工作。關於信號已經被轉換成下面的方式：dih以一個點（.）來代替，dah以一個破折號（-）來代替，單靜音與雙靜音則分別由一個空格和二個空格來代替。
下表為摩斯電碼在題目中可能出現的字元，你的程式必須要能夠處裡這些字元。
| Symbol | Code | Symbol | Code | Symbol | Code | Symbol | Code | Symbol | Code | Symbol | Code |
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | .- | J | .- - - | S | ... | 1 | .- - - - | . | .-.-.- | : | - - -... |
| B | -... | K | -.- | T | - | 2 | ..- - - | , | - -..- - | ; | -.-.-. |
| C | -.-. | L | .-.. | U | ..- | 3 | ...- - | ? | ..- -.. | = | -...- |
| D | -.. | M | - - | V | ...- | 4 | ....- | ' | .- - - -. | + | .-.-. |
| E | . | N | -. | W | .- - | 5 | ..... | ! | -.-.- - | - | -....- |
| F | ..-. | O | - - - | X | -..- | 6 | -.... | / | -..-. | _ | ..- -.- |
| G | - -. | P | .- -. | Y | -.- - | 7 | - -... | ( | -.- -. | " | .-..-. |
| H | .... | Q | - -.- | Z | - -.. | 8 | - - -.. | ) | -.- -.- | @ | .- -.-. |
| I | .. | R | .-. | 0 | - - - - - | 9 | - - - -. | & | .-... |
Input
輸入的第一列有一個整數T(1 ≤ T ≤ 10)，代表有幾組測試資料。
接下來每組測試資料由一連串的點、破折號、空格所組成。每組資料的最大長度不超過2000。
Output
對每組測試資料輸出一段文字。首先輸出一列這是第幾組測試資料，緊接著一列輸出已經解碼的句子。
每組測試資料間請以一空白行隔開。句子一律以大寫字母印出。
請參考Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
對於不含數字的文章有一種簡單的壓縮法，方法是用一個串列（list）來記錄曾經出現過的字（word）。壓縮的過程如下：如果遇到非英文字母的字 元，該字元直接複製到壓縮後的檔案。當遇到一個字時，如果這一個字是第一次出現，除了把這個字複製到壓縮後的檔案之外，並把他加到串列的開頭。如果這一個 字不是第一次出現，則這個字不會複製到壓縮後的檔案，而是把這個字在串列中的位置複製到壓縮後的檔案，並且在串列中把這個字移到串列的開頭。串列的開頭位 置為1。
現在你的任務是給你一篇用上述方法壓縮後的文章，請你把他還原回來。你可以假設所有的字都不會超過50個字元，並且未壓縮的文章不含有數字。另外，字的定義為：最長的連續的英文字母（A~Z, a~z）。例如：
- x-ray 包含了2個字：x 和 ray
- Mary's 包含了2個字：Mary 和 s
- It's a winner包含了4個字：It、s、a 和 winner
並且字有分大小寫，因此abc 和Abc是不同的2個字。在本問題中，不同的字的數目並無上限。
Input
只有一組測試資料。內容為多列壓縮後的文章。最後一列僅含有一個0，代表輸入結束（此列無輸出）。請參考Sample Input。
Output
對於輸入的每一列，輸出解壓縮後的文章。請參考Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Queues 與 Priority Queues 是大家都知道的資料結構，然而 Team Queue卻不是這麼廣為人知，但是他在日常生活中卻常常出現，像是午餐時段排在 Mensa前面的人群就是一個Team Queue
在一個Team Queue中每個元素都屬於一個隊伍，如果一個元素要進入Team Queue時，他會先從頭到尾搜索Team Queue，如果看到他的隊友已經在裡面了，那他就會排到他的隊友後面(插隊)；如果沒有隊友在裡面，他就會排到Team Queue最後面，並成為隊伍的最後一個元素(運氣差)。把元素從Team Queue拿出來時就像普通的Queue一樣，會照順序從Team Queue的最前面到最後面
你的任務就是模擬這個Team Queue
Input
輸入將包含多組測資，每組測資第一個數字是team的數量t(1<=t<=1000)
接下來T行就是這些Team，每行最前面的數字是這個Team的人數，接下來就是這個Team的成員
Team的成員範圍0-999999，一個Team最多有1000個成員
最後，接下來會有一些指令，下面是三種指令
ENQUEUE x - 將元素x丟進Team Queue
DEQUEUE - 將Team Queue 最前面的元素移除掉並且印出來
STOP - 結束這組測資
警告：測試資料可能多達20萬筆，所以要更有效率的去處理你的程式。
ENQUEUE與DEQUQUE照理說只需要常數時間
Input結尾會有個0
Output
對於每組測資，首先先印出"Scenario #k"，其中k是測試用的數量。然後，每個DEQUEUE指令都要印出你移除掉的元素。
在每組測資後面(包括最後一組)都要多印一個空白行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在上次的課程上，我們學會了在O(lg P)的時間內算出BP
的方法。
但是，如果B不是一個數字，而是一個矩陣呢？還記得費式數列嗎？
Fn = Fn-1 + Fn-2 , for n > 1
F1 = 1
F0 = 0
其實費式數列可以轉乘矩陣相乘的形式，[Fn ;Fn-1 ] = [1,1;1,0]*[Fn-1 ;Fn-2 ]
我們將[Fn-1 ;Fn-2 ]再次拆開，可得到：[Fn ;Fn-1 ] = [1,1;1,0;]∗ ([1,1;1,0] [Fn-2 ;Fn-3 ]) = [1,1;1,0]2*[Fn-2 ;Fn-3 ]
所以，[Fn ;Fn-1 ] = [1,1;1,0]n−1*[F1 ;F0]
設B = [1,1;1,0] , P = n − 1，則問題轉化為Big Mod。
現在給予數字n 及M,求Fn % 2M
Input
每行有兩個數字n, M。(n ≤ 2147483647, M ≤ 20)
Output
每行有一個數字，代表Fn % 2M
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在PB 上，我們學會了將費式數列轉化成矩陣相乘的形式。其實，我們可以將此
技巧轉成更general 的形式。
Fn = c1* Fn−1+c2 Fn−2+ ⋯ +ck Fn−k+ck+1 , for n ≥ k
其中已知的項是：
F0 , F1 , F2 , … , Fk−1 , c1 ,c2 , … , ck+1
矩陣相乘的形式會表示成：
[ Fn; Fn−1;.... Fn−k;ck+1] = [B]*[ Fn-1; Fn−2;.... Fn−k-1;ck+1]
請試著推導出B 矩陣，使得你可以用Big Mod 的方式求 Fn %M
Input
輸入第一行表示有幾組測試資料，最多20 組。
每組測資：
第一行有3 個數字：k(0 ≤ k ≤ 25), m(1 ≤ m < 231), n(0 ≤ n < 231)
第二行有c1 , c2 , … , ck+1(−231≤ ci < 231)
第三行有 F0 , F1 , … , Fk−1(−231≤ Fi < 231)
Output
每行有一個數字，代表 Fn %M
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在一個叫「堆疊市」的城市中有一個有名的火車站。由於地形限制以及經費的關係，火車站及唯一的鐵路的樣子如下圖：
現在火車從A方向來，預定從B方向離開。火車共有N節車廂（N <=1000），並且各車廂依次以1到N來編號。你可以假設各車廂在進站之前可以單獨與其他車廂分離，也可以單獨離開車站到往B方向的鐵軌上。你也可以假設在任何時間火車站都可以容納所有的車廂。但是一旦一節車廂進站後，就不能再回到A方向的鐵軌上了，並且一旦離開車站往B方向後，也不能再回到車站。
現在你的任務是寫一個程式，判斷火車能否以一特定的排列方式在B方向的鐵軌上。
Input
輸入含有多組測試資料。每組測試資料的第一列，有1個整數N，其意義如上所述。對於此組測試資料接下來有0到多個不等的測試，每個測試一列，每列有N個整數，內容為1,2,......,N的任意排列。當遇到僅含有一個0的一列，代表該組測試資料結束。
N=0代表輸入結束，請參考Sample Input。
Output
對每一組測試資料的每個測試，輸出該1,2,......,N的任意排列是否可能。如果可能，請輸出Yes，若不可能則輸出No。
每組測試資料後亦請空一列。請參考Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在 Hedonia 島上的官方語言是 Hedonian 語。有位 Hedonian 語言學教授發現她的許多學生並未弄明白 Hedonian 語的語法規則。她實在是厭煩了訂正學生的語法錯誤，所以她決定要她的學生們寫個程式，能夠檢查出他們寫的句子中的語法錯誤。就跟 Hedonian 人的天性一樣，Hedonian 語的文法規則也相當單純，規則如下：
0.這個語言中僅有 p 到 z，還有 N，C，D，E，I 這幾個字母。
1.從 p 到 z 中，任何一個字母都是一個正確的句子。
2.如果 s 是一個正確的句子，那麼 Ns 也是。
3.如果 s 及 t 都是正確的句子，那麼 Cst, Dst, Est 還有 Ist 也都是正確的句子。
4.0. 到 3. 是檢查一個句子是否合乎語法僅有的規則。
你被要求寫程式檢查一個句子是否滿足上述的規則 0. 到 4.。
Input
輸入中含有許多句子，每個句子一列，都只含有 p 到 z 還有 N, C, D, E, I這幾個字母。你可以假設每個句子至多有 256 個字母，至少 1 個字母。
Output
對於一個格式正確的句子輸出 YES，對於一個錯誤的句子則輸出 NO。
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
你陷入一個 3D 城堡的迷宮中， 需要找到一條快速的路逃出去！ 這個城堡由空的或填滿石頭的立方體組成, 向東、西、南、北以及上、下移動一個單位個需要一分鐘。 你不能斜的移動， 並且迷宮最外層的每一面都包含著堅固的石牆。可能逃的出去嗎? 如果可能的話，最少需要花多少時間呢？
Input
輸入含有多組測試資料，每組測試資料的第一列有3個正整數L、R、C（均介於1到30之間）。
L 表示迷宮有幾層
R 和 C 表示每層有幾列幾行
之後共有L個區塊（每個區塊代表一層），每個區塊含有 R 列，每列有 C 個字元。 每個字元表示迷宮的一個單位。 '#'表示這個單位充滿石頭， 而 '.' 表示這是個空的空間。你的起始位置在標明 'S' 的地方, 出口在 'E' 之處. 在一層描述完後有一列空白區隔。 若L=R=C=0 代表輸入結束，請參考Sample Input。
Output
每個迷宮有一列的輸出。 如果可以達到出口的話， 請輸出：Escaped in x minute(s).其中的 x 表示最短離開時間。如果沒有辦法逃出去請輸出：Trapped!
Sample Input Download
Sample Output Download
Tags
Discuss
Description
一般來說在編碼（Encoding）的技術常常用在加密，或是要有較節省的通訊與儲存空間的時候。在此，我們發展了一套簡單的編碼的方法，這方法可以把不大於5個字元（都是小寫字母）的特殊字都指定一個唯一的整數。
在這裡所謂的特殊字是指在這個字裡面，下一個字元一定比上一個來的大。例如：k、is、abc、aepx、gwxyz都是合法的。而aab、are、cat則不是。
對每一個合法的字我們根據字的長度與字元的順序給他一個整數編號。也就是：
a -> 1
b -> 2
.
.
z -> 26
ab -> 27
ac -> 28
.
.
az -> 51
bc -> 52
.
.
vwxyz -> 83681
你的任務就是要做這樣的編碼。
Input
每筆測試資料一列。每列有1個字（1到5個小寫字母）。
Output
對每一測試資料，如果這個字不是合法的，請輸出0。否則請輸出該字的編號。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
你的一個朋友正在做一個關於西洋棋中騎士旅行問題（Traveling Knight Problem）的研究，他希望你幫他解決一個問題：就是給你2個格子的位置X及Y，請你找出騎士從X走到Y最少需要走幾步。
Input
每筆測試資料一列。每列有2個西洋棋的座標位置。每個位置座標是由一個英文字母（a-h，代表棋盤的第幾欄）及一個數字（1-8，代表棋盤的第幾列）組成。
Output
對每一列輸入，請輸出 "To get from xx to yy takes n knight moves.".
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
雖然 Rujia Liu 通常出很難的題目，他偶而也會出一些簡單的題目來鼓勵大家解題。
給你一個陣列，你必需回答在此陣列中某一特定的數值 v 重複出現第 k 次時的位置(在此陣列中的位置，以1開始)。為了讓問題難一些（並且有趣一些），你必須回答m個這樣的詢問。
Input
輸入會有許多組測試資料，每組資料的第一列有兩個整數n, m (1 <= n, m <= 100,000)，n 表示陣列的長度，接下會有 n 個小於1,000,000的正整數。再接下來有 m 列，每列為一組 k v 值(1 <= k <= n, 1<= v <= 1,000,000)，請回答每一組數值 v 出現第 k 次在陣列中的位置。
Output
請依要求輸出序號(以1為第一個)，如果不存在請輸出 0。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在一個字串中，「未排序」的程度是以各字元間彼此的大小關係來計算的。例如在字串 DAABEC中，「未排序」的程度為 5，因為D比它右邊的4個字元大，E比它右邊的1個字元大。而字串AACEDGG「未排序」的程度為 1（幾乎是快排序好的，唯一的未排序發生在E和D之間），字串ZYXW「未排序」的程度為 6（剛好是完全排序的相反）。
現在你的任務是為許多的DNA字串來做排序。每個字串中僅含有A,C,G和T這4種字元。排序的原則是根據各字串「未排序」的程度，由小到大輸出。在這裡每個字串的長度均相同。
Input
輸入的第一列有一個整數代表以下有幾組測試資料。每組測試資料的第一列含有2個正整數 n（0 < n <= 50）和 m（0 < m <= 100），n 代表字串的長度，m 代表字串的數目。接下來的 m 列，每列有一個長度為 n 的字串。
第一列及第一組測試資料，以及各組測試資料間均有一空白列。請參考Sample Input。
Output
對每組測試資料按照「未排序」的程度，由小到大輸出各字串。假如有不只2個字串「未排序」的程度相同，則按照它們在輸入中的順序輸出。
各組測試資料之間請輸出一空白列，輸出格式請參考Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
如果一個數字從左往右讀和從右往左讀都是一樣，那麼這個數字就叫做“回文數”。例如，12321就是一個回文數，而77778就不是。當然，回文數的首和尾都應是非零的，因此0220就不是回文數。 有多組測資，每組測資有用空格隔開的兩個數N和S。 N行, 每行一個滿足上述要求的數，並按從小到大的順序輸出。
事實上，有一些數（如21），在十進制時不是回文數，但在其它進制（如二進制時為10101）時就是回文數。
寫一個程式，讀入兩個十進制數N(1≤N≤15),S(0 <
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
搗蛋為了讓競技程式基礎班的同學有個地方可以討論題目，寫了一個CPTBook讓大家上去討論以及閒聊；CPTBook除了討論，還可以加入好友，讓好友之間可以開聊天室一起討論。為了增進大家感情，他寫了一個介紹朋友的功能，為了確定兩人之間關係是否密切，需要看看他們需要經過幾個朋友牽線才行。請問你是否可以幫搗蛋寫個程式去檢查兩人之間需要經過幾個朋友連線?
Input
有多組測資，每組測資第一行是N(N<1001)代表這組測資會出現幾個人，M(M<10000)代表這組測資有幾組連線，以及q(q<20)代表接下來有幾個問題。接下來M行，每行有兩個字串S_1,S_2 (0<|S_1 |,|S_2 |<20)代表兩個人的名字，且這兩個互為朋友，S_1,S_2皆為小寫英文字母且中間不會有空白，只要是同名字就視為同個人。接下來q行，每行有兩個字串S_1,S_2 (0<|S_1 |,|S_2 |<20)代表兩個人的名字，然後要詢問這兩個人之間需要經過多少朋友連線
Output
對於每個問題輸出這兩個人需要經過多少朋友才行連線(兩人的朋友沒交集請輸出-1,兩人如果互相是朋友請輸出0(自己也會是自己的朋友)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
假如在一個數列中，a的順序在b的前面，但是a比b還大，那我們就稱(a, b)為逆序數對(Inversion Pair)。只要我們計算一個數列Inversion Pair的數量，就可以知道這數列最少需要幾次左右互換才能夠排序好。現在給你數列，請算出Inversion Pair數量。
Input
多組測資。
每組測資有一行，每一行中有多個整數(int範圍)表示一個數列。
相鄰兩個整數以一個空白隔開，每一行整數最多有1000個。
Output
對於每組測資請輸出Inversion Pair的數量
Sample Input Download
Sample Output Download
Tags
Discuss
Description
競技程式期中考考完了，Alan想要把score board整理成同學的成績表。不過他筆電的excel壞了，讓他沒辦法將成績依照學號排好，你可以幫他排一下嗎?
Input
多組測資，每組測資第一行有個整數n(n<100000)表示參加考試的人數，接下來n行有一個字串表示同學的Team(字串長度<15),以及非負整數表示解題數(解題數<20)，以及數字表示學號(學號最多9位，不會有0開頭的學號,學號不會重複且皆為正整數)
Output
對於每組資料請按照學號由小到大輸出 學號,隊伍名,解題數，中間請以一個空白隔開，每組資料後請多一個換行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
術語介紹：若有一算式a+b，則a跟b是運算元，+是運算子。
數學上，最常見的算式就是四則運算式，如：(1+5)*8/2、3*7/9*4等。此次我們要學習如何處理四則運算式。四則運算表示式是中序(infix)表示式，要先經過神祕的轉換，轉成後序(postfix)表示式，才好處理。上述範例的後序表示式為
15+8*2/、37*9/4*
當有後序表示式後，我們可以快速算出答案。方法是：使用一個Stack，遇到運算元就Push進去，遇到運算子就Pop最上面的兩個元素，然後作運算子動作，再將結果Push進去。
但由於後序表示式算結果太簡單，故此題我們要考的是如何達成神祕的轉換。其實，神祕的轉換也是用一個Stack來達成的。規則是：
1. 左括號(：要直接進Stack
2. 右括號)：要將Stack連續Pop並輸出，直到Pop一個左括號停止(此右括號不用Push)
3. 運算元：直接輸出
4. 運算子：Stack開始Pop，直到(1)最上方元素的優先權小於目前運算子的優先權，或是(2)Stack為空才停止。然後，將目前的運算子Push進去
優先權：”(“ < “+” = “-“ < “*” = “/”
Input
第一個數字N，表示N組測資。接下來N行，每行表示一組測資。
每行最多1000個字元，其中會出現0-9, (, ), +, -, *, /
運算元為一位數字。
Output
對於每組測資，輸出一行該算式的後序表示式。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
搗蛋玩仙劍五結果深陷在迷宮中，他知道他現在需要先拿到鑰匙，到出口時才有辦法離開。搗蛋八個方位都可以走(上,下,左,右,上左,上右,下左,下右)請問你可以幫搗蛋算算看他從起點到拿到鑰匙到出去最少需要走多少步嗎
Input
有多組測資，每組第一行有兩個數字n(n<1000), m(m<1000)，分別表示迷宮的行與列。接下來n行，每行有m個字元。字元種類有：‘#’代表牆壁、‘.’代表可以走的路、‘S’代表搗蛋的位置、‘K’代表鑰匙的位置、‘E’代表出口的位置。(‘S’,‘K’,‘E’都是可以通過的點，且各都只會出現一次)。
Output
對於每組測資請輸出一行數字，表示搗蛋最少需要走多遠。若無解，請輸出-1。測資間請空一空白行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
我們尋找要尋找一個最好的回文。在尋找回文時不用理睬那些標點符號、空格(但應該保留下來以便做為答案輸出),只用考慮字母'A'-'Z'和'a'-'z'。要你尋找的最長的回文的文章是一個不超過8,000個字元的字串。我們將保證最長的回文不會超過2,000個字元(在除去標點符號、空格之前)。
Input
輸入有多組測資，每組測資結束時，會有單獨一行的[###OVER###]
每組測資不會超過8,000字元。每組測資內可能有一行或多行，但是每行都不超過80個字符(不包括最後的換行符號)。
Output
每組測資輸出的第一行應該包括找到的最長回文的長度。
下一行或幾行應該包括這個回文的原文（沒有除去標點符號、空格），把這個回文輸出到一行或多行（如果回文中包括換行符號）。
如果有多個回文長度都等於最大值，輸出最前面出現的那一個。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
雜湊表(Hash Table)是一個將資料鍵值透過雜湊函數(Hash Function)轉換為資料儲存位置（通常是陣列索引的號碼）。而且可以快速進行資料插入、搜尋以及刪除的資料結構。不過有時候兩個不同的資料經過雜湊函數會產生同樣的數值，這稱為發生碰撞(collision)，碰撞的其中一個解決方法就是用Linked-List把兩個資料串起來。現在給一個雜湊函數: f(key) = key%1001，請你建出一個陣列大小是1001的雜湊表，模擬接下來的動作
Input
一開始雜湊表都是空的，接下來會有多種指令
●Insert n:請將數字n插入雜湊表，產生碰撞時請讓比較晚加入的插在前面。
●Look k:請按照順序印出雜湊表第k個table的所有數字(數字間請留一個空白，最後一個數字後請換行)，如果沒數字請輸出Null。
●Delete n:如果n有在雜湊表裡，請刪除n(如果有多個n請先刪除晚進來的)；若沒有，請印出Error。
●Search n:如果n有在雜湊表裡，請輸出Yes；反之輸出No。
●End:結束輸入
n為int範圍內非負整數，0<=k<1001
Output
對於Look, Delete, Search指令請按照規則輸出
Sample Input Download
Sample Output Download
Tags
Discuss
Description
地球正遭受死亡病毒的攻擊。幸運地，衛生署成功的把病毒的感染侷限在一格一格的區塊裡。接著，公衛專家成功地發現了病毒感染區塊的傳遞規則。在每一天，每個區塊的狀態是取決於與它相鄰的8個區塊的狀態（垂直、水平、對角線）
1. 當一個受感染區塊有2或3個相鄰感染區塊，則此區塊將會維持感染狀態
2. 當一個未感染區塊有正好3個相鄰感染區塊，則此區塊將會成為感染狀態
3. 若非上述兩個案例，則此區塊將會成為未感染狀態
你的任務就是抵抗病毒及恢復所有區塊。衛生署派一台抗毒原形機器人給你操作。這機器的功能總結如下：
1. 每一天的開始，你移動這台機器到相鄰8個區塊的其中1個區塊，但不允許移動到受感染的區域。而且不允許停留在原地。
2. 機器移動完之後，除了機器所在的區塊以外的所有區塊遵照上述傳遞規則進行病毒傳遞
特別的是，機器所在的土地將無視病毒傳遞規則，即使它有正好3個相鄰感染區塊。不幸的是，機器的防毒功能並不會殘餘下來。所以只要機器離開此區塊，此區塊還是有可能會被感染。
以下有一個範例，@是機器，#是病毒。
你的任務是操控機器人移動，在最少天數下，使所有區塊恢復原狀。
Input
有多組測資。Input的最後一行是單一個0。
每組測資的格式是
.png)
n為邊長，整片土地是n*n個區塊組成的。(1<=n<=5)
剩餘的部份是n行，每行有n個字元。
每個字元表示此區塊的最初狀態：’#’代表受感染，’.’代表未感染，’@’代表機器人的初始位置。整張圖只會有一個’@’
Output
對於每組測資，輸出可達成恢復所有區塊的最少天數。
如果找不到一連串的操作可以恢復所有區塊，則輸出-1
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
LISP是最早的高階程式語言之一，而Lists則是LISP中最重要的資料結構。Lists可以很簡單的用來表達其他的資料結構，例如：tree。在這個問題中，給你LISP中的S表示式（S-expression），請你寫一個程式判斷這表示式（整數的二元樹）是否存在一條由根節點到樹葉的路徑，且路徑上各節點的值的和為某一特定的數 n。例如：在以下的樹中共有4條從根到樹葉的路徑。而各路徑的和分別為27,22,26以及18。
在LISP中的S表示式有以下的格式：
empty tree ::= ()
tree ::= empty tree | (integer tree tree)
上圖中的樹若以S表示式表達為：(5 (4 (11 (7 () ()) (2 () ()) ) ()) (8 (13 () ()) (4 () (1 () ()) ) ) )
注意：在樹中所有的葉節點為 (integer () () )
既然空樹不存在任何根到葉的路徑，任何對空樹是否有某個和的詢問，其答案都是否定的。
Input
輸入含有多組測試資料。每組測試資料的開頭有一個整數 n。接下來為一S表示式。所有的S表示式一定是合法的，但是可能會跨多列，並且可能含有空白字元。請參考Sample Input。
Output
對每一組測試資料輸出一列。如果S表示式所表達的樹存在一條由根到葉的路徑，且路徑上節點值的和為n的話，則輸出yes，否則輸出no。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
奇偶易位排序法(Odd-Even Transposition Sort)是⼀種用於平行程式的排序方法。
做法是重複以下兩個動作：
1. 奇數位置與左手邊比較(a[0]&a[1],a[2]&a[3],…)，如果左邊較大則交換
2. 奇數位置與右手邊比較(a[1]&a[2],a[3]&a[4],…)，如果左邊較大則交換
動作1 與動作2 都是平行處理，平行處理即是每⼀對要比較的數對則分配1 顆
CPU 來檢查關係。所以，這n/2個數對可以用n/2個CPU 在O(1)時間內同時完成。
所以我們可以分析最差的情況是：從最左邊的數字需要換到最右邊的位置(或最
右邊換到最左邊)。因為他每次只能換相鄰的兩數，所以需要做n-1 次，綜合起
來它的時間複雜度就是 O(1)*O(n) = O(n)
現在給你⼀些數列，請算算看需要做幾次兩兩交換(動作)才可以完成排序。
◎同⼀次動作不論交換幾次都算⼀次，但是如果沒交換要算零次
Input
多組測資，每組測資有⼀行，第⼀個數字n(n<1000)是數字的數量，接下來會有
n 個整數(整數絕對值<=10000)表示這個數列。
Output
對於每組測資，輸出Odd-Even Transposition Sort 要兩兩交換的次數
Sample Input Download
Sample Output Download
Tags
Discuss
Description
NTHU OJ 第1000 題的題目是 A+B，題目是請大家輸出A+B 的值，這題因為很
簡單，所以有很多人去做。不過Alan 最近在改judge 網頁，不小心把Rank List
的網頁改爛了，所以現在網頁的Rank List 沒有依照程式執行速度排序，你可以
幫Alan 寫個排序，把Rank List 重新改好嗎?
Input
多組測資，每組測資第⼀行有個整數n(n<100000)表示解題人數，接下來n 行每
行代表⼀個解題者的資訊，第⼀個字串是User ID(長度<20 的大小寫英文字母與
數字)，第二個字串是CPU Time(正浮點數，到小數後第三位)。
Output
對於每組測資請依照CPU Time 排序，輸出名次(從1 開始排)、User ID、CPU
Time(輸出到小數點後三位)，中間以空白隔開；如果CPU Time 相同，先出現的要排前面
Sample Input Download
Sample Output Download
Tags
Discuss
Description
術語介紹：若有一算式a+b，則a 跟b 是運算元，+是運算子
我們將算式從中序轉後序之後，就可以利用stack 把答案算出來！計算的方法是
1. 如果是運算元，那就直接Push 到stack 中
2. 如果是運算子，那就Pop 出stack 最上面兩個數字，算完再Push 回去
舉個例子：假如後序是 1 2 + 4 –
那我們會先把1,2 丟進stack；然後碰到“+”時把1,2 拿出來計算，再把答案3 丟
回stack；然後把4 丟到stack，碰到”-“時再把stack 的3,4 拿出來處理，再把答
案-1 丟回stack；算式結束後，stack 中剩下的值(唯一存在的)就會是答案。
Input
第⼀個數字N，表示N 組測資。
接下來N 行，每行表示⼀組測資。
每行有⼀個開頭數字M，代表運算元加運算子總共有多少符號。
然後，後面接著有M 個符號，且任兩個運算元或運算子中間會以空白隔開。
每行運算元以及運算子加起來最多1000 個。
每個運算元為絕對值小於等於1000 的整數，運算子有”+”,”-“
Output
對於每組測資，輸出該算式的答案。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
給⼀個由2D 點座標所組成的數列S，點的座標會先依照x 座標(小到大)，再依
照y 座標(小到大)排序。針對每個數列S，會有多個詢問。每個詢問會給予⼀個
座標，請回答這座標有沒有出現在S 中。
Input
多組測資，每組測資第一行有兩個正整數，n(n<100000)表示座標點的數量，以及q(q<100000)表示問題數量。
接下來n行，每行有兩數字x,y(int範圍)代表每個點的座標，中間以空白隔開。
接下來q行，每行有兩數字x,y(int範圍)代表一個詢問
Output
對於每個詢問，請輸出這座標有沒有出現在S中。
有請輸出"Yes"，沒有請輸出"No"。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Hash Table(雜湊表)的時間複雜度完全建立在資料的分散程度。假如很多資料都擠在同一格，那他搜尋就需要花上O(n)；反之如果每個資料都分散在不同格，那他搜尋只需要O(1)就可以了。有證明指出當Hash Table的大小如果是質數，那資料會比非質數還分散！證明的話交給數學系就好，資工系只要會用就可以了。現在你想要建一個大小約為n的Hash Table，請你找到離n最近的質數。
Input
有多組測資。
每組測資有一個正整數N，2≤N≤1000000
Output
對於每組測資，請輸出離N最近的質數。
如果兩個質數與N的距離相同，則輸出比較大的那個質數。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
老鼠走迷宮是Alan大一程式設計的作業題目，他的問題是：老鼠只能走四個方向(上,下,左,右)，要怎樣才能讓老鼠從起點走出迷宮？當時陳煥宗老師是請大家讓老鼠靠著右邊牆壁走，就可以走到出口。不過Alan覺得這樣程式要跑好久，他希望老鼠可以在最短的步數內走到終點，但他不知道要怎麼寫比較好，你可以幫他完成他的作業嗎?
Input
有多組測資，每組第一行有兩個正整數n, m (2
字元種類有：‘#’代表牆壁、‘.’代表可以走的路、‘S’代表老鼠的起點的位置、‘E’代表出口的位置。(‘S’,‘E’都只會出現一次，且會出現在邊框)，
迷宮的邊框只會有三種可能：起點‘S’、終點‘E’、牆壁‘#’
Output
對於每組測資請輸出一行數字，表示老鼠最少需要走幾步才行到終點。若無解，請輸出-1。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
對於一個只有'a'到'z'的string，我們可以把它當成26進位表示法的數字。其中'a'表示0，'b'表示1……'z'表示25，"ba"表示26，"cb"表示53。
String number轉換成十進位的方法就是 a0*26n-1 + a1*26n-2+….+an-1*1
例如 "dcba"，就是 3*263 + 2*262 + 1*26 + 0*1 = 54106
現在請你把String Number轉成十進位數字。
Input
有多組測資，每組測資一行，每行有個字串('a'-'z')，字串長度最長是100
Output
對於每組測資輸出String Number轉成十進位的數字
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
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
有一天，勇者搗蛋在礦坑中採集魔法石。魔法石每顆威力都一樣，但是重量不一樣。由於搗蛋的背包有容量限制，所以當背包滿了的時候，他會希望能留下最輕的幾顆魔法石。有時候，他也會遇到怪獸，此時就要消耗背包的魔法石炸它。現在，給你這些事件的發生過程，請針對題目的要求輸出。
給予背包數量N及事件數Q，每個事件有2種可能：
1. Pick [Number]：表示撿起了重量為[Number]的魔法石。若背包還沒滿，則放入背包。若背包滿了，則留下最輕的N顆魔法石。
2. Use [Number]：表示遇到了怪獸，需要從背包拿出[Number]顆魔法石。為了減輕負擔，所以每次都是先用最重的魔法石。
針對每次”Use”指令，輸出用掉的魔法石重量。不會出現遇到了怪獸，但魔法石卻不夠用的情形。
Input
有多組測資。
每組測資第一行，有兩個整數N, Q (1<=N, Q<=10^5)
接下來有Q行，每行有”Pick”或”Use”，加上一個整數X (1<=X<=150000)
所以每次都是先用最重的魔法石。
針對每次”Use”指令，輸出用掉的魔法石重量。不會出現遇到了怪獸，但魔法石卻不夠用的情形。
Output
針對每個”Use”指令，輸出一行含有X個數字。
數字由使用的先後順序排序，中間含一個空白。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
John有 n 件事情要做，不幸的是這些事情並不是各自獨立的，而是有相依性的。換句話說可能有某件事情一定要在另一件事情做完之後才能做。
Input
每組測試資料可能有好幾列。第一列有2個整數 n,m。（1 <= n <= 100）n代表共有幾件事情要做（編號從 1 到 n），m 代表事情之間有幾個相依關係存在。接下來的m列每列有2個整數 i 和 j。代表 i 這件事情一定要在 j 這件事前被執行。
n=m=0時代表輸入結束。
Output
對每組測試資料，請輸出n個整數，代表事情被執行的順序。
註：答案可能不是唯一解
Sample Input Download
Sample Output Download
Tags
Discuss
Description
1976年，在電腦協助之下證明了4色地圖理論（Four Color Map Theorem）。就是僅以4種顏色在地圖上不同的區域塗色，使得相鄰的區域顏色均不相同。
現在，你要解決一個類似，但比較簡單的問題。給你一個相連的圖，請你在節點上塗色（只有2種不同的顏色），並且回答是否可以使得相鄰的節點顏色均不相同。為了使問題簡單一些，你可以假設：
沒有節點會有連向自己的邊。
邊是沒有方向性的，也就是說如果節點A可以連到節點B，那麼代表節點B也可以連到節點A。
圖形是強連通的，也就是說任2節點之間皆有路徑相連。
Input
輸入含有多組測試資料。每組測試資料的第一列有一個正整數 n（1 < n < 200）代表節點的數目。第二列有一個正整數m，代表邊的數目。接下來的m列每列有2個整數代表邊所連接的2個節點的代號。這n個節點的代號分別為0到n-1。
n=0代表輸入結束。
Output
對每一組測試資料輸出是否可以用2種顏色塗節點使得相鄰的節點顏色均不相同。
若可以請輸出：BICOLORABLE.，否則輸出：NOT BICOLORABLE.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
給你一個圖形，你的任務是找到一種最佳塗色的方法。圖形中的點要被塗顏色（只能塗黑色或白色），而且任何2個相連的點不可以都塗黑色。所謂最佳的塗色方法是指讓這個圖形黑色的點最多。以下圖形的塗色即是一種最佳塗色：
.gif)
Input
輸入的第一列有一個整數，代表以下有多少組測試資料。
每組測試資料的第一列含有2個整數 n ( 1 <= n <= 100 )，k。n 代表圖形中點的數目（編號從1到 n），k 代表圖形中邊的數目。接下來的 k 列每列含有 2 個點的編號，代表一個邊。請參考Sample Input。
Output
對每一組測試資料輸出 2 列。第一列輸出最多可以有多少個點可以被塗黑色。第二列輸出一種可能的塗法，以塗黑色點的編號來表示。請參考 Sample Output。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
一位稀有書籍收藏家最近發現一本用一種不尋常的語言所寫的書。雖然這書看起來是用26個英文字母寫成的，但是其英文字母的順序卻跟我們所熟悉的英文字母不同。例如：在我們的觀念中英文字母的順序（由小到大）應該是A,B,C,......,X,Y,Z。所以我們的英文字典中字的順序可能是：APPLE < BALL
這位收藏家在書中發現有索引的存在，所以他嘗試著從索引中去找出這種奇怪字母的排列順序。不久他就放棄了，因為實在是太繁瑣了。
你的任務是寫一個程式來完成收藏家的工作。也就是給你一些字（當然是根據這種奇怪字母的字典排列順序），請你找出各字母的排列順序。
Input
只有一組測試資料。每列有一個字（最多20個字元，都是大寫英文字母）。這些字代表在這本稀有書的索引中出現的字（字典順序由小到大）。當遇到僅含有一'#'的一列，代表輸入結束。請注意：在這些字中並非26個英文字母一定都會用到，但是從這些字當中一定存在唯一完整的字母排列順序。
Output
輸出一列各字母的排列順序。若以Sample Input為例說明：
從第一列及第二列可以得到的資訊：X
從第二列及第三列可以得到的資訊：沒有
從第三列及第四列可以得到的資訊：Y
從第四列及第五列可以得到的資訊：Z
所以答案應該是XZYW
Sample Input Download
Sample Output Download
Tags
Discuss
Description
小鳥彼爾德是可愛的圖案，Alan喜歡用彼爾德的圖案來回應別人。彼爾德的圖案有多種，以下列出其中幾種圖的代碼以及他的網址
.gif) |
A |
 |
E |
| http://img.com/Bird/001.gif | http://img.com/Bird/016.gif | ||
 |
B |
 |
F |
| http://img.com/Bird/002.gif | http://img.com/Bird/105.gif | ||
 |
C |
 |
G |
| http://img.com/Bird/012.gif | http://img.com/Bird/036.gif | ||
 |
D |
 |
H |
| http://img.com/Bird/042.gif | http://img.com/Bird/032.gif |
請對於Alan輸入的網址輸出彼爾德圖的代碼
Input
多組測資，每組測資ㄧ行，每行有一個網址(只會出現上面列出的網址)
Output
對於每組測資，輸出對應圖案的代碼。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
最近大學推薦申請放榜，搗蛋想要查查看他的學弟有沒有上清大，所以他就去找了清大榜單來查。不過要慢慢找准考證實在太麻煩了，你能幫他找到他學弟的准考證號碼嗎?
Input
有多組測資，每組測資第一行有兩個正整數n(n<105)代表榜單上准考證號碼數量，以及q(q<105)代表詢問次數；接下來會有n個准考證號碼(int範圍正整數，且不會有0開頭)表示榜單，再接下q行每行有個准考證號碼(int範圍正整數)代表一個詢問。榜單准考證號碼不會照准考證順序排，且因為一個人同時可以申請多個系所，所以榜單的准考證號碼可能會重複。
Output
對於每個詢問，如果准考證號碼有出現在榜單上輸出"Yes"，反之輸出"No"
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
話說搗蛋是一個包打聽，他的樂趣就是觀察某些人的互動或是從朋友那打聽消息，以確定某兩個人是否有姦情好感。（雖然這猜測不一定正確，有時還會被吐槽『這誤會可大了！』，但他樂此不疲～）
有一天，他收到一封加密過的名單。上面列有一連串的資料，每筆資料代表被懷疑的兩人。但由於這份名單被隱去名字只有代號，他可能只知道A<=>B、A<=>C、B<=>D、、等。為了解密，他決定先將這些代號分成男生一群、女生一群，再來推測人名。請問是否有一個分法，可以將這些代號分成兩群？（當不能分成兩群的時候，表示可能發現了一個大秘密…）
Input
有多組測資。
每組測資第一行為整數N，表示有N個人(代號為1..N，N<=1000)
接下來為整數K，表示有K個被懷疑的關係。
接下來K行，每行有兩個整數，表示這兩個代號可能是互有好感的。
當N=0時，測資結束。
Output
針對每組測資，
如果有辦法將代號分成男女兩群，請輸出”Successful”；
否則，請輸出”You discover a BIG Secret!!”
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在一個字串中，「未排序」的程度是以各字元間彼此的大小關係來計算的。例如在字串 DAABEC中，「未排序」的程度為 5，因為D比它右邊的4個字元大，E比它右邊的1個字元大。而字串AACEDGG「未排序」的程度為 1（幾乎是快排序好的，唯一的未排序發生在E和D之間），字串ZYXW「未排序」的程度為 6（剛好是完全排序的相反）。
現在你的任務是為許多的DNA字串來做排序。每個字串中僅含有A,C,G和T這4種字元。排序的原則是根據各字串「未排序」的程度，由小到大輸出。在這裡每個字串的長度均相同。
Input
多組測資。每組測試資料的第一列含有2個正整數 n（0 < n <= 600）和 m（0 < m <= 10000），n 代表字串的長度，m 代表字串的數目。接下來的 m 列，每列有一個長度為 n 的字串。
Output
對每組測試資料按照「未排序」的程度，由小到大輸出。各組測試資料之間請輸出一空白列。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在叢林中因為樹木藤蔓很多，在經過一些地方時需要花比平常更多的時間。地圖上有’#’表示無法經過的障礙物，’.’表示需要花一個時間經過的平地，’T’表示需要花兩個時間經過的樹林，’S’表示起點，’E’表示終點，起點終點只出現一次，行走方向有上下左右四種，現在你可以算算從起點到終點最少需要多少時間嗎?
Input
多組測資，每組第一行有兩個正整數n(n<=700),m(m<=700)代表地圖的行與列，接下來n行會有m個符號表示這個地圖。
Output
對於每組測資輸出從起點到終點所需花的時間，如果無法到終點輸出"-1"
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
在Waterloo大學裡有許多的建築物正在興建。學校雇用了建築工人、水電工人以及一個程式設計師。程式設計師？不要懷疑，那個人就是你。你的任務就是要算出要建置校園網路需要用多少纜線。
每棟建築物可以視為在X-Y平面上的一個點。連接2棟建築物的網路線均為直線，且網路線為雙向的。網路線可以自由的跨越，但是只有在建築物的地方網路線才有接頭。
學校給你一張校園的地圖，上面有各建築物的位置座標，以及一些已經存在於建築物間的網路線。對那些已經存在的網路線，你不要去動它。你的任務是要架設新的網路線，使得所有的建築物都可以藉由網路相連。當然，學校方面希望你新架設的網路線越短越好。
Input
輸入含有多組測試資料。
每組測試資料的第一列有一個整數N（1 <= N <= 750），代表建築物的數目（建築物的編號從1到N）。接下來的N列每列有2個整數（介於-10000到10000之間），代表為這N棟建築物的座標（不會有2棟不同的建築物在同一個點上）。再接下來的一列有一個整數M（0 <= M <= 1000）代表已有M條網路線連接於建築物之間。再接下來的M列每列有2個正整數代表某條已存在的網路線所連接的2棟建築物編號。任2棟建築物間最多只會有一條網路線連接。
請參考Sample Input。
Output
每組測試資料輸出一列。含有一個浮點數（小數點後2位），代表你所新架設的網路線的長度，使得校園間各建築物都可以網路連接，而且長度要最小。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Alan 出題目時會隨機產生一些測試資料。現在他要出一個BFS 題目，所以他用電腦隨機
產生一些邊，但是測試資料中不應該出現重複的邊，也不應該出現自己連自己的情況，所
以他得把這些情況都處理掉。不過他最近為了訊號與系統考試焦頭爛額中，你可以幫他處
理測資嗎?
Input
有多組測資。
每組測資，第一行有兩個正整數。
n(n<=500)表示這組測資有多少個點，m(m<=50000)表示原本邊的數量。
接下來m 行，每行會有兩個正整數代表一個邊。點的編號是由1~n，邊是雙向邊。
Output
對於每組測資，輸出沒有重複邊與自己連自己情況的測資。
第一行是點的數量n’與邊的數量m’。
接下來m’行輸出所有邊，邊請照原本輸入順序排列。每組測資之後請多一個換行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
捷運會依照你坐了多少站來收費，計算費用的方法是：(起點到終點的最短距離/5)*5+20。
例如永春站要到台北車站，最短路線是永春->市政府->國父紀念館->忠孝敦化->忠孝復興
->忠孝新生->善導寺->台北車站，共需經過七站，所以票價就是 (7/5)*5+20 = 25 元。現在
給你捷運地圖，以及起點站，你能夠算出起點站到所有站所需要的票價嗎?
Input
有多組測資，每組測資第一行有三個正整數n(n<=500)代表捷運站數，m 代表連線，以及
s 代表起點站。接下來m 行每行有兩個正整數a,b(1<=a,b<=n)代表捷運站的連線(雙向)，捷
運站之間必定是連通的
Output
對於每組測資，請依照index順序輸出起點站到所有站所需的票價，不同站票價中間空一個空格，
起點站到起點站不用錢。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在西洋棋裡，皇后的移動方式是選擇米字的其中一個方向移動，且移動步數可為任意長度。
有一個經典問題名為N 皇后問題，在一個N*N 的西洋棋盤上找一個解法，放置N 個皇后，
使得這些皇后兩兩不會攻擊到彼此。
現在將棋盤上的每一格賦予一個數字。並定義⼀一個解法的分數為，這N 個皇后所在位置的
數字相加。給予一個N*N 棋盤，詢問所有解法內，分數最高的解法為多少？
Input
有多組測資。
每組測資第一行，有一個整數N(1<=N<=8)。
接下來有N 行，每行有N 個數字，且每兩個數字間用一個空白隔開。
每個數字Qij 為整數。(-100 <= Qij <= 100)
Output
輸出所有N 皇后解法中，分數最高為多少。
若無任何可行的N 皇后解法，則輸出”No Solution”。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Output the sum of A+B in radix N.
Input
For each line, there are three positive integers, N, A and B. (2 <= N <= 16, A, B is at most 100-digits) A and B are represented in radix N.
Output
For each line a case, output the sum of A+B in radix N.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two strings, output them in alphabetical order.
Note: the order is AaBbCcDd ... YyZz.
Input
For each case a line, there are two strings separated by a single space. The lengths of the strings are no more than 30.
Output
For each case a line, output the two strings in alphabetical order, separated by a single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000), denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b (1 <= a,b <= 1000), which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Output
For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a tree G(V, E) and its root, print its level-order traversal, where we visit all of the nodes at the same level before going to the lower ones. Each node is labeled by a unique integer number, and in case that the node has more than one child, the one who is labeled by smaller number should be visited first. The figure below illustrates the structure of two sample cases.
Figure. The illustration of two sample cases.
Input
The first line of input is a single integer T (T ≤ 100), denoting the number of test cases. Each test case started with an integer pair N (N ≤ 1000) and R, indicating the number of nodes and the root number respectively. The following N - 1 lines contain pairs of integers ui and vi (1 ≤ ui, vi ≤ N), each in a line, which means ui and vi are adjacent.
Output
For each test case, output “Case i:” denoting the traversal of i-th test case on a line. Then, for each visited node, started from the root, print the labeled number. Every two successive numbers are separated by a space characters. Print a blank line between test cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a string, output all different possible set of K characters in the string. And sort them in the dictionary order. For example, if K=2 and the given string is ‘CDBABBD’, output
AB
AC
AD
BB
BC
BD
CD
DD
Input
The first line of input contains a positive integer t (t <= 30), which indicates the number of test cases. For each case, there are one strings and a positive integer K in a line. The length of the string is less than 100 and strings contain only 'A'-'K'; The number K, less than or equal to 10, indicates the length of substrings.
Output
For each test case, output all different possible set of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The map is a 2-dimensional grid of squares, each square is filled with one color. You will be given a sequence of colors. You can move between adjacent squares vertically or horizontally in the given color order. '*' is where you start, and '#' is the goal.
For example, given the map as follow, and the color order "RGB":
BGRG#
RGBGR
*GRGB
There are two different ways to reach the goal:
xx456
123xx
0xxxx
and
xxxx8
123x7
0x456
So we know that the shortest path from '*' to '#' needs 6 steps.
Implement a BFS to find the smallest number of steps to reach the goal.
Input
The input consists of several maps. Each map begins with a line containing two integers N and M (1 <= N, M <= 10^3) specifying the map height and width. The next N lines will be M upper case letters, '*', or '#'. Each letter denotes one color.
The next line is a string that specifies the color order. One color won’t appear twice in the given order.
Each case is separated by a blank line. The input is terminated by two zeros.
Output
For each map, print one line containing the smallest possible number of step to reach the goal. If there's no way to reach the goal, output the string "No solution." instead. One step is defined as a movement between two adjacent cells.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A plot '#' represents a land. If two plots are adjacent horizontally, vertically, or diagonally, then they are part of the same island. An island can be quite large and may contain numerous plots. Your job is to determine how many different island are there.
Input
The input file contains one or more maps. Each map begins with a line containing M and N, the number of rows and columns in the map, separated by a single space. If M = N = 0 it signals the end of the input; otherwise 1 <= M <= 100 and 1 <= N <= 100. Following this are M lines of N characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either '*', representing the sea, or '#', representing the land.
Output
For each map, output the number of distinct islands. Two different lands are part of the same island if they are adjacent horizontally, vertically, or diagonally.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 chess queens. The task is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the sum of the numbers on the squares selected is the maximum . (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one queen.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions.
Input
Input will consist of K (the number of boards), on a line by itself, followed by K sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a non-negative integer less than 100. Each case is separated by a blank line. There will never be more than 20 boards.
Output
The outputs of all test cases should be printed in order. For each test case a line, print the highest score right justified in field 5 characters wide.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sequence of digits, there may be many ways to add “+” and “-” between them to form an expression whose evaluated result is 0. For example, there are 3 solutions to the sequence “1 2 1 2”, which are “1 + 2 - 1 - 2”, “1 - 2 - 1 + 2” and “12 - 12”. Note that the sign must be put between two digits (which means “- 1 + 2 + 1 - 2” is not a valid solution), but it is not necessary to add signs between every pairs of digits (“12 - 12” is valid, for instance). Moreover, the order of digits in the sequence may not be changed. Find the number of valid solutions to a given sequence.
Input
Each test case consists of two lines. The first line is an integer N (2 ≤ N ≤ 12) denoting the number of digits in the sequence, and the second line contains N digits in the range [1, 9]. The input is terminated by a zero after the last test case, and the number of test cases will be no more than 1500.
Output
For each case, output “Case i:” and then the number of solutions, seperated by a space character, i is the number of test case starting from 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are N jobs (labeled from 1 to N) that you have to schedule, and some jobs are related to other jobs. For example, if job No.3 is related to job No.2, then job No.3 can only be done after job No.2 is done.
Output the number of all possible scheduling.
Input
The first line contains a positive integer T (T <= 20), which indicates how many cases in the input.
Each case starts with two positive integers N and M (1 <= N <= 10), and N denotes the amount of the job. The next M lines contain the relationship among jobs. Each line contains two positive integers A and B, separated by a single space, denoting A is related to B.
Each case is separated by a blank line.
Output
The output contains one line for each test case. Each line contains an integer, which is the number of all possible ways.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Sudoku is a number-placement puzzle. The goal is to fill a 9×9 grid so that each row, each column and each of the nine 3×3 blocks (the sub-squares that compose the grid, indicated by the bold lines in the figure below) contains all of the digits from 1 to 9. Please solve the given puzzles.
.png)
Figure. A Sudoku puzzle
Input
The first line of the input consists of an integer T, which is the number of puzzles. Each puzzle occupies 9 lines, and there are 9 digits in each line. The empty cell is filled with 0. The first line is followed by an empty line, and there is also an empty line between two successive puzzles.
Output
For each test case, output the sequence number of the test case, followed by the solved puzzle (all of the empty cells are filled according to the rule) in the same format as the input. Print an empty line between two successive puzzles.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two increasing sorted lists S1 and S2. Each has N integers. There are N*N sums composed of one element in S1 and the other element in S2. Please output the smallest N sums.
Input
The input includes multiple test cases. In each test case, the first line contains one integers N. The second line contains N integers and the third line also contains N integers.
Guarantee every element or every sum must be an integer.
1 <= N <= 105
Output
The one line contains the smallest N sums. They are separated by single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the grades of N people. Please output the sorted result. (Increasing order)
Input
The input includes multiple test cases.
In each test case, the first line contains one integer N. The following N lines specify the name Si and the grade Gi.
1 <= N <= 105
1 <= |Si| <= 10
0 <= Gi <= 100 (Gi is an integer.)
Output
For every test case, output the result in N lines. Every line contains the name and the grade. If more people’s grades are same, output by input order. (That means it uses stable sort.)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The median of an integer sequence can be found by arranging all the integers from the smallest to the largest and picking the middle one. If the number of integers is even, the median is defined to be the mean of the two middle integers. Given an integer sequence, output the median of the sequence.
Input
There are multiple test cases. Each case begins with an integer N (1 <= N <= 106) in a line. The next line has N integers are in the next line, separated by spaces. The input is terminated if N = 0.
Output
For each test case, print a number represent the median of the sequence.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It is a common feature that the web browsers support moving backward and forward among the pages recently visited. Please simulate this function, which uses two stacks, backward stack and forward stack, and is commanded by following keywords.
(1) VISIT <url> - Push the current page on the top of the backward stack, and make the page specified by URL become the new current page. The entries in forward stack are then discarded.
(2) BACK - Push the current page on the top of the forward stack and pop the page from the top of the backward stack, which becomes the new current page. If the backward stack is empty, this command should be ignored.
(3) FORWARD - Push the current page on the top of the backward stack and pop the page from the top of the forward stack, which becomes the new current page. If the forward stack is empty, this command should be ignored.
Assume that the browser initially loads the web page at the URL “http://www.acm.org/”.
Input
There is only one set of commands in the input. Each command occupies a line, and the length of URLs will be no more than 100 and they contain no space character. The number of commands will be no more than 100000, and the input is terminated by end-of-file (EOF). You may assume that the entries in the stack will be no more than 10000 at any time.
Output
For each command, output the URL of the current page after the command is executed, in a line. In case that the command is ignored, print “Ignored” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are N numbers in a queue. The origin sequence is from 1 to N. (1 is the head). The operation “Move a b” means to move all the numbers in front of a (including a) and then insert them in front of b without changing order. Given several such operations and output the final status of the sequence.
Input
There will be only one test case. The test case begins with an integer N (1 <= N <= 106) indicating the number of people. There are several operations followed. The format is “Move a b” (without quote) you can assume that the position of a is in front of the position of b. The test case is terminated by “Exit” (without quote).
Output
Output the numbers from the first one to the last one, and separate two consecutive numbers by a space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maintain a doubly linked list, which supports the following operations:
(1) IH i : Insert a new integer i to the head of the list.
(2) IT i : Insert a new integer i to the tail of the list.
(3) RH : Print and remove the element in the head of the list.
(4) RT : Print and remove the element in the tail of the list.
(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.
To improve the performance, it is suggested that three pointers be maintained: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.
Input
There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains no more than 500000 operations, and it is terminated by end-of-file (EOF). You may assume that i will fit in a 32-bit signed integer. The list is initially empty.
Output
For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a positive integer N, calculate the N'th Fibonacci number.
Input
For each case a line, there is a positive integer N. ( 1 <= N <= 1000 ) When N equals 0, it is the end of file.
Output
For each case a line, print the N'th Fibonacci number.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Edit distance is to measure the difference between two strings. There are three types of edit operations that can be used to change a given string S:
(1) Substitution: replace a character of S by a different character. For example, “cut” can be changed to “cat” by replacing “u” with “a”.
(2) Insertion: insert a single character into S. For example, “cat” can be changed to “cats” by inserting “s” at the end of “cat”.
(3) Deletion: delete a single character from S. For example, “cats” can be changed to “cat” again by deleting “s” from “cats”.
Given two strings S1 and S2, the edit distance between S1 and S2 is defined as the minimum number of edit operations required to transform S1 to S2.
Input
Each case consists of two lines. Each line contains a string of lowercase characters, with the first line representing S1 and the second representing S2. The length of each string is no more than 4000.
Output
Print the edit distance between S1 and S2.
Hint
Suppose that S1 and S2 are strings with n and m characters, respectively. Let S1[1..n] and S2[1..m] denote these two strings. Now, we can define a function Dist(x, y) to give the edit distance between the strings S1[1..x] and S2[1..y]. It is easy to check that Dist(x, y) satisfies the following rules:
●Dist(x, 0) = x for all x = 0, 1, 2, …, n;
●Dist(0, y) = y for all y = 0, 1, 2, …, m;
●Dist(x, y) = min { Dist(x – 1, y)+1, Dist(x, y – 1)+1, Dist(x – 1, y – 1)+a } if x > 0 and y > 0, where a = 1 if S1[x] is not the same as S2[y]; otherwise, a = 0.
The required answer will be the value of Dist(n, m).
You should store the value of each entry Dist(i, j) or you may not pass all of the test case
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within the range.
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases. In each test case, the first line contains an integer n (n <= 105), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-231 <= ai <= 231-1). The followed line contains a positive integer q (q <= 105), denoting the number of queries. Next q lines define q queries, one per line. Each query is specified by two integers a and b (1 <= a <= b <= n), meaning a range, in which the partial sum of the given integers are queried.
Output
For each query, output a line with the partial sum of the given integers within the queried range.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Give two strings which represent the pre-order traversal and the in-order traversal of a binary tree, generate the post-order traversal of the binary tree.
Input
The input consists of several test cases. Each test case has two strings in a line separated by a space. The first string is the pre-order traversal of the binary tree; the second string is the in-order traversal of the binary tree. Each string will contain only capital characters and the characters will be unique.
Output
For each test case, output a string to represent the post-order traversal of the binary tree.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Palindrome is a string that is identical to its reverse, like "level" or "aba". Given a string, find the longest palindrome in the string.
Input
The input consists of multiple lines. Each line contains a string. The length of each string is less than 1000.
Output
In each test case, output the longest palindrome in the string. If there are many palindromes of the same length, output the first one in the string.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are many countries on a map. Each of them has a unique ID, which is a positive integer. All of them want to expand their territories. A country can expand its territory if its neighboring land (up, down, left, and right) has not been occupied by any other countries. The expansion speeds are the same for all countries. (We may consider that all countries simultaneously perform one expansion move at a time.) If two or more countries want to occupy the same land, the country with the smaller ID can occupy the land. The expansion stops if no changes of the map can be made.
Input
The input file begins with an integer T (1 < T < 1000), indicating the number of test cases. Each test case begins with three integers N, M, and K (0 < N < 300, 0 < M < 300, K
Output
For each test case, output the final area (number of lands) of each county, ordered by the country’s ID (from small to large). Print a blank after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Evaluate the result of a given numerical expression written in postfix notation.
Input
The first line of the input contains an integer N (N ≤ 100) which denotes the number of test cases. Each test case begins with an integer M (M ≤ 10000) representing the number of tokens in the expression, followed by M tokens in the next line. Tokens are separated by spaces and the operators contain only “+”, “-”, “*” and “/”; the operands are integers in the range [0, 100]. The division operator “/” here is considered as integral division. You may assume that all of the expressions are valid (divide-by-zero would never occur) and the answer will fit in 32-bit signed integers. Evaluated results (in each stage of the evaluation ) will fit in 100-digit signed integers and divide-by-bignumber would never occur.
Output
The output of each test case occupies a line. Each line begins with the test case number “Case i:”, and then a space character followed by the evaluated answer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We can encrypt a string into other string. One method is to put a string into an n×n array first, where n is the smallest number such that n2 is larger than or equal to the length of the string. Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order. The encrypted string is the output of the row major order. For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.
The output string is "Googrd e sed i".
If the end of the encrypted string are spaces, don't output them. For example, the output of "Bass GG" is "B Ga Gss".
Input
The input consists of multiple lines. Each line is a test case, a string S with length <= 1000. The number of test case is less than 100.
case1: O(N)
case2: O(N)
case3: O(N)
case4: O(N)
N means string length.
Output
For each test case, output the encrypted string of S.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two strings, find the length of the longest common substring.
Input
The first line of input contains a positive integer t , which indicates the number of test cases. For each case, there are two strings in a line (length of the string <= 1000).
Case1: O(n3) T <= 10 , length of string <= 100
Case2: O(n2) T <= 100 , length of string <= 1000
Case3: O(n2) T <= 100 , length of string <= 1000
Case4: O(n2) T <= 500 , length of string <= 1000
Output
Output the length of the longest common substring.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are some rectangles in 2 dimensional space. We define some relations:
(1) Intersect: Choose any 2 rectangles A and B. They intersect each other if and only if there exists at least one point that can cover by the 2 rectangles. If A and B intersect, they are in the same group.
Figure 1. Sample of intersection
(2) Transitivity: Choose any 3 rectangles A, B, C. If A intersect B and B intersect C, we denote that A, B, C are in the same group.
Figure 2. Sample of Transitivity
Given the rectangles in the 2D space, please find the size of the maximum rectangle group.
Input
There are more than one cases in the input. Each case contains N rectangles in the first line of the case. In the next n lines, each line contains 4 integers: lx, ly, rx, ry. (0 <= lx, ly, rx, ry <= 1000)
lx, ly denote the left-bottom coordinate of the rectangle.
rx, ry denote the right-top coordinate of the rectangle.
Input ends with N = 0.
9212 O(N!*N) can pass this input, N <= 10
9213 O(N3) can pass this input, N <= 100
9214 O(N2) can pass this input, N <= 1000
9215 O(N2) can pass this input, N <= 1000
Output
For each test case, output the number of maximum group in one line.
Take first input for examples.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000), denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b (1 <=a,b <= 1000), which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
9216: O(N!*N)
9217: O(N3)
9218: O(N2)
9219: O(N2)
Output
For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Please maintain a min-max heap, which stores integers and is able to support following operations:
(1) PUSH k - Insert an integer k into the heap. k will fit in a 32-bit signed integer.
(2) POPMIN - Delete the minimum element from the heap.
(3) POPMAX - Delete the maximum element from the heap.
(4) MIN - Print the minimum element in the heap.
(5) MAX - Print the maximum element in the heap.
Input
There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 5*106. You may assume that the number of elements stored in the heap will be no more than 3*106 at any time.
Case 1: For each operations O( n ), operation num:104
Case 2: For each operations O( log(n) ), operation num:106
Case 3: For each operations O( log(n) ), operation num:2*106
Case 4: For each operations O( log(n) ), operation num:5*106
Output
(1) POPMIN - In case that the heap is empty, print ”Error” instead.
(2) POPMAX - In case that the heap is empty, print ”Error” instead.
(3) MIN - Print the minimum element in the heap. In case that the heap is empty, print ”Null” instead..
(4) MAX - Print the maximum element in the heap. In case that the heap is empty, print ”Null” instead.