Description

Alfred wants to plan what to cook in the next days. He can cook various dishes. For each dish the costs of the ingredients and the benefit value is known. If a dish is cooked the second time in a row, the benefit value for the second time is 50 percent of the benefit value of first time, if it is prepared for the third or higher time in a row, the benefit value is 0. For example cooking a dish with benefit value v three times in a row leads to a total benefit value of 1.5*v.
Help him to build the menu which maximizes the benefit value under the constraint that his budget is not exceeded.

Input

The input consists of several test cases. Each test case begins with 3 integers in a line: The number of days k (1<=k<=21) Alfred wants to plan for, the number of dishes n (1<=n<=50) he can cook and his budget m (0<=m<=100).
The following n lines describe the dishes Alfred can cook. The i-th line contains two integers: the costs c (1<=c<=50) and the benefit value v (1<=v<=10000) of the i-th dish.
The end of the input is signaled by a test case with k = n = m = 0. You don't need to process this test case.

Output

For each output, print the maximum benefit value reachable with 1 digit after the decimal point. Then print k integers with i-th integer being the number of the dish to cook on day i. Dishes are numbered from 1 to n. Print at least one space or new line character after each integer.
If there are several possible menus reaching the maximum benefit value, select the one with minimum costs, if there are several with minimum costs, you can print any of them.
If every menu exceeds the budget, print only the benefit value of 0.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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.

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

撲克牌一副有52張，一副新的撲克牌由上到下的順序是：黑桃A, 黑桃2,…, 黑桃Q, 黑桃K, 紅心A, …, 紅心 K, 梅花A, …,梅花K, 方塊A,…,方塊K，為了方便起見，我們以{1, 2, 3, …, 51, 52} 作為一副新的撲克牌由上到下的順序。

如果大家看過Liar game (詐欺遊戲)，想必知道有一種叫做完美洗牌的洗牌方式，一開始洗牌的時候，會將撲克牌由上到下平分成兩堆，假設是第一次洗牌，則開始會分成{1, 2,…, 26}和{27, 28, …, 52}左右兩堆，一般洗牌是將撲克牌面朝下左右交錯的洗，之所以稱作為完美洗牌，代表他有以下的特性：

1.      同一堆的牌在洗完牌之後必定不會放在相鄰的位置，也就是洗牌每次都是左右各一張的交錯。

2.      每次洗牌的兩堆牌必定平分成等量的兩分

3.      左手邊是撲克牌上面的26張，右手是剩下的26張

4.      每次洗牌交錯時必定先從左邊開始

根據這樣的規則，一副新的撲克牌在第一次洗牌之後的順序會變成：

{27, 1, 28, 2, 29, 3, …, 51, 25, 52, 26}

我們沒有像Liar game一樣的心算能力，所以請你寫一個程式去計算一副新的撲克牌經過完美洗牌k(0 <= k <= 10,000,000) 次後，撲克牌的排列

Input

第一行有一個正整數T (T < 30)，代表接下來有幾筆測試資料

接下來T行，每行都有一個數字k (0 <= k <= 10,000,000)，代表一副新的撲克牌經過k次的完美洗牌。

Output

每筆測試資料各佔五行。

對於每筆測試資料，第一行輸出"Case i:"表第幾筆測資，接下來四行輸出經過k次完美洗牌後由上到下的排列順序，每13個數字一行。

在每一行中，相鄰兩個數字之間以一個空白隔開，第一個數字前面以及最後一個數字後面不可以有空白。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Luchu在學校是個很受女同學歡迎的男生，在他要畢業的時候，學校將舉辦著一場盛大的舞會，大受歡迎的Luchu受到了眾多女性的舞伴邀請，Luchu想從這幾個女性挑出適合做為舞伴的女性。為了讓他能在畢業舞會中展現絕妙的舞姿，他決定由下列的方法選出最適合的女伴：

1. 這位女伴的身高不能跟自己一樣高，不然跳起來在視覺上太對稱會沒有美感
2. 因為Luchu不希望女伴和自己身高差太多，所以他打算從比他矮的女性中挑一個最高的作為女伴後選A
3. Luchu不在乎女伴比自己高，但也不能高太多，所以他打算從比他高的女性中挑一個最矮的作為女伴後選B

Luchu想先知道女伴後選A和B的身高後再決定要選哪位作為舞會的幸運兒。今天女同學由左到右，按照身高由低到高排列 (相鄰的兩位女同學的身高可以相等)，今天Luchu告訴你他自己的身高，想要問你女伴後選A, B的身高各是多少？

Input

輸入只有一組測試資料，第一行有一個數字N (1 <= N <= 50,000)，表示有N位想要跟Luchu跳舞的女同學。第二行是這N位女同學由小到大排列的身高，身高的範圍以正整數表示 (1~2³¹-1)，每個數字後面都會有一個空白隔開。第三行Q (1 <= Q <= 25,000)，表示Luchu有幾種可能的身高，不用為此感到奇怪，因為當Luchu發覺他適合的女伴後選A和B都不合他的胃口時，他會換一雙不同高度的鞋子來微調他的身高，直到他覺得滿意為止。) 下一行有Q個Luchu可能的身高，也是以正整數表示 (1~2³¹-1)，每個數字後面都會有一個空白隔開。

注意：輸入和輸出請不要使用C++的cin, cout，這兩個太慢可能會造成超時的問題，可以使用scanf和printf作為替代。

Output

輸出一共有Q行，每行都有兩個正整數，並且這兩個數字之間以一個空白隔開，每行的這兩個數字代表每次得到Luchu後，女伴候選A和B的身高，如果沒有比Luchu矮或高的女伴，就輸出大寫字母X表示。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一個連續非負整數陣列A = {a₁, a₂, …, a_N}，已知0 < a₁+ a₂+ …+ a_N < 2³¹，給定一個數字x，請寫一個程式判斷陣列A中是否存在連續和a_i + a_i+1+…+a_j = x？(注意：連續和至少包含一個陣列元素)

Input

第一行有一個正整數 T (T <= 50)，表示接下來有T筆測試資料。

每一筆測資資料都有三行資料，第一行有一個正整數N (N < 500,000) 表示陣列A的長度是N。第二行有一個整數x (0 <= x < 2³¹)，代表題目中的x值。第三行有N個整數，每個整數的範圍介於 (0 <= x < 2³¹)，且兩個整數之間以一隔空白隔開。

Output

每筆測資各占一行，如果存在一個連續和為x，輸出Yes，反之輸出No。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

排序是電腦科學裡面重要的一個東西。如果資料是排序好的話，幾乎每個問題都可以很有效率的解決。

市面上有一些很棒的排序演算法已經可以到達排序的下限O (n lg n)。

在這個問題我們想要討論的是一個新的排序方法。

在這個方法裡只有一個運算叫Flip，這個運算的動作是只能交換相鄰兩個數字。

給你一些數字。然後用Flip這個運算把這些數字由小排到大。

你必須找出最少要做這個運算幾次，才能把這些數字排好。

範例如下：

"1 2 3" --> 0次

"2 3 1" --> 2次

Input

輸入有多組測試資料。每組測試資料會給定一個N(N<=1000)，代表有幾個數字。

下一行會有N個以空白隔開的整數，代表這N個數字。

輸入以EOF結束。

提示：讀測資可以用while (scanf("%d", &N) == 1)或while (scanf("%d", &N) != EOF)的方式讀取多組測資，以後不再提示這類輸入問題。

Output

對每組測試資料印出一行"Minimum exchange operations : M"，M是最少翻轉的次數。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給定一堆電話號碼，決定是否合法，合法的規則是，

沒有一個人的號碼是別人號碼的前端 (Prefix) 出現。以下是範例：

• Emergency 911
• Alice 97625999
• Bob 91125426

在範例裡，我們不能去叫Bob，因為Emergency的號碼"911"會是Bob電話號碼的前端 (Prefix) 。

因此這個範例是不合法的。

Bonus: 使用Bubble Sort, Insertion Sort 或 Selection Sort Accepted的同學，將code寄給助教檢驗可以多得到一題的分數。

Input

第一行給一個整數t, 1<=t<=40, 代表有幾組測試資料。
每組測試資料先給定一個整數n，代表有幾個電話號碼，1<=n<=10000。
接下來n行每一行都給一個不重覆的電話號碼，電話號碼長度最多只有10碼。

Output

對每一組測試資料， 如果他是恆定的輸出"YES"，反之則輸出"NO"。 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

實作一個Min-Heap, 模擬Heap的Insert, Delete, Top的功能。
以下是執行的幾種指令：

 i x 將數字x insert到Heap，x是整數 (0 <= x <= 2,147,483,647)
d 移除Heap中最小的元素
t 輸出Heap中最小的元素
e 離開程式

Input

輸入包含一連串的指令，每個指令各佔一行。

指令的個數在1,000,000個以內。

小提示：不需要先把所有指令讀完才能輸出，可以每次讀到t就直接輸出，不需要先記起來最後才輸出，所有題目這樣做都不會有問題，以後不再贅述。

Output

對於每個t指令，輸出Heap中最小的數，如果Heap裡面沒有任何元素時，輸出null。
每一筆輸出各佔一行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

大學學測放榜，教育部查榜系統提供一種查詢方式，輸入名次k，將列出該名次的總分以及所有排名為第k名的同學，

因為相同名次的同學很多，所以該系統統一以准考證號碼的順序來排列。

舉例來說，假設有5位學生：Mary, John, Ben, Alice, Gill
以下是他們的排名

Input

只有一組測資。
第一行有2個數字N (N <= 200,000) 代表學生總人數, Q (Q <= 50) 代表查詢名次的次數
接下來的N行代表按照准考證號碼順序排列的學生。
每行有學生的姓名 (只包含長度16以內的大小寫英文字母) 以及考試成績 (0~1000分的整數)

接下來有Q行，每行只有一個數字k (k > 0)，表示要查詢第k名的資訊

Output

一共有Q組輸出，每組的第一行輸出Query #i: 考試成績，i表示第幾個查詢，若輸入的名次k不存在，在考試成績的部分輸出null。
接下來幾行輸出該名次的同學名字(各佔一行)。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

排序是一個很常被使用的工具，如何更有效率的完成排序是一件很重要的事情。

交換排序的程式，雖然可以很簡單的使用O(n²) 的演算法來完成，不過我們希望改善他的效率，

因此同樣的題目，我們把數字的個數提升到1000倍！

提示：Merge Sort可以解決這個問題

Input

輸入有多組測試資料。每組測試資料會給定一個N (N<=1,000,000)，代表有幾個數字。

下一行會有N個以空白隔開的整數，代表這N個數字。

輸入以EOF結束。

Output

對每組測試資料印出一行"Minimum exchange operations : M"，M是最少翻轉的次數。

注意：M可能會超過int範圍

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一疊薄煎餅，請你寫一個程式來指出要如何安排才能使這些薄煎餅由上到下依薄煎餅的半徑由小到大排好。所有的薄煎餅半徑均不相同。

要把薄煎餅排好序需要對這些薄煎餅做翻面（flip）的動作。方法是以一抹刀插入一疊薄煎餅中，然後做翻面的動作（也就是說在抹刀上面的薄煎餅經翻面後，會依相反的次序排列）。若一疊共有n個薄煎餅，我們定義最底下的薄煎餅的位置為1，最上面的薄煎餅位置為n。當抹刀插入位置為k時，代表從位置k到位置n的薄煎餅要做翻面的動作。

一開始時，這疊薄煎餅隨意堆放，並以半徑大小來表示。例如：以下3疊薄煎餅（最左邊那一疊8是最上面一個薄煎餅的半徑）

8 7 2
4 6 5
6 4 8
7 8 4
5 5 6
2 2 7

對最左邊那疊薄煎餅，如果我們把抹刀插在位置3（就是半徑為7的那塊薄煎餅的下面）的地方做翻面，就會得到中間那疊，如果我們再把抹刀插在位置1（就是半徑為2的那塊薄煎餅的下面）的地方做翻面，就會得到最右邊那疊。

Input

每組測試資料一列，內容為這一疊薄煎餅一開始的狀態。每列開始的整數（介於1到100之間）代表位於最上方薄煎餅的半徑，依此類推。薄煎餅的數目介於1到30之間。請參考Sample Input。

Output

對每一組測試資料輸出2列。第一列為原來那疊薄煎餅。第2列則為要使這疊薄煎餅由小到大排列所做的翻面的動作。數字代表抹刀所插入的位置。（0代表已完成）。如果已經排好了，則不需再有翻面的動作。請參考Sample Output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

林克李斯特有個手環斷掉了, 他想修復這個手環,可是牛仔很忙, 所以他希望你能幫他組合這個手環.
這個手環是由大小不同的珠子造成的, 由於只有一條線, 所以從左邊或右邊放入珠子.
林克李斯特會給你一張指令表, 告訴你在那一邊放入多大的珠子. 不幸的是, 由於林克李斯特很懶惰, 所以當他發現錯誤的時候他不會去把指令改掉, 只會說要刪哪邊的珠子(What the hell!!)
再加上這個人又有點控制慾, 所以他會常常想要看看這串手環的情形. 因此, 你要滿足他所有目標！！
以下是指令表的形式：
ib x:把x大小的珠子加入手環的右邊
if x:把x大小的珠子加入手環的左邊
db:移除手環右邊的珠子
df:移除手環左邊的珠子
pb：印出手環最右邊珠子的大小
pf: 印出手環最左邊珠子的大小

Input

輸入只有一組測資, 有很多行指令. 指令最多不超過1000000個.

Output

當遇到pf或是pb的指令時, 印出相對應的值.如果鍊子上沒有東西的話,請輸出null

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

畢業的季節要到了. 為了給他女朋友一個畢業禮物, 大衛霍夫曼決定打造一個金鍊子. 他收集了很多的金條並且打算送到打鐵店把他們通通連成一條. 而打鐵店很有個性的每次只能連接兩個金條, 而連起來的價錢就是兩個金條長度相加, ex:長度2和長度3的連接起來的價錢為5 大衛是個窮苦的學生, 所以他希望能夠讓組合的價錢越低越好, 身為好朋友的你, 能不能幫他算出最低的組合價錢呢？！

Input

第一行輸入一個整數T(<=20), 表示有幾組測試資料. 每組測試資料描述了大衛要買得鍊子資訊. 接下來每組會先輸入一個N(1<=N<=40000), 表示大衛要買得鍊子數量. 接下來N個數字L1, L2, ..., LN, 描述了這N個鍊子的長度.

Output

對每組測試資料, 印出一行大衛要花的最少價錢

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在資料結構中有一個常見的問題就是二元樹的尋訪（traversal of a binary tree）。有三種方式來尋訪二元樹的每個節點：
前序（Pre-order）：先拜訪樹根，然後左子樹，然後右子樹。
中序（In-order）：先拜訪左子樹，然後樹根，然後右子樹。
後序（Post-order）：先拜訪左子樹，然後右子樹，然後樹根。
以下圖為例： 前序的拜訪順序為： ABCDEF， 中序的拜訪順序為：CBAEDF ，後序的拜訪順序為： CBEFDA。 在本問題中，給你一棵二元樹的中序及前序的拜訪順序，請你算出該二元樹的後序拜訪順序。

Input

輸入的第一列有一個正整數 C（C <= 2000），代表以下有多少組測試資料。 每組測試資料一列。每列的開始有一個整數 N（1 <= N <= 52），代表二元樹中節點的數目。接下來有2個字串，分別代表某一棵2元樹的前序及中序的拜訪順序。2個字串都只包含大寫或小寫英文字母，而且不會有重複的字母出現。輸入格式請參考Sample Input。

Output

對每一列輸入，請輸出該2元樹以後序拜訪的順序。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在本題中，題目會先給你一個包含小括號（）及中括號〔〕的字串。當字串符合下列條件時我們稱他為正確的運算式：
該字串為一個空字串
如果Ａ和Ｂ都為正確的運算式，則ＡＢ也為正確的運算式，
如果Ａ為正確的運算式，則（Ａ）及〔Ａ〕都為正確的運算式。
現在，請你寫一支程式可以讀入這類字串並檢查它們是否為正確的運算式。字串的最大長度為128個字元。

Input

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

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

西元67年，在羅馬和猶太人的衝突中，史學家 Josephus 和其他40個人被關在一個洞穴中。羅馬人知道 Josephus 的下落後希望他能投效羅馬帝國。但是他的同伴們卻不允許他投降。所以Josephus 建議他們彼此殺害，一個接一個，被殺的順序就由命運決定。傳統上他們決定命運的方式為：大家圍成一個圓圈，從某個人開始算起，每算到 3 個人那個人就被殺掉，如此不斷下去，直到只剩一個人。後來 Josephus 成為唯一的存活者並投降羅馬。我們有興趣的是：Josephus 如何剛好是那個存活者？真的是運氣好，還是他事先在暗地裡用 41 顆石頭練習過，或者他有一個數學的方法可以知道要站在哪一個位置才能成為最後的存活者？ 聽過這個故事後，你相當的憂心要是將來某一天你也面臨同樣的情況要怎麼辦。所以你決定用你的手上型電腦寫一個程式算出應該從那個人開始算起，你才可以成為那個最後唯一存活的人。 在這個問題中，你的程式必須能解決 Josephus 描述的另一種變形。有 n 個人排成一個圓圈，面向內，依順時鐘方向編號從 1 到 n。你的位置在 1 。殺人程序由編號 i 的人開始算起（順時鐘方向），直到算到第 k 個人，那個人立刻被殺掉。然後從這個被殺的人左邊的那個人再順時鐘方向算 k 個人，那個人必須負責埋葬剛才被殺的那個人，然後回去站在剛才被殺的那個人的位置。接下來從這個人的左邊那個人算起，第 k 個人又被殺掉，如此一直下去直到只剩下一個人為止。 例如：當 n=5, k=2, i=1, 那麼被殺的順序為 2, 5, 3, 1，存活者為4。

Input

輸入含有多組測試資料。 每組測試資料有2個整數 n, k 。你可以假設最多只有 100 個人。 若 n = k = 0 時代表輸入結束。請參考Sample Input。

Output

對每組測試資料輸出一開始時應該從哪一個人算起（也就是 i），才能確保你是最後唯一的存活者。請記住：你的位置在 1。以上述的例子來看，必須由第 3 個人算起，最後存活的人才能是 1 。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

平面上有MxN個格子，每格的寬和高都是一個單位長度。

今天這些格子裡面有一些被標記起來，稱之為障礙格，我們要從指定的兩個非障礙格A和B，找出從A走到B的最短距離 ，

對於每個格子都只能往他上下左右相鄰的四個非障礙格走動，每走一格就會多一個距離。

舉例來說：

上圖中深藍色的格子為障礙格，我們從A走到B的最短距離是：

從A往下走4格，往右走4格，往上走2格，往右走2格，往下走3格。

所以A走到B的最短距離是15。

Input

第一行表示有T (T <= 30) 組測試資料。

對於接下來T組測試資料中：

第一行有兩個正整數M, N(0 < M < 100, 0 < N < 100)表示格子寬和高的數量

第二行有兩個數字(X_A, Y_A)表示格子A的座標(0 <= X_A < M, 0 <= Y_A < N)

第三行有兩個數字(X_B, Y_B)表示格子B的座標(0 <= X_B < M, 0 <= Y_B < N)

第四行有一個整數B表示接下來有幾個障礙格

接下來的B行中各有兩個數字(X, Y)表示障礙格子座標 (0 <= X < M, 0 <= Y < N) 

Output

對於每一組輸出A到B的最短距離，如果A無法走到B，則輸出 -1表示。 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給定長度L (L <=20) 且皆由不重複的小寫字母組成的字串S

我們定義最小字典排列S'

假設S = "cab"，則最小字典排序S' = "abc" (就是所有字母由小到大排列)

我們要求第N+1小的字典排列(0 <= N < L!) (Hint: 所以N要用到long long)

舉例來說

假設S = "abc", N = 0，則答案為"abc"

假設S = "abc", N = 5，則答案為"cba"   

假設S = "abc", N = 3，則答案為"bca"  

假設S = "cba", N = 3，則答案為"bca"  

Input

第一行表示有幾組測試資料

接下來的每組測試資料都有兩行

第一行是字串S

第二行是整數N 

Output

每組測試資料輸出第N+1小的字典排列

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給一些變數關係：例如 x < y ,  x < z

求所有可能的排序關係(不會有兩個數字相等)，舉上面的例子來說

有可能是 x < y < z，也有可能是x < z < y
 

Input

有幾組測資不清楚(這題最難的是Input，請同學加油)

每組測資有兩行，

第一行是有哪些變數(每個變數都是單一小寫字母)，最少兩個，最多不超過20個變數，變數之間以空格隔開

第二行是兩兩變數關係，例如第一組測資的第二行a b b f就表示a

Output

對於每一組測試資料

按照字典排序輸出所有可能的排序關係

例如第一組測資的第一種輸出abfg就表示a

兩組測資要以一個空白行隔開，最後一組測資後面不要有空白行(注意：最後一組測資的最後一種輸出仍要換行)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給一個字串S，該字串由不重複的小寫字母組成，且長度最長為15

列出從字串S挑出k個字母可以組成所有可能的子序列(就是在原字串S中的前後關係不會變動)

例如S = "bac"，k = 2

那麼所有可能的字串為："ba", "bc", "ac"

Input

第一行T (T <= 30)表示有幾筆測資
對於每筆測資都有兩行，第一行為字串S，第二行為數字k (0 < k <= 字串長度)
 

Output

對於每組測試資料，第一行輸出"Case #i:"表示第幾組測資

接下來按照字典排序輸出所有可能的子序列
 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

2100年，宇宙傳輸將會成為事實。宇宙傳輸公司計畫了一些航班在一些人潮洶湧的行星上。

這些航班的花費已經預先決定了，而花費的單位叫做「嘎洛洛」。

對一些沒有直接航班的行星間而言，他們可以選擇一些直接航班可到之處當作中繼站(ex: A-B, B-C，那麼A可以到C)。

為了協助旅客們查詢航班，宇宙傳輸公司想要提供一個軟體讓旅客們可以直接找到最好的方式(花費最少的方式)從某星球到某星球，

輸出最好路徑上所有點。而如果有兩種以上的最好方法的話，就選擇編號較小的星球。

每個測試資料保證只有一個最好路徑。

技術規格

1. 星球的最多26個，最少1個。星球用大寫字母來表示(A~Z)
2. 各個星球的直接連線數最多200條，最少1條，每兩個星球之間最多只有一條直接連線。
3. 各個連線的花費是一個自然數，最多到100嘎洛洛。

Input

第一行有兩個整數s, p，中間空一空白。s代表星球數，p代表直接連線數。

接下來一行有一個整數n(n <= 20)表示有多少個問題。

接下來的n行，每一行包含兩個字每e_k和e_m，表示使用者正在找的最便宜的方式從星球e_k到e_m。

Output

對每個詢問，輸出一行最好的路徑，起點、中繼點以及終點，每個點之間空一個空白格。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

這個故事裡，有一群突擊隊員被交付一個重要任務：他們必須要摧毀敵人總部。

敵人的總部由很多大樓組成，大樓和大樓之間有路連接。突擊隊員們必須去過每個大樓並且放下炸彈。

任務在某個大樓開始然後散至各各大樓。突擊隊員通過大樓之間的路穿梭自如。

他們可以去任何他們可以到的地方，但是最後要在某個地方集合。

在這個問題裡，你得到了各個不同敵人總部內的資訊。你的工作就是決定最短的時間來完成這個任務。

每個突擊隊員在有相連的大樓裡穿梭只需要一單位的時間。你可以假設放炸彈的時間可以省略。

每個突擊隊員可以帶無限多的炸彈XD，突擊隊員的總數量也是無限多的!!

Input

輸入第一行有一圈數字T < 50，表示有幾組測試資料。

每個測試資料表示敵人的總部資訊，

每組測試資料第一行有一個正整數N(N <= 100)，表示有幾棟大樓屬於總部。

接下來一行有一個正整數R，表示有多少條路。

接下來每一行包含兩個不同的數字u,v，代表哪兩棟大樓相連0 <= u, v < N，表示有一條路從u到v。

大樓從0到N-1。

每組測資最後一行有兩個整數s, d(0 <= s, d < N)，s代表任務從哪開始，d代表他們集合之處。

你可以假設任兩棟大樓之間最多只有一條路。

但在兩棟大樓之間可能不只有一種走法。

Output

對每組資料輸出一行，包含case number還有最小完成時間。

詳情參考sample output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給定一群數組：A = {a₁, a₂, a₃, ..., a_n}，求該組數字的最小公倍數lcm(a₁, a₂, a₃, ..., a_n)

Input

測試資料第一行有一個數字T (T <= 100)代表接下來有幾筆測試資料 

每筆測試資料都有兩行

第一行有一個數字n (2 <= n <= 20)表示數組A有幾個數字

第二行有n個數字a₁, a₂, ..., a_n，每個數字都是正整數且0 < a₁*a₂*...*a_n < 2,147,483,648

Output

對於第i筆測試資料，輸出數組A的最小公倍數 x = lcm(a₁, a₂, ..., a_n)

輸出格式：Case i: x

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

古典數學家很常以信件來討論各自的猜想，以下是尤拉(Euler)寄給哥德巴契(Goldbach)的一封信

“That every number which is resolvable into two prime numbers can be resolved into as many prime numbers as you like, can be illustrated and confirmed by an observation which you have formerly communicated to me, namely that every even number is a sum of two primes, and since (n-2) is also a sum of two prime numbers, n must be a sum of three, and also four prime numbers, and so on. If, however, n is an odd number, then it is certainly a sum of three prime numbers, since (n-1) is a sum of two prime numbers, and can therefore be resolved into as many prime numbers as you like. However, that every number is a sum of two primes, I consider a theorem which is quite true, although I cannot demonstrate it.”

-- Euler to Goldbach, 1742

Euler認為所有偶數的數字都可以拆成兩個質數相加，但畢竟沒有經過證明，
而且有些奇數也有可能是兩個質數相加，請你設計一個程式，
判斷某個數字n是不是可以寫N = p1+p2，(p1, p2為相異兩質數)

Input

每一行代表一個測試資料，最多有10,000行
每行都有一個正整數 (0 < n <= 100,000,000)

Output

對於每一個測試資料，有以下兩種輸出情形：
n is not the sum of two primes!
n is the sum of p1 and p2.
如果一個存在多組n = p1 + p2，則輸出p1 < p2且p2-p1的值要最小的答案

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

清大某研究室為了分析新竹市民的社群分布情形，他們在火車站前找了N個人出來來取樣

統計，因為人數太多，所以他們採取了一策略，就是隨便抓兩個人出來問他們之間是不是

朋友，當他們發現A和B是朋友的時候，就會紀錄下來，在不知道幾次的詢問下，他們總共

記錄了M筆兩個人之間是朋友的資料。

但是沒有調查完所有人之間的關係，所以他們就用一種Heruistic的作法，只要A和B是朋友，

B和C也是朋友，朋友的朋友就是朋友，所以A和C也會是朋友，根據這種做法，他們可以

把所有有朋友關係的人都視為同一個社群，他們要計算出這些人中，社群人數最大的團體

一共有幾個人，請你寫程式幫忙他們計算該值。

Input

第一行有一個正整數表示有幾筆測試資料

每筆測試資料第一行有兩個正整數 N (1 <= N <= 30,000), M (0 <= M <= 500,000)

表示取樣的人數和記錄為朋友關係的資料筆數

接下來M行有兩個正整數A, B (1 <= A <= N, 1 <= B <= N, A != B)

表示第A個人和第B個人之間是朋友

Output

對於每筆測試資料，輸出這些人中，最大的社群有幾個人

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一些點的座標，把這些點用墨水畫直線連起來，使得所有的點最後都連在一起。你的任務是寫一個程式找出墨水畫出的長度最小是多少？

Input

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

每組測試資料的第1列有一個整數n（0< n <= 100），代表點的個數。接下來有n列代表這n個點的座標，每列有2個實數

輸入的第一列與第一組測試資料間空一列，各測試資料間亦空一列。請參考Sample Input

Output

對每一組測試資料輸出墨水畫出的長度最小是多少(四捨五入到小數點後第二位)。測試資料間亦請空一列。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

美國國家資源局使用衛星影像技術來調查森林中的樹種，你的任務就是根據輸入的樹木名稱，計算各樹種所佔的百分比。

Input

輸入的第1列有一個正整數n，代表以下有多少組測試資料。空一列之後才是測試資料。

每組測試資料含有一或多列（不會超過1000000列），每列有一樹木的名稱（最多30個字元）。測試資料間有一空白列。請參考Sample input

Output

對每一組測試資料，輸出各樹種名稱（樹種不會超過10000種，按數種名稱lexicographical order排列，也就是按照ascii碼大小）及所佔的比例（四捨五入到小數點後4位）。測試資料間亦請空一列。參考Sample Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

清華大學是個開放空間，所以常常會有很多狗移民進來，每隻狗都有攻擊性，假如有學生上nthu板抱怨校狗追車擋車亂叫或是咬人時，

懷生社就得要把校狗中最俱攻擊性的那隻狗抓去犬社關禁閉以懲戒他。

懷生社想要一個程式可以新增校狗資料，還有顯示最有攻擊性的校狗，以及當校狗被關禁閉時要從校狗名單移除，

他們本來想拜託布魯斯幫寫，可是布魯斯最近都在 tetris battle 所以沒空，請問你可以幫懷生社一個忙嗎？

Input

有四個指令

a: 新增校狗，後面會有一個名字跟數字代表狗的名字以及他的攻擊性( 校狗名字長最多10個英文字 ， 0<= 攻擊性數字 <100)

s: 觀察校狗，這時候請輸出最俱攻擊性校狗的名字

c: 捕捉校狗，請把最俱攻擊性的校狗關到犬社，移出校狗清單

e: 結束程式

指令最多 500,000 個

校狗名和攻擊性可能會相同，不過只要是不同時間進入學校的，他就是不同的狗 

在觀察校狗時，假如有多隻校狗攻擊性相同，那就輸出最晚進來的校狗

在捕捉校狗時，假如有多隻校狗攻擊性相同，那就捕捉最晚進來的校狗 

(老校狗比較熟悉學校較容易訓練)

Output

對於s指令輸出最俱攻擊性的校狗名字，如果清大無校狗就請輸出 Null

每一筆輸出各佔一行

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

你正計畫去歐洲旅行，但是你不知道該到哪些城市，所以你就向父母尋求建議。

你的母親說："兒子呀！你應該去巴黎、馬德里、里斯本和倫敦，而且要按照這樣的順序去玩。"

你的父親卻說："No,No,No, 你應該先去巴黎，然後里斯本，然後倫敦，最後才去馬德里。相信我。"

現在你陷入一個困境中了，如果你聽從父親的建議，那會傷了母親的心。如果你聽從了母親的建議，那會傷了父親的心。但是如果你不管他們的建議，更可能傷了他們2個人的心。

所以你決定盡可能的聽從他們2人的建議。所以你決定了：巴黎，里斯本，倫敦這樣順序的旅程，以滿足你的父母親。雖然這個決定使你只能到巴黎，里斯本，倫敦這3個城市去，而無法去馬德里。

如果你的父親建議："倫敦─巴黎─裡斯本─馬德里"這樣的旅程，那麼你將有2組組合："巴黎─裡斯本"及"巴黎─馬德里"來盡可能滿足你的父母。在這個情況下，你就只能去2個城市玩了。

你想要避免將來要面臨這樣的難題，如果他們建議的城市更多的話。所以你相要寫一個程式來幫助你。你將每個城市以一個字元來表示，這些字元包括大小寫英文字母，數字，以及空白字元。因此，你可以到63個城市可以去玩。但是請注意：你可能會到一個城市不止一次。

假如你以a代表巴黎，b代表馬德里，c代表里斯本，d代表倫敦，那你母親建議的旅程順序就是：abcd，而你父親建議的則是：acdb（上面的第一個例子）

程式必須輸入父母所建議的2個旅程，然後回答在盡可能滿足你父母的情況下，你最多可以去多少個城市旅行。

Input

輸入含有多組測試資料。每一組測試資料2列，分別代表你父母所建議的2個旅程（每列最多100個字元）。當遇到一列內容為單一"#"時，代表輸入結束。請參考Sample Input。

Output

每組測試資料輸出在盡可能滿足你父母的情況下，你最多可以去多少個城市旅行。請參考Sample Output。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

經過在百貨公司的一場血拼之後，小梅發現她身上的零錢共有17分（cent，美金貨幣單位，其他貨幣及面值請參考下方紅字部分），分別是1個dime，1個nickel，以及2個penny。隔天，小梅去便利商店買完東西後發現她身上的零錢恰好又是17分，這次是2個nickel及7個penny。小梅就在想，有幾種硬幣的組合可能湊成17分呢？經過仔細算算之後，發現共有6種。

你的問題就是：給一個金額，請你回答共有多少種硬幣組合的方式。

p.s 美國的零錢共有以下幾種硬幣以及其面值：

• penny, 1 cent
• nickel, 5 cents
• dime, 10 cents
• quarter, 25 cents
• half-dollar, 50 cents

Input

每組測試資料1列，有1個整數n（0 <= n <=30000），代表零錢的總金額。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。輸出格式為以下2種其中之一。

• There are m ways to produce n cents change.
• There is only 1 way to produce n cents change.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

長短腳叔叔在爬樓的時候為了避免跌倒，他的左腳只爬奇數個階梯(1, 3, 5, ...)，右腳只爬偶數個階梯(2, 4, 6, ...)，最多可以一次爬2K個階梯

當然身為一個正常的大叔，走路不會故意連續走兩個左腳或連續走兩個右腳，一定是一左一右交替著走，

在一個不知名的山上寺廟前有N階樓梯，請問他有幾種走法可以爬到山上？

舉例來說，假如N=5, K = 2

長短腳叔叔可以{左腳1階, 右腳4階}, {左腳3階, 右腳2階}, {右腳2階, 左腳3階}, {右腳2階, 左腳1階, 右腳2階}, {右腳4階, 左腳1階}

一共有5種走法

Input

輸入第一行包含一個整數T (T < 100) 表示接下來有幾筆測資。

接下來的每組測資都有兩個數字：

N (1 <= N <= 1000)表示有幾階樓梯, 

K (1 <= K <= 50)表示他左腳可以走{1, 3, 5, ..., 2K-1}階樓梯，右腳可以走{2, 4, 6, ... 2K}階樓梯

Output

每組輸出一行輸出有幾種走法可以爬到山上，因為走法可能太多，

假設一共有X種走法，請輸出X%12345678來表示所有走法

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在正方城這個城市走路是件相當容易的事，因為所有的道路都是像棋盤的線一樣，把城市切割成一塊一塊的正方形。大部分的十字路口都是安全的，行人可以直接通過。然而也有少數的十字路口比較危險，所以建有地下道或天橋供行人通過。

現在有一個人想要從位於城市西北方（也就是左上角）的公園十字路口到位於東南方（也就是右下角）的車站十字路口去。由於他是個懶惰的人，他不想要走比需要多一點點的路，也就是說他一定是往下或往右走，絕對不會往上或往左走。另外，他也不喜歡走天橋或地下道，所以他會避開這些危險的十字路口。你的任務就是幫他算一下從左上角走到右下角有多少種不同的走法。

以下的圖顯示出有4條東西向的道路，有5條南北向的道路，有3個十字路口是危險的。所以從左上角走到右下角要走(N-1)+(W-1) = 3+4 = 7格的距離，並且總共有4種不同的走法。

Input

輸入的第一列有一個正整數，代表以下有多少組測試資料。每組測試資料的第一列有2個整數W,N（均不大於100），W代表東西向道路的數目，N代表南北向道路的數目，編號如上圖所示。接下來的W列代表這W條東西向道路，每列的第一個數為這是第幾條東西向道路，接下來有0個或多個不等的數，代表某些南北向道路與這條東西向道路相交的十字路口是危險的。

輸入的第一列與第一組測試資料之間，以及各組測試資料之間均有一空白列，第一組Sample Input表示的路如上圖所示，請參考。

Output

每組測試資料輸出一列，為一個整數。代表這個人從左上角走到右下角有多少種不同的走法。

測試資料間亦請空一列。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Gustavo knows how to count, but he is now learning how write numbers. As he is a very good student, he already learned 1, 2, 3 and 4. But he didn't realize yet that 4 is different than 1, so he thinks that 4 is another way to write 1. Besides that, he is having fun with a little game he created himself: he make numbers (with those four digits) and sum their values. For instance:

132 = 1 + 3 + 2 = 6
112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (remember that Gustavo thinks that 4 = 1)
After making a lot of numbers in this way, Gustavo now wants to know how much numbers he can create such that their sum is a number n. For instance, for n = 2 he noticed that he can make 5 numbers: 11, 14, 41, 44 and 2 (he knows how to count them up, but he doesn't know how to write five). However, he can't figure it out for n greater than 2. So, he asked you to help him.

Input

Input will consist on an arbitrary number of sets. Each set will consist on an integer n such that 1 <= n <= 1000. You must read until you reach the end of file.

Output

For each number read, you must output another number (on a line alone) stating how much numbers Gustavo can make such that the sum of their digits is equal to the given number.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Bart's sister Lisa has created a new civilization on a two-dimensional grid. At the outset each grid location may be occupied by one of three life forms: Rocks, Scissors, or Papers. Each day, differing life forms occupying horizontally or vertically adjacent grid locations wage war. In each war, Rocks always defeat Scissors, Scissors always defeat Papers, and Papers always defeat Rocks. At the end of the day, the victor expands its territory to include the loser's grid position. The loser vacates the position.
Your job is to determine the territory occupied by each life form after n days. The first line of input contains t, the number of test cases. Each test case begins with three integers not greater than 100: r and c, the number of rows and columns in the grid, and n. The grid is represented by the r lines that follow, each with c characters. Each character in the grid is R, S, or P, indicating that it is occupied by Rocks, Scissors, or Papers respectively.

For each test case, print the grid as it appears at the end of the nth day. Leave an empty line between the output for successive test cases.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are Ash, the famous Pokemon trainer. To become the greatest Pokemon master, you travel through regions battling against gym leaders and entering Pokemon League competitions. With your well-trained Pikachu, Squirtle and Bulbasaur, you have already captured six badges! What a marvellous performance!

Now, you are walking through the Enchanted Forest, where the most powerful Pokemons live... No, not those giant dragons; we are actually talking about Jigglypuffs. A Jigglypuff is a normal-type Balloon Pokemon, with a round, balloon-like body, a tuft of fur on its forehead, and stubby arms and legs. What's so powerful of them? Well, Jigglypuff has a well-regarded singing voice, and its most popular attack is to sing its opponent to sleep! Therefore, it is always a good idea to find a route avoiding places wherever you might hear the Jigglypuffs' lullaby.

Let us model the situation as follows: we shall treat the forest as a rectangular grid formed by paths which are 1 unit apart. Your starting position is at the top left corner of the grid (1, 1), and you will leave the forest at the lower right corner (R, C). There might be blocked areas which you are not allowed to trespass through. Jigglypuffs might be present at some intersections. The loudness L of each Jigglypuff is given, which means that places whose Euclidean distance is no more than L units away from the Jigglypuff are considered "dangerous" and should be avoided.

Input

Input consists of several test cases. Each test begins with two integers R and C (1 ≤ R, C ≤ 200), the number of rows and columns in the grid map. Then comes an integer m, followed by m lines each giving the coordinates of a blocked position. Next there is an integer n (0 ≤ n ≤ 100), the number of Jigglypuffs in the forest. The following n lines each gives the position of a Jigglypuff and its loudness L (1 ≤ L ≤ 100).

Input ends with a test case where R=0 and C=0. You must not process this test case.

Output

For each case, if some "dangerous" places are unavoidable, print "Impossible." Otherwise, give the length of the shortest path to get out of the forest safely.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.

A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 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 absence of oil, or `@', representing an oil pocket.

Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are to write a program that has to generate all possible words from a given set of letters.

Example: Given the word "abc", your program should - by exploring all different combination of the three letters - output the words "abc", "acb", "bac", "bca", "cab" and "cba".

In the word taken from the input file, some letters may appear more than once. For a given word, your program should not produce the same word more than once, and the words should be output in alphabetically ascending order.

Input

The input file consists of several words. The first line contains a number giving the number of words to follow. Each following line contains one word. A word consists of uppercase or lowercase letters from A to Z. Uppercase and lowercase letters are to be considered different.

Output

For each word in the input file, the output file should contain all different words that can be generated with the letters of the given word. The words generated from the same input word should be output in alphabetically ascending order. An upper case letter goes before the corresponding lower case letter.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Morse code is a method for long-distance transmission of textual information without using the usual symbols. Instead information is represented with a simpler, binary, alphabet composed of short and long beeps. The short beep is called dih, and the long beep is called dah. For instance, the code for the letter O is dah dah dah (three long beeps). Actually, because the codification is not prefix-free, there is also a third symbol, which is silence. The code between two letters is a simple silence, the code between two words is a double silence.

You have been assigned the job to translate a message in Morse code. The signal has already been digitalized in the following fashion: dih is represented by a dot (.), dah is represented by a dash (-). Simple and double silences are represented by a single space character and two space characters respectively.

The following table represents the Morse code of all the characters that your program need to be able to handle.

Input

The first line of input gives the number of cases, T (1 ≤ T ≤ 10). T test cases follow. Each one is a sequence of dot, dash and space characters. Two messages are separated by a newline. The maximum length of a message is 2000.

Output

The output is comprised of one paragraph for each message. The paragraph corresponding to the n-th message starts with the header Message #n, on a line on its own. Each decoded sentence of the message appears then successively on a line of its own. Two paragraphs are separated by a blank line. The sentences shall be printed in uppercase.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Football the most popular sport in the world (americans insist to call it "Soccer", but we will call it "Football"). As everyone knows, Brasil is the country that have most World Cup titles (four of them: 1958, 1962, 1970 and 1994). As our national tournament have many teams (and even regional tournaments have many teams also) it's a very hard task to keep track of standings with so many teams and games played!

So, your task is quite simple: write a program that receives the tournament name, team names and games played and outputs the tournament standings so far.

A team wins a game if it scores more goals than its oponent. Obviously, a team loses a game if it scores less goals. When both teams score the same number of goals, we call it a tie. A team earns 3 points for each win, 1 point for each tie and 0 point for each loss.

Teams are ranked according to these rules (in this order):

1. Most points earned.
2. Most wins.
3. Most goal difference (i.e. goals scored - goals against)
4. Most goals scored.
5. Less games played.
6. Lexicographic order.

Input

The first line of input will be an integer N in a line alone (0 < N < 1000). Then, will follow N tournament descriptions. Each one begins with the tournament name, on a single line. Tournament names can have any letter, digits, spaces etc. Tournament names will have length of at most 100. Then, in the next line, there will be a number T (1 < T <= 30), which stands for the number of teams participating on this tournament. Then will follow T lines, each one containing one team name. Team names may have any character that have ASCII code greater than or equal to 32 (space), except for '#' and '@' characters, which will never appear in team names. No team name will have more than 30 characters.

Following to team names, there will be a non-negative integer G on a single line which stands for the number of games already played on this tournament. G will be no greater than 1000. Then, G lines will follow with the results of games played. They will follow this format:

team_name_1#goals1@goals2#team_name_2 

For instance, the following line:

Team A#3@1#Team B 

Means that in a game between Team A and Team B, Team A scored 3 goals and Team B scored 1. All goals will be non-negative integers less than 20. You may assume that there will not be inexistent team names (i.e. all team names that appear on game results will have apperead on the team names section) and that no team will play against itself.

Output

For each tournament, you must output the tournament name in a single line. In the next T lines you must output the standings, according to the rules above. Notice that should the tie-breaker be the lexographic order, it must be done case insenstive. The output format for each line is shown bellow:

[a]) Team_name [b]p, [c]g ([d]-[e]-[f]), [g]gd ([h]-[i])

Where:

[a] = team rank
[b] = total points earned
[c] = games played
[d] = wins
[e] = ties
[f] = losses
[g] = goal difference
[h] = goals scored
[i] = goals against

There must be a single blank space between fields and a single blank line between output sets. See the sample output for examples.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Background

Robotics, robot motion planning, and machine learning are areas that cross the boundaries of many of the subdisciplines that comprise Computer Science: artificial intelligence, algorithms and complexity, electrical and mechanical engineering to name a few. In addition, robots as ``turtles'' (inspired by work by Papert, Abelson, and diSessa) and as ``beeper-pickers'' (inspired by work by Pattis) have been studied and used by students as an introduction to programming for many years.

This problem involves determining the position of a robot exploring a pre-Columbian flat world.

The Problem

Given the dimensions of a rectangular grid and a sequence of robot positions and instructions, you are to write a program that determines for each sequence of robot positions and instructions the final position of the robot.

A robot position consists of a grid coordinate (a pair of integers: x-coordinate followed by y-coordinate) and an orientation (N,S,E,W for north, south, east, and west). A robot instruction is a string of the letters 'L', 'R', and 'F' which represent, respectively, the instructions:

Left: the robot turns left 90 degrees and remains on the current grid point.
Right: the robot turns right 90 degrees and remains on the current grid point.
Forward: the robot moves forward one grid point in the direction of the current orientation and mantains the same orientation.

The direction North corresponds to the direction from grid point (x,y) to grid point (x,y+1).

Since the grid is rectangular and bounded, a robot that moves ``off'' an edge of the grid is lost forever. However, lost robots leave a robot ``scent'' that prohibits future robots from dropping off the world at the same grid point. The scent is left at the last grid position the robot occupied before disappearing over the edge. An instruction to move ``off'' the world from a grid point from which a robot has been previously lost is simply ignored by the current robot.

Input

The first line of input is the upper-right coordinates of the rectangular world, the lower-left coordinates are assumed to be 0,0.

The remaining input consists of a sequence of robot positions and instructions (two lines per robot). A position consists of two integers specifying the initial coordinates of the robot and an orientation (N,S,E,W), all separated by white space on one line. A robot instruction is a string of the letters 'L', 'R', and 'F' on one line.

Each robot is processed sequentially, i.e., finishes executing the robot instructions before the next robot begins execution.

Input is terminated by end-of-file.

You may assume that all initial robot positions are within the bounds of the specified grid. The maximum value for any coordinate is 50. All instruction strings will be less than 100 characters in length.

Output

For each robot position/instruction in the input, the output should indicate the final grid position and orientation of the robot. If a robot falls off the edge of the grid the word ``LOST'' should be printed after the position and orientation.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.


Assumptions:

number of tracks on the CD. does not exceed 20
no track is longer than N minutes
tracks do not repeat
length of each track is expressed as an integer number
N is also integer

Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD

Input

Any number of lines. Each one contains value N, (after space) number of tracks and durations of the tracks. For example from first line in sample data: N=5, number of tracks=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes

Output

Set of tracks (and durations) which are the correct solutions and string ``sum:" and sum of duration times.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.

Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Calvin likes to lie in a field and look at the night sky. Since he doesn’t know any real star constellations, he makes them up: if two stars are close to each other, they must belong to the same constellation. He wants to name them all, but fears to run out of names. Can you help him and count how many constellations there are in the sky?

Two stars belong to the same constellation if distance between their projections on a two-dimensional sky plane isn’t more than D units.

Input

There is a number of tests T (T ≤ 50) on the first line. Each test case contains the number of stars N (0 ≤ N ≤ 1000) a real distance D (0.00 ≤ D ≤ 1000.00). Next N lines have a pair of real coordinates X Y (−1000.00 ≤ X, Y ≤ 1000.00) for each star. Real numbers in the input will have at most 2 digits after a decimal point.

Output

For each test case output a single line "Case T: N". Where T is the test case number (starting from 1) and N is the number of constellations.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A city is served by a number of fire stations. Some residents have complained that the distance from their houses to the nearest station is too far, so a new station is to be built. You are to choose the location of the fire station so as to reduce the distance to the nearest station from the houses of the disgruntled residents.

The city has up to 500 intersections, connected by road segments of various lengths. No more than 20 road segments intersect at a given intersection. The location of houses and firestations alike are considered to be at intersections (the travel distance from the intersection to the actual building can be discounted). Furthermore, we assume that there is at least one house associated with every intersection. There may be more than one firestation per intersection.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of input contains two positive integers: f,the number of existing fire stations (f <= 100) and i, the number of intersections (i <= 500). The intersections are numbered from 1 to i consecutively. f lines follow; each contains the intersection number at which an existing fire station is found. A number of lines follow, each containing three positive integers: the number of an intersection, the number of a different intersection, and the length of the road segment connecting the intersections. All road segments are two-way (at least as far as fire engines are concerned), and there will exist a route between any pair of intersections.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

You are to output a single integer: the lowest intersection number at which a new fire station should be built so as to minimize the maximum distance from any intersection to the nearest fire station.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Disky and Sooma, two of the biggest mega minds of Bangladesh went to a far country. They ate, coded and wandered around, even in their holidays. They passed several months in this way. But everything has an end. A holy person, Munsiji came into their life. Munsiji took them to derby (horse racing). Munsiji enjoyed the race, but as usual Disky and Sooma did their as usual task instead of passing some romantic moments. They were thinking- in how many ways a race can finish! Who knows, maybe this is their romance!

In a race there are n horses. You have to output the number of ways the race can finish. Note that, more than one horse may get the same position. For example, 2 horses can finish in 3 ways.

1. Both first
2. horse1 first and horse2 second
   
3. horse2 first and horse1 second
   

Input

Input starts with an integer T (<=1000), denoting the number of test cases. Each case starts with a line containing an integer n ( 1 <= n <= 1000 ).

Output

For each case, print the case number and the number of ways the race can finish. The result can be very large, print the result modulo 10056.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A common word puzzle found in many newspapers and magazines is the word transformation. By taking a starting word and successively altering a single letter to make a new word, one can build a sequence of words which changes the original word to a given end word. For instance, the word ``spice'' can be transformed in four steps to the word ``stock'' according to the following sequence: spice, slice, slick, stick, stock. Each successive word differs from the previous word in only a single character position while the word length remains the same.

Given a dictionary of words from which to make transformations, plus a list of starting and ending words, your team is to write a program to determine the number of steps in the shortest possible transformation.

Input

The first line of the input is an integer N, indicating the number of test set that your correct program should test followed by a blank line. Each test set will have two sections. The first section will be the dictionary of available words with one word per line, terminated by a line containing an asterisk (*) rather than a word. There can be up to 200 words in the dictionary; all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.

Following the dictionary are pairs of words, one pair per line, with the words in the pair separated by a single space. These pairs represent the starting and ending words in a transformation. All pairs are guaranteed to have a transformation using the dictionary given. The starting and ending words will appear in the dictionary.

Two consecutive input set will separated by a blank line.

The output should contain one line per word pair for each test set, and must include the starting word, the ending word, and the number of steps in the shortest possible transformation, separated by single spaces. Two consecutive output set will be separated by a blank line.

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Russian nesting dolls are brightly painted hollow wooden figures. The dolls in a set have roughly the same shape, typically humanoid, but different sizes. When the set is assembled, the biggest doll contains the second-biggest doll, the second-biggest contains the third-biggest, and so on.

We can approximate the shape of a doll as a cylinder of height h, diameter d, and wall thickness w. Such a doll would have a hollow of height h-2w and diameter d-2w.

Boris and Natasha each has a set of dolls. The sets are nearly identical; each has the same number of dolls, which look the same but differ in their dimensions. Last night Boris and Natasha were playing with their dolls and left them in the living room. Their mother tidied them away, dumping them all in one box. Can you help Boris and Natasha separate their sets of dolls?

Standard Input will consist of several test cases. The first line of each test case will contain n, the number of dolls in each set (1 < n <= 100). 2n lines follow; each gives the dimensions, h, d, w of a different doll (h,d >= 2w > 0). A line containing 0 follows the last test case.

For each test case, separate the dolls into two sets of nesting dolls such that, within each set, the dolls fit within each other, standing straight up, as described above. The first n lines of output should give the dimensions of the dolls in one set, in decreasing order by height. The next line should contain a single hyphen, "-". The next n lines should give the dimensions of the dolls in the second set, also in decreasing order by height. There will always be a solution. If there are many solutions, any will do. Output an empty line between test cases.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In A.D. 2100, aliens came to Earth. They wrote a message in a cryptic language, and next to it they wrote a series of symbols. We've come to the conclusion that the symbols indicate a number: the number of seconds before war begins!

Unfortunately we have no idea what each symbol means. We've decided that each symbol indicates one digit, but we aren't sure what each digit means or what base the aliens are using. For example, if they wrote "ab2ac999", they could have meant "31536000" in base 10 -- exactly one year -- or they could have meant "12314555" in base 6 -- 398951 seconds, or about four and a half days. We are sure of three things: the number is positive; like us, the aliens will never start a number with a zero; and they aren't using unary (base 1).

Your job is to determine the minimum possible number of seconds before war begins.

Input

The first line of input contains a single integer, T. T test cases follow. Each test case is a string on a line by itself. The line will contain only characters in the 'a' to 'z' and '0' to '9' ranges (with no spaces and no punctuation), representing the message the aliens left us. The test cases are independent, and can be in different bases with the symbols meaning different things.

1 ≤ T ≤ 100
The answer will never exceed 10¹⁸

1 ≤ the length of each line < 61

Output

For each test case, output a line in the following format:

Case #X: V
Where X is the case number (starting from 1) and V is the minimum number of seconds before war begins.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Geometrically, any square has a unique, well-defined centre point. On a grid this is only true if the sides of the square are an odd number of points long. Since any odd number can be written in the form 2k+1, we can characterise any such square by specifying k, that is we can say that a square whose sides are of length 2k+1 has size k. Now define a pattern of squares as follows.

The largest square is of size k (that is sides are of length 2k+1) and is centred in a grid of size 1024 (that is the grid sides are of length 2049).
The smallest permissible square is of size 1 and the largest is of size 512, thus .
All squares of size k > 1 have a square of size k div 2 centred on each of their 4 corners. (Div implies integer division, thus 9 div 2 = 4).
The top left corner of the screen has coordinates (0,0), the bottom right has coordinates (2048, 2048).
Hence, given a value of k, we can draw a unique pattern of squares according to the above rules. Furthermore any point on the screen will be surrounded by zero or more squares. (If the point is on the border of a square, it is considered to be surrounded by that square). Thus if the size of the largest square is given as 15, then the following pattern would be produced.



Write a program that will read in a value of k and the coordinates of a point, and will determine how many squares surround the point.

Input

Input will consist of a series of lines. Each line will consist of a value of k and the coordinates of a point. The file will be terminated by a line consisting of three zeroes (0 0 0).

Output will consist of a series of lines, one for each line of the input. Each line will consist of the number of squares containing the specified point, right justified in a field of width 3.

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have n marbles of different colors which are distributed in 2 boxes. In each move you can move one marble from one box into another. You have to move the marbles in such a way that first box contains each combination of marble sets exactly once. There are 2n combinations of marbles.
For example you have 4 marbles. Box 1 has marbles of color 1 and 3. And Box 2 has marbles of color 2 and 4. Then the solution can be as follows.

Input

Input contains multiple test cases. The first line of the input contains T(1≤T≤20) the number of test cases. Each test case consists of 2 lines. The first line contains n(1≤n≤10) and b1(0≤b1≤n). n is the number of marbles and b1 is the number of marbles in the first box. The next line contains b1 integer the indices of the marbles which are in the first box. All of these numbers are distinct and between 1 and n inclusive. The rest of the n-b1 marbles are in 2nd box.

Output

For each test case output contains 2n lines. The first 2n-1 lines contains the moves( see the sample output for formatting). The last line is blank. In case there are multiple solutions any valid solution is acceptable.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A permutation of n+1 is a bijective function of the initial n+1 natural numbers: 0, 1, ... n. A permutation p is called antiarithmetic if there is no subsequence of it forming an arithmetic progression of length bigger than 2, i.e. there are no three indices 0 ≤ i < j < k < n such that (pi, pj, pk) forms an arithmetic progression.


For example, the sequence (2, 0, 1, 4, 3) is an antiarithmetic permutation of 5. The sequence (0, 5, 4, 3, 1, 2) is not an antiarithmetic permutation of 6 as its first, fifth and sixth term (0, 1, 2) form an arithmetic progression; and so do its second, fourth and fifth term (5, 3, 1).

Your task is to generate an antiarithmetic permutation of n.

Each line of the input file contains a natural number 3 ≤ n ≤ 10000. The last line of input contains 0 marking the end of input. For each n from input, produce one line of output containing an (any will do) antiarithmetic permutation of n in the format shown below.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A conveyor belt has a number of vessels of different capacities each filled to brim with milk. The milk from conveyor belt is to be filled into 'm' containers. The constraints are:

• Whenever milk from a vessel is poured into a container, the milk in the vessel must be completely poured into that container only. That is milk from same vessel can not be poured into different containers.
• The milk from the vessel must be poured into the container in order which they appear in the conveyor belt. That is, you cannot randomly pick up a vessel from the conveyor belt and fill the container.
• The ith container must be filled with milk only from those vessels that appear earlier to those that fill jth container, for all i < j

Given the number of containers 'm', you have to fill the containers with milk from all the vessels, without leaving any milk in the vessel. The containers need not necessarily have same capacity. You are given the liberty to assign any possible capacities to them. Your job is to find out the minimal possible capacity of the container which has maximal capacity. (If this sounds confusing, read down for more explanations.)

Input

A single test case consist of 2 lines. The first line specifies 1<=n<=1000 the number of vessels in the conveyor belt and then 'm' which specifies the number of containers to which, you have to transfer the milk. (1 <= m <= 1000000) .The next line contains, the capacity 1<=c<=1000000 of each vessel in order which they appear in the conveyor belt. Note that, milk is filled to the brim of any vessel. So the capacity of the vessel is equal to the amount of milk in it. There are several test cases terminated by EOF.

Output

For each test case, print the minimal possible capacity of the container with maximal capacity. That is there exists a maximal capacity of the containers, below which you can not fill the containers without increasing the number of containers. You have to find such capacity and print it on a single line.

Explanation of the output:

Here you are given 3 vessels at your disposal, for which you are free to assign the capacity. You can transfer, {1 2 3} to the first container, {4} to the second, {5} to third. Here the maximal capacity of the container is the first one which has a capacity of 6. Note that this is optimal too. That is, you can not have the maximal container, have a capacity, less than 6 and still use 3 containers only and fill the containers with all milk.

For the second one, the optimal way is, {4 78} into the first container, and {9} to the second container. So the minimal value of the maximal capacity is 82. Note that {4} to first container and {78 9} to the second is not optimal as, there exists a way to have an assignement of maximal capacity to 82, as opposed to 87 in this case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as
P Q
where P is the number of prison cells and Q is the number of prisoners to be released.
This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.

1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.

1 ≤ P ≤ 10000
1 ≤ Q ≤ 100

Output

For each test case, output one line in the format

Case #X: C
where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:

The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions . A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.

Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.

Input

The input file will contain one or more test cases. The first line of each test case contains an integer n, representing the number of different blocks in the following data set. The maximum value for n is 30. Each of the next n lines contains three integers representing the values , and .

Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height"

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have been given the job of forming the quiz teams for the next ‘MCA CPCI Quiz Championship’. There are 2 × N students interested to participate and you have to form N teams, each team consisting of two members. Since the members have to practice together, all the students want their member’s house as near as possible. Let x₁ be the distance between the houses of group 1, x₂ be the distance between the houses of group 2 and so on. You have to make sure the summation (x₁ + x₂ + x₃ + … + x_n) is minimized.

Input

There will be many cases in the input file. Each case starts with an integer N (N ≤ 8). The next 2 × N lines will given the information of the students. Each line starts with the student’s name, followed by the x coordinate and then the y coordinate. Both x, y are integers in the range 0 to 1000. Students name will consist of lowercase letters only and the length will be at most 20.

Input is terminated by a case where N is equal to 0.

Output

For each case, output the case number followed by the summation of the distances, rounded to 2 decimal places. Follow the sample for exact format.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given several segments of line (int the X axis) with coordinates [L_i,R_i]. You are to choose the minimal amount of them, such they would completely cover the segment [0,M].

Input

The first line is the number of test cases, followed by a blank line.

Each test case in the input should contains an integer M(1<=M<=5000), followed by pairs "L_i R_i"(|L_i|, |R_i|<=50000, i<=100000), each on a separate line. Each test case of input is terminated by pair "0 0".

Each test case will be separated by a single line.

Output

For each test case, in the first line of output your programm should print the minimal number of line segments which can cover segment [0,M]. In the following lines, the coordinates of segments, sorted by their left end (L_i), should be printed in the same format as in the input. Pair "0 0" should not be printed. If [0,M] can not be covered by given line segments, your programm should print "0"(without quotes).

Print a blank line between the outputs for two consecutive test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The International Space Station contains many centrifuges in its labs. Each centrifuge will have some number (C) of chambers each of which can contain 0, 1, or 2 specimens. You are to write a program which assigns all S specimens to the chambers such that no chamber contains more than 2 specimens and the following expression for IMBALANCE is minimized.


where:

CM_i is the Chamber Mass of chamber i and is computed by summing the masses of the specimens assigned to chamber i.
AM is the Average Mass of the chambers and is computed by dividing the sum of the masses of all specimens by the number of chambers (C).

Input

Input to this program will be a file with multiple sets of input. The first line of each set will contain two numbers. The first number (1<=C<=5) defines the number of chambers in the centrifuge and the second number (1<=S<=2C  ) defines the number of specimens in the input set. The second line of input will contain S integers representing the masses of the specimens in the set. Each specimen mass will be between 1 and 1000 and will be delimited by the beginning or end of the line and/or one or more blanks.

Output

For each input set, you are to print a line specifying the set number (starting with 1) in the format "Set #X" where "X" is the set number.

The next C lines will contain the chamber number in column 1, a colon in column number 2, and then the masses of the specimens your program has assigned to that chamber starting in column 4. The masses in your output should be separated by exactly one blank.

Your program should then print ``IMBALANCE = X" on a line by itself where X is the computed imbalance of your specimen assignments printed to 5 digits of precision to the right of the decimal.

The final line of output for each set should be a blank line. (Follow the sample output format.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an undirected weighted graph G , you should find one of spanning trees specified as follows.

The graph G is an ordered pair (V, E) , where V is a set of vertices {v₁, v₂,..., v_n} and E is a set of undirected edges {e₁, e₂,..., e_m} . Each edge e E has its weight w(e) .

A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with n - 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the n - 1 edges of T .

For example, a graph G in Figure 5(a) has four vertices {v₁, v₂, v₃, v₄} and five undirected edges {e₁, e₂, e₃, e₄, e₅} . The weights of the edges are w(e₁) = 3 , w(e₂) = 5 , w(e₃) = 6 , w(e₄) = 6 , w(e₅) = 7 as shown in Figure 5(b).

=6in

There are several spanning trees for G . Four of them are depicted in Figure 6(a)∼(d). The spanning tree T_a in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree T_a is 4. The slimnesses of spanning trees T_b , T_c and T_d shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree T_d in Figure 6(d) is one of the slimmest spanning trees whose slimness is 1.

Your job is to write a program that computes the smallest slimness.

Input

The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.

n m
a₁ b₁ w₁

a_m b_m w_m

Every input item in a dataset is a non-negative integer. Items in a line are separated by a space.

n is the number of the vertices and m the number of the edges. You can assume 2n100 and 0mn(n - 1)/2 . a_k and b_k (k = 1,..., m) are positive integers less than or equal to n , which represent the two vertices v_ak and v_bk connected by the k -th edge e_k . w_k is a positive integer less than or equal to 10000, which indicates the weight of e_k . You can assume that the graph G = (V, E) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).

Output

For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, `-1' should be printed. An output should not contain extra characters.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a small city called Iokh, a train service, Airport-Express, takes residents to the airport more quickly than other transports. There are two types of trains in Airport-Express, the Economy-Xpress and the Commercial-Xpress. They travel at different speeds, take different routes and have different costs.

Jason is going to the airport to meet his friend. He wants to take the Commercial-Xpress which is supposed to be faster, but he doesn't have enough money. Luckily he has a ticket for the Commercial-Xpress which can take him one station forward. If he used the ticket wisely, he might end up saving a lot of time. However, choosing the best time to use the ticket is not easy for him.

Jason now seeks your help. The routes of the two types of trains are given. Please write a program to find the best route to the destination. The program should also tell when the ticket should be used.

Input

The input consists of several test cases. Consecutive cases are separated by a blank line.

The first line of each case contains 3 integers, namely N, S and E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ N), which represent the number of stations, the starting point and where the airport is located respectively.

There is an integer M (1 ≤ M ≤ 1000) representing the number of connections between the stations of the Economy-Xpress. The next M lines give the information of the routes of the Economy-Xpress. Each consists of three integers X, Y and Z (X, Y ≤ N, 1 ≤ Z ≤ 100). This means X and Y are connected and it takes Z minutes to travel between these two stations.

The next line is another integer K (1 ≤ K ≤ 1000) representing the number of connections between the stations of the Commercial-Xpress. The next K lines contain the information of the Commercial-Xpress in the same format as that of the Economy-Xpress.

All connections are bi-directional. You may assume that there is exactly one optimal route to the airport. There might be cases where you MUST use your ticket in order to reach the airport.

Output

For each case, you should first list the number of stations which Jason would visit in order. On the next line, output "Ticket Not Used" if you decided NOT to use the ticket; otherwise, state the station where Jason should get on the train of Commercial-Xpress. Finally, print the total time for the journey on the last line. Consecutive sets of output must be separated by a blank line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.
Your task is to determine, given the layout of some domino tiles, the minimum number of dominos that must be knocked down by hand in order for all of the dominos to fall.

Input

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.

Output

For each test case, output a line containing one integer, the minimum number of dominos that must be knocked over by hand in order for all the dominos to fall.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are to find the length of the shortest path from the top to the bottom of a grid covering specified points along the way.

More precisely, you are given an n by n grid, rows 1...n and columns 1…n (1 ≤ n ≤ 20000). On each row i, two points L(i) and R(i) are given where 1 ≤ L(i) ≤ R(i) ≤ n. You are to find the shortest distance from position (1, 1), to (n, n) that visits all of the given segments in order. In particular, for each row i, all the points
(i, L(i)); (i, L(i) + 1), (i, L(i) + 2), …, (i, R(i)),
must be visited. Notice that one step is taken when dropping down between consecutive rows. Note that you can only move left, right and down (you cannot move up a level). On finishing the segment on row n, you are to go to position (n, n), if not already there. The total distance covered is then reported.

Input

Input file contains maximum 10 sets of inputs. The description of each set is given below:

The first line of each set consists of an integer n, the number of rows/columns on the grid. On each of the next n lines, there are two integers L(i) followed by R(i) (where 1 ≤ L(i) ≤ R(i) ≤ n).

Input is terminated by a set whose value of n is zero. This input should not be processed.

Output

For each set of input output is one integer, which is the length of the (shortest) path from (1, 1) to (n, n) which covers all intervals L(i), R(i).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their discovery of a new, highly noise resistant, antenna. It is called 4DAir, and comes in four types. Each type can only transmit and receive signals in a direction aligned with a (slightly skewed) latitudinal and longitudinal grid, because of the interacting electromagnetic field of the earth. The four types correspond to antennas operating in the directions north, west, south, and east, respectively. Below is an example picture of places of interest, depicted by twelve small rings, and nine 4DAir antennas depicted by ellipses covering them.

Obviously, it is desirable to use as few antennas as possible, but still provide coverage for each place of interest. We model the problem as follows: Let A be a rectangular matrix describing the surface of Sweden, where an entry of A either is a point of interest, which must be covered by at least one antenna, or empty space. Antennas can only be positioned at an entry in A. When an antenna is placed at row r and column c, this entry is considered covered, but also one of the neighbouring entries (c+1,r),(c,r+1),(c-1,r), or (c,r-1), is covered depending on the type chosen for this particular antenna. What is the least number of antennas for which there exists a placement in A such that all points of interest are covered?

Input

On the first row of input is a single positive integer n, specifying the number of scenarios that follow. Each scenario begins with a row containing two positive integers h and w, with 1<h<40 and 0<w<10. Thereafter is a matrix presented, describing the points of interest inSweden in the form of h lines, each containing w characters from the set [‘*’,’o’]. A ‘*’-character symbolises a point of interest, whereas a‘o’-character represents open space.

Output

For each scenario, output the minimum number of antennas necessary to cover all ‘*’-entries in the scenario’s matrix, on a row of its own.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You, a programmer of an important software house, have been fired because you didn't solve an important problem that was assigned to you. You are very furious and want to take revenge on your boss, breaking the communication between his computer and the central server.

The computer of your boss and the central server are in the same network, which is composed of many machines (computers) and wires linking pairs of those machines. There is at most one wire between any pair of machines and there can be pairs of machines without a wire between them.


To accomplish your objective, you can destroy machines and wires, but you can't destroy neither the computer of your boss nor the central server, because those machines are monitored by security cameras. You have estimated the cost of blowing up each machine and the cost of cutting each wire in the network.


You want to determine the minimum cost of interrupting the communication between your boss' computer and the central server. Two computers A and B can communicate if there is a sequence of undestroyed machines x1,..., xn such that x1 = A , xn = B and xi is linked with xi+1 with an uncut wire (for each 1<=i<=n-1).

Input

The input consists of several test cases. Each test case is represented as follows:

A line with two integers M and W ( 2<=M<=50 , 0<=W<=1000 ), representing (respectively) the number of machines and the number of wires in the network.
M - 2 lines, one per machine (different from the boss' machine and the central server), containing the following information separated by spaces:
An integer i ( 2<=i<=M - 1 ) with the identifier of the machine. Assume that the boss' machine has id 1 and that the central server has id M .
An integer c ( 0<=c<=100000 ) specifying the cost of destroying the machine.
W lines, one per wire, containing the following information separated by spaces:
Two integers j and k ( 1 <= j < k <= M ) specifying the identifiers of the machines linked by the wire. Remember that the wire is bidirectional.
An integer d ( 0<=d<=100000 ) specifying the cost of cutting the wire.

The end of the input is specified by a line with the string ``0 0''.

Suppose that the machines have distinct identifiers.

Output

For each test case, print a line with the minimum cost of interrupting the communication between the computer of your boss and the central server.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A technique used in early multiprogramming operating systems involved partitioning the available primary memory into a number of regions with each region having a fixed size, different regions potentially having different sizes. The sum of the sizes of all regions equals the size of the primary memory.

Given a set of programs, it was the task of the operating system to assign the programs to different memory regions, so that they could be executed concurrently. This was made difficult due to the fact that the execution time of a program might depend on the amount of memory available to it. Every program has a minimum space requirement, but if it is assigned to a larger memory region its execution time might increase or decrease.

In this program, you have to determine optimal assignments of programs to memory regions. Your program is given the sizes of the memory regions available for the execution of programs, and for each program a description of how its running time depends on the amount of memory available to it. Your program has to find the execution schedule of the programs that minimizes the average turnaround time for the programs. An execution schedule is an assignment of programs to memory regions and times, such that no two programs use the same memory region at the same time, and no program is assigned to a memory region of size less than its minimum memory requirement. The turnaround time of the program is the difference between the time when the program was submitted for execution (which is time zero for all programs in this problem), and the time that the program completes execution.

Input

The input data will contain multiple test cases. Each test case begins with a line containing a pair of integers m and n. The number m specifies the number of regions into which primary memory has been partitioned (1 ≤ m ≤ 10), and n specifies the number of programs to be executed (1 ≤ n ≤ 50).
The next line contains m positive integers giving the sizes of the m memory regions. Following this are n lines, describing the time-space tradeoffs for each of the n programs. Each line starts with a positive integer k (k ≤ 10), followed by k pairs of positive integers s₁, t₁, s₂, t₂, ..., s_k, t_k, that satisfy s_i < s_i + 1 for 1 ≤ i < k. The minimum space requirement of the program is s₁, i.e. it cannot run in a partition of size less than this number. If the program runs in a memory partition of size s, where s_i ≤ s < s_i + 1 for some i, then its execution time will be t_i. Finally, if the programs runs in a memory partition of size s_k or more, then its execution time will be t_k.

A pair of zeroes will follow the input for the last test case.

You may assume that each program will execute in exactly the time specified for the given region size, regardless of the number of other programs in the system. No program will have a memory requirement larger than that of the largest memory region.

Output

For each test case, first display the case number (starting with 1 and increasing sequentially). Then print the minimum average turnaround time for the set of programs with two digits to the right of the decimal point. Follow this by the description of an execution schedule that achieves this average turnaround time. Display one line for each program, in the order they were given in the input, that identifies the program number, the region in which it was executed (numbered in the order given in the input), the time when the program started execution, and the time when the program completed execution. Follow the format shown in the sample output, and print a blank line after each test case.
If there are multiple program orderings or assignments to memory regions that yield the same minimum average turnaround time, give one of the schedules with the minimum average turnaround time.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Modern graphic computer programs can, among other, even more stunning capabilities, fill a closed region. Though not all of them can protect the user from accidentally choosing to fill the background rather than the inner part. Besides being a channel hopper at home your boss' favourite hobby is colouring the pictures, you cannot protest long about adding this magnificent protection feature to his graphic program.


This means that your job is to write a program, which determines whether a point belong to a polygon, given the array of its vertices.


To make life a bit simpler you may assume that:

all edges of the polygon are vertical or horizontal segments
(1) lengths of all the edges of the polygon are even integer numbers
(2) co-ordinates of at least one vertex are odd integer numbers
(3) both co-ordinates of any vortex cannot be divisible by 7 at the same time
(4) the investigated point P has both co-ordinates being even integer numbers
(5) the polygon has at most 1000 vertices
(6) co-ordinates of the vertices lay in the range: -10000..10000.

Input

Input data may consist of several data sets, each beginning with a number of polygon's vertices (n). Consecutive n lines contain co-ordinates of the vertices (x followed by y). Then go the co-ordinates of investigated point P. Input data end when you find 0 the number of polygon's vertices.

Output

For each polygon and each point P you should print one character (in separate lines): T when P belongs to the polygon or F otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a 2-D Cartesian space, a straight line segment A is defined by two points A0=(x0,y0), A1=(x1,y1). The intersection of line segments A and B (if there is one), together with the initial four points, defines four new line segments.
In Figure 1.1, the intersection P between lines B and C defines four new segments. As a result, the toal amount of line segments after the evaluation of intersections is five.

Figure 1.1 - Intersections of line segments

Problem
Given an initial set of lines segments, determine the number of line segments resulting from the evaluation of all the possible intersections.
It is assumed, as a simplification, that no coincidences may occur between coordinates of singular points (intersections or end points).

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of the input contains the integer number N of line segments. Each of the following N lines contains four integer values x0 y0 x1 y1,separated by a single space, that define a line segment.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The integer number of lines segments after all the possible intersections are evaluated.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Axel and Birgit like to play a card game in which they build a house of cards, gaining (or losing) credits as they add cards to the house. Since they both have very steady hands, the house of cards never collapses. They use half a deck of standard playing cards. A standard deck has four suits, two are red and two are black. Axel and Birgit use only two suits, one red, one black. Each suit has 13 ranks. We use the notation 1R, 2R, ..., 13R, 1B, 2B, ..., 13B to denote ranks and colors.

The players begin by selecting a subset of the cards, usually all cards of rank up to some maximum value M. After shuffling the modified deck, they take eight cards from the top of the deck and place them consecutively from left to right to form four ``peaks." For instance, if M = 13 and if the first ten cards (from 26) are:

6B 3R 5B 2B 1B 5R 13R 7B 11R 1R ...

then the game starts off with four peaks and three valleys as shown in Figure 7.

Figure 7: Peaks and valleys formed by the top 8 cards in the deck.
The remaining cards are placed face up, in a single row.

Each player is identified with a color, red or black. Birgit is always black and Axel is always red. The color of the first card used for the peaks and valleys determines which player has the first turn. For the example in Figure 7, Birgit has the first turn since the first card is 6B.

Players alternate taking turns. A turn consists of removing the card from the front of the row of cards and then doing one of the following:

Holding the card until the next turn (this is a ``held card").
Covering the valley between two peaks with the drawn card or the held card, forming a ``floor". The remaining card, if any, is held.
Placing two cards over a floor, forming a peak (one of the cards must be a ``held'' card).
Not all options are always available. At most one card may be held at any time, so the first option is possible only if the player is not already holding a card.

Since the cards in the row are face up, both players know beforehand the order in which the cards are drawn.

If the player forms a downward-pointing triangle by adding a floor, or an upward-pointing triangle by adding a peak, then the scores are updated as follows. The sum of the ranks of the three cards in the triangle is added to the score of the player whose color is the same as the majority of cards in the triangle. If no triangle is formed during a play, both scores remain unchanged.

In the example from Figure 7, if Birgit places her card (11R) on the middle valley, she gains 14 points. If she places her card on the left valley, Axel gains 19 points. If she places her card on the right valley, Axel gains 29 points.

If no more cards remain to be drawn at the end of a turn, the game is over. If either player holds a card at this time, the rank of that card is added to (subtracted from) that player's score if the color of the card is the same as (different from) that player's color.

When the game is over, the player with the lower score pays a number of Swedish Kronor (Kronor is the plural of Krona) equal to the difference between the two scores to the other player. In case of a tie there is no pay out.

You must write a program that takes a description of a shuffled deck and one of the players' names and find the highest amount that player can win (or the player's minimum loss), assuming that the other player always makes the best possible moves.

Input

The input file contains multiple test cases representing different games. Each test case consists of a name (either `Axel' or `Birgit'), followed by a maximum rank M ( 5<=<=M13), followed by the rank and color of the 2M cards in the deck in their shuffled order. Every combination of rank (from 1 through M) and color will appear once in this list. The first eight cards form the initial row of peaks from left to right in the order drawn, and the remaining items show the order of the rest of the cards.

The final test case is followed by a line containing the word `End'.

Output

For each test case, print the test case number (starting with 1), the name of the player for the test case, and the amount that the player wins or loses. If there is a tie, indicate this instead of giving an amount. Follow the sample output format.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Inspired by the ice sculptures in Harbin, the members of the programming team from Arctic University of Robotics and Automata have decided to hold their own ice festival when they return home from the contest. They plan to harvest blocks of ice from a nearby lake when it freezes during the winter. To make it easier to monitor the thickness of the ice, they will lay out a rectangular grid over the surface of the lake and have a lightweight robot travel from square to square to measure ice thickness at each square in the grid. Three locations in the grid are specified as ``check-in" points and the robot is supposed to radio a progress report from these points when it is one-fourth, one-half, and three-fourths of the way through its tour of inspection. To avoid unnecessary wear and tear on the surface of the ice, the robot must begin its tour of the grid from the lower left corner, designated in (row,column) coordinates as (0,0), visiting every other grid location exactly once and ending its tour in row 0, column 1. Moreover, if there are multiple tours that the robot can follow, then a different one is to be used each day. The robot is able to move only one square per time step in one of the four compass directions: north, south, east, or west.


You are to design a program that determines how many different tours are possible for a given grid size and a sequence of three check-in points. For example, suppose the lake surface is marked off in a 3 x 6 grid and that the check-in points, in order of visitation, are (2,1), (2,4), and (0,4). Then the robot must start at (0,0) and end at (0,1) after visiting all 18 squares. It must visit location (2,1) on step 4 (= 18/4), location (2,4) on step 9 (= 18/2), and location (0,4) on step 13 (= 3 x 18/4). There are just two ways to do this (see Figure 8). Note that when the size of the grid is not divisible by 4, truncated division is used to determine the three check-in times.


Note that some configurations may not permit any valid tours at all. For example, in a 4 x 3 grid with check-in sequence (2,0), (3,2), and (0,2), there is no tour of the grid that begins at (0,0) and ends at (0,1).

Input

The input contains several test cases. Each test case begins with a line containing two integers m and n, where 2<=m, n<=8, specifying the number of rows and columns, respectively, in the grid. This is followed by a line containing six integer values r₁, c₁, r₂, c₂, and r₃, c₃, where 0<=r_i < m and 0<=c_i < n for i = 1, 2, 3.

Following the last test case is a line containing two zeros.

Output

Display the case number, beginning at 1, followed by the number of possible tours that begin at row 0, column 0, end at row 0, column 1, and visit row r_i, column c_i at time i x m x floor(n/4) for i = 1, 2, 3. Follow the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The 15-puzzle is a very popular game; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. The object of the puzzle is to arrange the tiles so that they are ordered as below:
                                                                                               

Here the only legal operation is to exchange missing tile with one of the tiles with which it shares an edge. As an example, the following sequence of moves changes the status of a puzzle

                                                 

A random puzzle position 

The missing Tile moves to right. Denoted by R

The missing Tile moves upwards. Denoted by U

The missing Tile moves to the left. Denoted by L

The letters in the previous row indicate which neighbor of the missing tile is swapped with it at each step; legal values are 'R','L','U' and 'D', for RIGHT, LEFT, UP, and DOWN, respectively.

Given an initial configuration of a 15-puzzle you will have to determine the steps that would make you reach the final stage. The input 15-puzzles requires at most 45 steps to be solved with our judge solution. So you will not be allowed to use more than 50 steps to solve a puzzle. If the given initial configuration is not solvable you just need to print the line “This puzzle is not solvable.”

Input

The first line of the input contains one integer N, which indicates how many sets of puzzle, will be given as input. Next 4N lines contain N sets of inputs. It means four lines make one set of input. Zero denotes the missing tile.

Output

For each set of input you will have to give one line of output. If the input puzzle is not solvable then print the line “This puzzle is not solvable.” If the puzzle is solvable then print the move sequence as described above to solve the puzzle.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The game Vexed is a Tetris-like game created by James McCombe. The game consists of a board and blocks that are arranged in stacks. If the space to the immediate left or right of a block is open (that is, it contains no other block nor any part of the game board “wall”), then that block can be moved in that direction. Only blocks that are not part of the game board wall can be moved; “wall” blocks are stationary in all events. After a block is moved, if it or any other block no longer has anything under it, those blocks fall until they land on another block. After all blocks have landed, if any two or more identically-marked pieces are in contact horizontally and/or vertically, then those blocks are removed as a group. If multiple such groups result, then all groups are removed simultaneously. After all such groups are removed, all blocks again fall to resting positions (again, wall blocks do not move). This might then result in more groups being removed, more blocks falling, and so on, until a stable state is reached. The goal of the game is to remove all the movable blocks from the board.

Consider the simple example shown here. For reference purposes, number the rows of the board from top to bottom starting with an index value of zero, and number the columns from the left to right, also with a starting index value of zero. Board positions can be therefore be referenced as ordered (row, column) pairs. By additionally using an “L” or “R” to refer to a left or right push respectively, we can also use the ordered triple (row, column, direction) to indicate moves.

In (A) we have two choices for moves as shown in (B). These moves are (0,1,R) and (1,3,L) using the identification scheme defined above. Note that if we try (0,1,R), the resulting board state as shown in (C) is a dead end; no further moves are possible and blocks still remain on the board. If we choose the other move, however, the blocks at (1,2) and (2,2) are now in vertical contact, so they form a group that should be removed as shown by (D). The resulting board state is shown in (E), leaving the two moves shown by (F). Note that either move would eventually allow a solution, but (0,1,R) leads to a two move solution, whereas (2,1,R) leads to a three move solution. (G) and (H) show the final steps if we choose (0,1,R).

There are often many ways to solve a particular Vexed puzzle. For this problem, only solutions with a minimum number of moves are of interest. The minimum number of moves can sometimes be surprising. Consider another example.

In this example there are ten possible first moves, and there are in fact several ways to arrive at a solution. There is only one move in (A), however, that allows us to achieve a solution with the minimum number of moves. Observe the sequence of events shown if (3,1,R) is chosen as the first move.

Input

The input will consist of several puzzles. Each begins with a line containing integers giving the number of rows (NR) and columns (NC) in the puzzle, and a string of characters (terminated by the end of line) giving the name of the puzzle; these items are separated by one or more spaces. This line is followed by an NR by NC array of characters defining the puzzle itself; an end of line will follow the last character in each row. NR and NC will each be no larger than 9. The “outer walls” (in addition to “inner wall” blocks) on the left, right, and bottom will always be included as part of the puzzle input, and are represented as hash mark (#) characters. Moveable blocks are represented by capital letters which indicate the marking on the block. To avoid possible ambiguities, open spaces in the puzzle are represented in the input by a hyphen (–) rather than by spaces. Other than the outer walls, wall blocks and moveable blocks may be arranged in any stable pattern. Every input puzzle is guaranteed to have a solution requiring 11 or fewer moves.

A puzzle with zero dimensions marks the end of the input and should not be processed.

Output

For each input puzzle, display a minimum length solution formatted as shown in the sample output. In the event that there are multiple solutions of minimum length, display one of them.

Sample Input  Download

Sample Output  Download

Tags

Discuss