Description
Queues 與 Priority Queues 是大家都知道的資料結構，然而 Team Queue卻不是這麼廣為人知，但是他在日常生活中卻常常出現，像是午餐時段排在 Mensa前面的人群就是一個Team Queue
在一個Team Queue中每個元素都屬於一個隊伍，如果一個元素要進入Team Queue時，他會先從頭到尾搜索Team Queue，如果看到他的隊友已經在裡面了，那他就會排到他的隊友後面(插隊)；如果沒有隊友在裡面，他就會排到Team Queue最後面，並成為隊伍的最後一個元素(運氣差)。把元素從Team Queue拿出來時就像普通的Queue一樣，會照順序從Team Queue的最前面到最後面
你的任務就是模擬這個Team Queue
Input
輸入將包含多組測資，每組測資第一個數字是team的數量t(1<=t<=1000)
接下來T行就是這些Team，每行最前面的數字是這個Team的人數，接下來就是這個Team的成員
Team的成員範圍0-999999，一個Team最多有1000個成員
最後，接下來會有一些指令，下面是三種指令
ENQUEUE x - 將元素x丟進Team Queue
DEQUEUE - 將Team Queue 最前面的元素移除掉並且印出來
STOP - 結束這組測資
警告：測試資料可能多達20萬筆，所以要更有效率的去處理你的程式。
ENQUEUE與DEQUQUE照理說只需要常數時間
Input結尾會有個0
Output
對於每組測資，首先先印出"Scenario #k"，其中k是測試用的數量。然後，每個DEQUEUE指令都要印出你移除掉的元素。
在每組測資後面(包括最後一組)都要多印一個空白行
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.
You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Input
The input file will contain one or more test cases. The first line of each test case will contain the number of stones n ( 2<=n<=200). The next n lines each contain two integers xi, yi (0<=xi,yi<=1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying ``Scenario #x" and a line saying ``Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 ≤ n ≤ 105. Then follow n integers h1, ..., hn, where 0 ≤ hi ≤ 109. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 × 10.0 × 0.21 = 1.05 US dollars, making a profit of 5 percent.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input
The input file will contain one or more test cases. On the first line of each test case there is an integer n (1 ≤ n ≤ 30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".
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 (xi, yi, zi). 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 xi, yi and zi.
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
To calculate the circumference of a circle seems to be an easy task - provided you know its diameter. But what if you don't?
You are given the cartesian coordinates of three non-collinear points in the plane. Your job is to calculate the circumference of the unique circle that intersects all three points.
Input
The input file will contain one or more test cases. Each test case consists of one line containing six real numbers x1, y1, x2, y2, x3, y3, representing the coordinates of the three points. The diameter of the circle determined by the three points will never exceed a million. Input is terminated by end of file.
Output
For each test case, print one line containing one real number telling the circumference of the circle determined by the three points. The circumference is to be printed accurately rounded to two decimals. The value of π is approximately 3.141592653589793.
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
Surely you have made the experience that when too many people use the Internet simultaneously, the net becomes very, very slow. To put an end to this problem, the University of Ulm has developed a contingency scheme for times of peak load to cut off net access for some cities of the country in a systematic, totally fair manner. Germany's cities were enumerated randomly from 1 to n. Freiburg was number 1, Ulm was number 2, Karlsruhe was number 3, and so on in a purely random order. Then a number m would be picked at random, and Internet access would first be cut off in city 1 (clearly the fairest starting point) and then in every mth city after that, wrapping around to 1 after n, and ignoring cities already cut off. For example, if n = 17 and m = 5, net access would be cut off to the cities in the order [1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7]. The problem is that it is clearly fairest to cut off Ulm last (after all, this is where the best programmers come from), so for a given n, the random number m needs to be carefully chosen so that city 2 is the last city selected.
Your job is to write a program that will read in a number of cities n and then determine the smallest integer m that will ensure that Ulm can surf the net while the rest of the country is cut off.
Input
The input file will contain one or more lines, each line containing one integer n with 3 ≤ n < 150, representing the number of cities in the country. Input is terminated by a value of zero (0) for n.
Output
For each line of the input, print one line containing the integer m fulfilling the requirement specified above.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the German Lotto you have to select 6 numbers from the set {1, 2, ... , 49}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k = 8 and S = {1, 2, 3, 5, 8, 13, 21, 34} there are 28 possible games: [1, 2, 3, 5, 8, 13], [1, 2, 3, 5, 8, 21], [1, 2, 3, 5, 8, 34], [1, 2, 3, 5, 13, 21], ... [3, 5, 8, 13, 21, 34].
Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.
Input
The input file will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order. Input will be terminated by a value of zero (0) for k.
Output
For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Suppose you have to evaluate an expression like A × B × C × D × E where A, B, C, D and E are matrices.
Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose. For example, let A be a 50 × 10 matrix, B a 10 × 20 matrix and C a 20 × 5 matrix. There are two different strategies to compute A × B × C, namely (A × B) × C and A × (B × C). The first one takes 15000 elementary multiplications, but the second one only 3500.
Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.
Input
Input consists of two parts: a list of matrices and a list of expressions. The first line of the input file contains one integer n (1 ≤ n ≤ 26), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix. The second part of the input file strictly adheres to the following syntax (given in EBNF):
SecondPart = Line { Line }
Line = Expression
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
Output
For each expression found in the second part of the input file, print one line containing the word "error" if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A number whose only prime factors are 2, 3, 5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.
Write a program to find and print the nth element in this sequence.
Input
The input consists of one or more test cases. Each test case consists of one integer n with 1 ≤ n ≤ 5842. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line saying "The nth humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
An addition chain for n is an integer sequence
- a0 = 1
- am = n
- a0
- For each k (1<=k<=m) there exist two (not neccessarily different) integers i and j (0<=i, j<=k-1) with ak=ai+aj
You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.
Input
The input file will contain one or more test cases. Each test case consists of one line containing one integer n (1<=n<=100). Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.
Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In how many ways can you choose k elements out of n elements, not taking order into account?
Write a program to compute this number.
Input
The input file will contain one or more test cases.
Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n).
Input is terminated by two zeroes for n and k.
Output
For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 231.
Warning: Don't underestimate the problem. The result will fit into an integer - but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In a few months the European Currency Union will become a reality. However, to join the club, the Maastricht criteria must be fulfilled, and this is not a trivial task for the countries (maybe except for Luxembourg). To enforce that Germany will fulfill the criteria, our government has so many wonderful options (raise taxes, sell stocks, revalue the gold reserves,...) that it is really hard to choose what to do.
Therefore the German government requires a program for the following task:
Two politicians each enter their proposal of what to do. The computer then outputs the longest common subsequence of words that occurs in both proposals. As you can see, this is a totally fair compromise (after all, a common sequence of words is something what both people have in mind).
Your country needs this program, so your job is to write it for us.
Input
The input file will contain several test cases.
Each test case consists of two texts. Each text is given as a sequence of lower-case words, separated by whitespace, but with no punctuation. Words will be less than 30 characters long. Both texts will contain less than 100 words and will be terminated by a line containing a single '#'.
Input is terminated by end of file.
Output
For each test case, print the longest common subsequence of words occuring in the two texts. If there is more than one such sequence, any one is acceptable. Separate the words by one blank. After the last word, output a newline character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.
Is an escape possible? If yes, how long will it take?
Input
The input file consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Write a program that can solve linear equations with one variable.
Input
The input file will contain a number of equations, each one on a separate line. All equations are strings of less than 100 characters which strictly adhere to the following grammar (given in EBNF):
Equation := Expression '=' Expression
Expression := Term { ('+' | '-') Term }
Term := Factor { '*' Factor }
Factor := Number | 'x' | '(' Expression ')'
Number := Digit | Digit Number
Digit := '0' | '1' | ... | '9'
Although the grammar would allow to construct non-linear equations like "x*x=25", we guarantee that all equations occuring in the input file will be linear in x. We further guarantee that all sub-expressions of an equation will be linear in x too. That means, there won't be test cases like x*x-x*x+x=0 which is a linear equation but contains non-linear sub-expressions (x*x).
Note that all numbers occuring in the input are non-negative integers, while the solution for x is a real number.
Output
For each test case, print a line saying "Equation #i (where i is the number of the test case) and a line with one of the following answers:
- If the equation has no solution, print "No solution.".
- If the equation has infinitely many solutions, print "Infinitely many solutions.".
- If the equation has exactly one solution, print "x = solution" where solution is replaced by the appropriate real number (printed to six decimals).
Print a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
As a member of an ACM programming team you'll soon find yourself always traveling around the world: Zürich, Philadelphia, San José, Atlanta,... from 1999 on the Contest Finals even will be on a different continent each year, so one day you might get to Japan or Australia.
At the contest site it would be interesting to know how many miles you are away from home. For this sake, your job is to write a program to compute the geographical distance between two given locations on the Earth's surface.
We assume that the Earth is a perfect sphere with a radius of exactly 6378 km. The geographical distance between A and B is the length of the geodetic line segment connecting A and B.
The geodetic line segment between two points on a sphere is the shortest connecting curve lying entirely in the surface of the sphere.
The value of pi is approximately 3.141592653589793.
Input
The input file will consist of two parts: a list of cities and a list of queries.
City List
The city list consists of up to 100 lines, one line per city. Each line will contain a string ci and two real numbers lati and longi, representing the city name, its latitude and its longitude, respectively.
The city name will be shorter than 30 characters and will not contain white-space characters.
The latitude will be between -90 (South Pole) and +90 (North Pole). The longitude will be between -180 and +180 where negative numbers denote locations west of the meridian and positive numbers denote locations east of the meridian. (The meridian passes through Greenwich, London.)
The city list will be terminated by a line consisting of a single "#".
Query List
Each line will contain two city names A and B.
The query list will be terminated by the line "# #".
Output
For each query, print a line saying "A - B" where A and B are replaced by the city names. Then print a line saying x km" where x is replaced by the geographical distance (in km) between the two cities, rounded to the nearest integer.
If one of the cities in the query didn't occur in the city list, print a line saying "Unknown" instead. Print a blank line after each query.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.
This is an example of one of her creations:
To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.
She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).
Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.
However, doing the reconstruction by hand, soon turned out to be tedious.
So now she asks you to write a program that does the job for her!
Input
The input file will contain one or more test cases.
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)
Input is terminated by end of file.
Output
For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
高中物理老師通常認為把問題隱藏在題目的文字中比單純計算要難得多，畢竟學生必須先看得懂題目才行！
所以他們不喜歡把題目出成像``電壓＝10伏特，電流＝5安培，請問電功率＝？"這種類型，而比較喜歡出成``你有一組電路，包含一個電壓＝10伏特的電池和一個燈泡。若現在有5安培的電流通過燈泡，請問燈泡的電功率是多少？"（由於本題Input與英文有關，茲將原文收錄如下：``You have an electrical circuit that contains a battery with a voltage of U=10V and a light-bulb. There's an electrical current of I=5A through the bulb. Which power is generated in the bulb?".）
然而超過半數的學生並不會把注意力放在那些文字上，他們只會設法從文字中找出已知條件：電壓＝10伏特，電流＝5安培。然後思索``我該用哪條公式？Ah, yes, P=I*V；所以P=10V*5A=500W。完成！"
OK,這個方法並不是每次都有用，所以通常這些學生在物理考試中得不到頂尖的成績，但至少這種簡單的演算法已足以獲得及格以上的成績。（遺憾但卻是事實）
現在我們要試試看電腦能不能通過高中物理考試，我們先來解決這個功率-電壓-電流(P-U-I type)的問題 ，也就是說題目給任兩個已知條件，你要求出第三個。
你的工作就是寫一支程式可以讀入一段題目的文字，並根據上面所描述的簡易演算法來求出答案。
Input
輸入檔的第一行會先告訴你有多少個題目要求答案。
每一個問題由一列包括兩個明確的已知條件和一些額外的文字組成。已知條件會以下列格式出現：I=xA 或 U=xV 或者 P=xW（x屬於實數）
在單位（A，V或W）前可能會帶有一個數量級單位：m(milli,10的-3次方)，k(kilo,10的3次方)或M(Mega,10的6次方)。總而言之，已知條件（data field）會遵守下列文法：
DataField ::= Concept '=' RealNumber [Prefix] Unit
Concept ::= 'P' | 'U' | 'I'
Prefix ::= 'm' | 'k' | 'M'
Unit ::= 'W' | 'V' | 'A'
額外說明 ：
等號不會出現在已知條件（data field）外的地方。
已知條件（data field）中不會出現空白字元。
已知條件可能給 電壓＋功率 或 功率＋電流 或 電流＋電壓 三種形式。
Output
對每個題目必須輸出三列：
第一列輸出``Problem #k"，k代表第幾題。
第二列輸出答案（試所求輸出電壓、功率或電流）並將數量級轉換為基本單位及兩位有效小數位數（見sample output）
第三列為空白行。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Once upon a time there was a large team coming home from the ACM World Finals. The fifteen travellers were confronted with a big problem:
In the previous weeks, there had been many money transactions between them: Sometimes somebody paid the entrance fees of a theme park for the others, somebody else paid the hotel room, another one the rental car, and so on.
So now the big calculation started. Some people had paid more than others, thus the individual bank accounts had to be balanced again. "Who has to pay whom how much?", that was the question.
As such a calculation is a lot of work, we need a program now that will solve this problem next year.
Input
The input file will contain one or more test cases.
Each test case starts with a line containing two integers: the number of travellers n (2<=n<=20) and the number of transactions t (1<=t<=1000). On the next n lines the names of the travellers are given, one per line. The names only consist of alphabetic characters and contain no whitespace. On the following t lines, the transactions are given in the format name1 name2 amount where name1 is the person who gave amount dollars to name2. The amount will always be a non-negative integer less than 10000.
Input will be terminated by two values of 0 for n and t.
Output
For each test case, first print a line saying "Case #i" where i is the number of the test case.
Then, on the following lines, print a list of transactions that reverses the transactions given in the input, i.e. balances the accounts again. Use the same format as in the input. Print a blank line after each test case, even after the last one.
Additional restrictions:
- Your solution must consist of at most n-1 transactions.
- Amounts may not be negative, i.e. never output "A B -20", output "B A 20" instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by building roads, settlements and cities across its uncharted wilderness.
You are employed by a software company that just has decided to develop a computer version of this game, and you are chosen to implement one of the game's special rules:
When the game ends, the player who built the longest road gains two extra victory points.
The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).
Compared to the original game, we will solve a simplified problem here: You are given a set of nodes (cities) and a set of edges (road segments) of length 1 connecting the nodes.
The longest road is defined as the longest path within the network that doesn't use an edge twice. Nodes may be visited more than once, though.
Example: The following network contains a road of length 12.
o o--o o
/ /
o--o o--o
/ /
o o--o o--o
/
o--o
Input
The input file will contain one or more test cases.
The first line of each test case contains two integers: the number of nodes n (2<=n<=25) and the number of edges m (1<=m<=25). The next m lines describe the m edges. Each edge is given by the numbers of the two nodes connected by it. Nodes are numbered from 0 to n-1. Edges are undirected. Nodes have degrees of three or less. The network is not necessarily connected.
Input will be terminated by two values of 0 for n and m.
Output
For each test case, print the length of the longest road on a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here's a 4 x 4 matrix which has the parity property:
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
The sums of the rows are 2, 0, 4 and 2. The sums of the columns are 2, 2, 2 and 2.
Your job is to write a program that reads in a matrix and checks if it has the parity property. If not, your program should check if the parity property can be established by changing only one bit. If this is not possible either, the matrix should be classified as corrupt.
Input
The input file will contain one or more test cases. The first line of each test case contains one integer n (n<100), representing the size of the matrix. On the next n lines, there will be n integers per line. No other integers than 0 and 1 will occur in the matrix. Input will be terminated by a value of 0 for n.
Output
For each matrix in the input file, print one line. If the matrix already has the parity property, print "OK". If the parity property can be established by changing one bit, print "Change bit (i,j)" where i is the row and j the column of the bit to be changed. Otherwise, print "Corrupt".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Today the first round of the Soccer World Championship in France is coming to an end. 16 countries are remaining now, among which the winner is determined by the following tournament:
1 Brazil -----+
+-- ? --+
2 Chile ------+ |
+-- ? --+
3 Nigeria ----+ | |
+-- ? --+ |
4 Denmark ----+ |
+-- ? --+
5 Holland ----+ | |
+-- ? --+ | |
6 Yugoslavia -+ | | |
+-- ? --+ |
7 Argentina --+ | |
+-- ? --+ |
8 England ----+ |
+-- World Champion
9 Italy ------+ |
+-- ? --+ |
10 Norway -----+ | |
+-- ? --+ |
11 France -----+ | | |
+-- ? --+ | |
12 Paraguay ---+ | |
+-- ? --+
13 Germany ----+ |
+-- ? --+ |
14 Mexico -----+ | |
+-- ? --+
15 Romania ----+ |
+-- ? --+
16 Croatia ----+
For each possible match A vs. B between these 16 nations, you are given the probability that team A wins against B. This (together with the tournament mode displayed above) is sufficient to compute the probability that a given nation wins the World Cup. For example, if Germany wins against Mexico with 80%, Romania against Croatia with 60%, Germany against Romania with 70% and Germany against Croatia with 90%, then the probability that Germany reaches the semi-finals is 80% * (70% * 60% + 90% * 40%) = 62.4%.
Your task is to write a program that computes the chances of the 16 nations to become the World Champion '98.
Input
The input file will contain just one test case.
The first 16 lines of the input file give the names of the 16 countries, from top to bottom according to the picture given above.
Next, there will follow a 16 x 16 integer matrix P where element pijgives the probability in percent that country #i defeats country #j in a direct match. Country #i means the i-th country from top to bottom given in the list of countries. In the picture above Brazil is #1 and Germany is #13, so p1,13=55 would mean that in a match between Brazil and Germany, Brazil wins with a probability of 55%.
Note that matches may not end with a draw, i.e. pij + pji = 100 for all i,j.
Output
Output 16 lines of the form "XXXXXXXXXX p=Y.YY%", where XXXXXXXXXX is the country's name, left-justified in a field of 10 characters, and Y.YY is their chance in percent to win the cup, written to two decimal places. Use the same order of countries like in the input file.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:
Every even number greater than 4 can be
written as the sum of two odd prime numbers.
For example:
- 8 = 3 + 5. Both 3 and 5 are odd prime numbers.
- 20 = 3 + 17 = 7 + 13.
- 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.
Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)
Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.
Input
The input file will contain one or more test cases.
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.
Output
For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.
Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.
Input
The input file will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2<=n<=200) and the number of road segments r (1<=r<=19900) making up the street network.
Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.
The last line of the test case contains two city names: start and destination.
Input will be terminated by two values of 0 for n and r.
Output
For each test case, print three lines:
- a line saying "Scenario #x" where x is the number of the test case
- a line saying "y tons" where y is the maximum possible load
- a blank line
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The company "21st Century Fruits" has specialized in creating new sorts of fruits by transferring genes from one fruit into the genome of another one. Most times this method doesn't work, but sometimes, in very rare cases, a new fruit emerges that tastes like a mixture between both of them.
A big topic of discussion inside the company is "How should the new creations be called?" A mixture between an apple and a pear could be called an apple-pear, of course, but this doesn't sound very interesting. The boss finally decides to use the shortest string that contains both names of the original fruits as sub-strings as the new name. For instance, "applear" contains "apple" and "pear" (APPLEar and apPlEAR), and there is no shorter string that has the same property.
A combination of a cranberry and a boysenberry would therefore be called a "boysecranberry" or a "craboysenberry", for example.
Your job is to write a program that computes such a shortest name for a combination of two given fruits. Your algorithm should be efficient, otherwise it is unlikely that it will execute in the alloted time for long fruit names.
Input
Each line of the input file contains two strings that represent the names of the fruits that should be combined. All names have a maximum length of 100 and only consist of alphabetic characters.
Input is terminated by end of file.
Output
For each test case, output the shortest name of the resulting fruit on one line. If more than one shortest name is possible, any one is acceptable.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maja is a bee. She lives in a bee hive with thousands of other bees. This bee hive consists of many hexagonal honey combs where the honey is stored in.
But bee Maja has a problem. Willi told her where she can meet him, but because Willi is a male drone and Maja is a female worker they have different coordinate systems.
|
Maja's Coordinate System |
Willi's Coordinate System |
|
Maja who often flies directly to a special honey comb has laid an advanced two dimensional grid over the whole hive. |
Willi who is more lazy and often walks around just numbered the cells clockwise starting from 1 in the middle of the hive. |
|
|
|
Help Maja to convert Willi's system to hers. Write a program which for a given honey comb number gives the coordinates in Maja's system.
Input
The input file contains one or more integers which represent Willi's numbers. Each number stands on its own in a separate line, directly followed by a newline. The honey comb numbers are all less than 100 000.
Output
You should output the corresponding Maja coordinates to Willi's numbers, each coordinate pair on a separate line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
While searching for treasures in an ancient Aztec ruin, Florida Jones (the brother of famous Indiana Jones) stumbles across a papyrus roll lettered with a long string of symbols. There are three different symbols occuring in the string which we will call B, W and Q here.
Being somewhat experienced in cryptography, Florida Jones recognizes the code immediately as the famous Quadtree Encoding Scheme that has been invented 3000 years ago.
With the Quadtree system, secret pictures (like treasure maps) were encoded in the following way: If the whole picture was black, it was encoded by the letter B. If it was completely white, it was encoded by W. If both colors were used (what was usually the case), it was encoded by Qxxxx where each x was a string that recursively encoded one quarter of the picture (in the order top left, top right, bottom left, bottom right). As the Aztecs always used quadratic pictures with n*n pixels where n was a power of two, this method always worked perfectly.
A 2*2 chess board, for instance, would be encoded as QWBBW, a 4*4 chess board as QQWBBWQWBBWQWBBWQWBBW.
Your job is to decode the quadtree string and output the picture in the XBM format (see output specification).
Input
The input file contains an integer n (8 <= n <= 512) on the first line, giving the size of the picture in pixels per row/column. n will always be a power of two.
On the second line, a string consisting of the letters B, W and Q follows. The string encodes a picture with n*n pixels with the quadtree scheme.
Output
- On the first line, print "#define quadtree_width n" where n is the picture size given in the input file.
- On the second line, print "#define quadtree_height n" accordingly.
- On the third line, print "static char quadtree_bits[] = {".
- Then, print n lines (each one encoding one pixel row of the picture) with n/8 hexadecimal numbers per line.
Each hexadecimal number is composed of 8 bits that encode 8 pixels from left to right (where the leftmost bit has the value 1 and the rightmost bit has the value 128). The hexadecimal numbers should be printed in the form 0xdd where d is one character of the set { 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f }.
Example: The 8 pixels WBBBBWWB would be written as 0x9e. (2+4+8+16+128 = 158 = 0x9e)
Print a comma after each hexadecimal number.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Vladimir has white skin, very long teeth and is 600 years old, but this is no problem because Vladimir is a vampire.
Vladimir has never had any problems with being a vampire. In fact, he is a very successful doctor who always takes the night shift and so has made many friends among his colleagues. He has a very impressive trick which he shows at dinner partys: He can tell tell blood group by taste.
Vladimir loves to travel, but being a vampire he has to overcome three problems.
- First, he can only travel by train because he has to take his coffin with him. (On the up side he can always travel first class because he has invested a lot of money in long term stocks.)
- Second, he can only travel from dusk till dawn, namely from 6 pm to 6 am. During the day he has to stay inside a train station.
- Third, he has to take something to eat with him. He needs one litre of blood per day, which he drinks at noon (12:00) inside his coffin.
You should help Vladimir to find the shortest route between two given cities, so that he can travel with the minimum amount of blood. (If he takes too much with him, people will ask funny questions like "What do you do with all that blood?")
Input
The first line of the input will contain a single number telling you the number of test cases.
Each test case specification begins with a single number telling you how many route specifications follow.
Each route specification consists of the names of two cities, the departure time from city one and the total travelling time. The times are in hours. Note that Vladimir can't use routes departing earlier than 18:00 or arriving later than 6:00.
There will be at most 100 cities and less than 1000 connections. No route takes less than one hour and more than 24 hours. (Note that Vladimir can use only routes with a maximum of 12 hours travel time (from dusk till dawn).) All city names are shorter than 32 characters.
The last line contains two city names. The first is Vladimir's start city, the second is Vladimir's destination.
Output
For each test case you should output the number of the test case followed by "Vladimir needs # litre(s) of blood." or "There is no route Vladimir can take."
Sample Input Download
Sample Output Download
Tags
Discuss
Description
As you maybe know, the qualification for the European Soccer Championship 2000 is a tournament where in each group each team plays against each other team twice. Germany is in group 3 together with Turkey, Finland, Moldova and Northern Ireland. 14 games have been played and 6 are still to come. (See attachment.)
A quick look at the current standings might make you think that Northern Ireland is already out of the race. But that's wrong! Imagine Northern Ireland wins their three remaining games, Germany plays remis against Turkey and loses against Finland, and Moldova defeats Turkey. Then Northern Ireland is number one!
For those who are not familiar with the scoring model: In each game a team gains 3 points for a victory, 1 point for a remis or 0 points for a loss. After all games have been played, teams are ranked according to points. In case of a tie, the additional tie breakers are: goal difference (i.e. goals scored - goals against), goals scored, and random choice, in that order.
The question your program should answer is:
Regarding all possibilities of how the remaining games could end, what is the highest and lowest possible rank of each team in the group after the tournament is over?
Input
The input will consist of one or more test cases. Each test case adheres to the following format:
- On the first line there will be one integer n (1 <= n <= 20), representing the number of teams in the group.
- On the next n lines, the names of the teams will follow. Names are always shorter than 30 characters and do not contain whitespace.
- On the next line, there will be an integer g, representing the number of completed games.
- Finally, g lines will follow, each one describing one completed game in the form team1 team2 goals1 goals2.
- You may further assume that at most 10 games will be remaining and each team has at least one remaining game to play. (This simplifies the problem a little.)
Input will be terminated by a value of zero (0) for n.
Output
For each test case, first print a line saying "Group #x" where x is the number of the test case (counting from 1).
Then, print one line per team in the order they appear in the input. On each line, print the team's name, a blank character, its best possible rank, a minus sign and its worst possible rank.
Print a blank line after each test case, even after the last one.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You want to plan a big birthday party with your friends. On planning you notice that you have to do a lot of operations with sets of friends. There is one group which consist of Arthur, Biene and Clemens. Then there is a group of friends you know from snowboarding which consists of Daniel, Ernst, Frida and Gustav. If you want to invite them both, the resulting party group consists of g1 + g2 (the result is the union of both groups). Then you can compute the intersection of the two groups g1 * g2, which consists of the empty set. Maybe you want to invite a group g1, but excluding all members of an other group g2, which is written as g1 - g2.
Intersection (*) has precedence over union (+) and set difference (-). All operations are left associative, which means that in A op1 B op2 C you first have to evaluate A op1 B (provided op1 and op2 have equal precedence).
Input
The input consists of one or more lines. Each line contains one expression that you have to evaluate. Expressions are syntactically correct and only consist of the characters:
- '{' and '}'
- the elements 'A' to 'Z' meaning friend Arthur to Zora.
- the operations '+', '-' and '*'
- '(' and ')' for grouping operations
- the newline character ' ' marking the end of an expression.
A line is never longer than 255 characters.
Output
Output the resulting set in curly braces '{' and '}', each on a line of its own. Print elements of sets sorted alphabetically.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Having realized that the quadtree-encoded treasure map was a fake, Florida Jones maliciously plans to also play a prank for the next treasure hunter after him. But for that, he needs your help once again:
Can you write a program that takes a picture in the XBM format and encodes it with the quadtree scheme?
Input
- The first line will be "#define quadtree_width n" where n is the picture size in pixels. (The picture is quadratic: n*n pixels)
- The second line will be "#define quadtree_height n" accordingly.
- The third line will be "static char quadtree_bits[] = {".
- Then, n lines will follow, each one encoding one pixel row of the picture. There will be n/8 hexadecimal numbers per line.
Each hexadecimal number is composed of 8 bits that encode 8 pixels from left to right (where the leftmost bit has the value 1 and the rightmost bit has the value 128). The hexadecimal numbers are printed in the form 0xdd where d is one character of the set { 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f }.
Example: The 8 pixels WBBBBWWB are written as 0x9e. (2+4+8+16+128 = 158 = 0x9e)
After each hexadecimal number, a comma follows. - The last line will be "};".
Output
First, print the integer n (8 <= n <= 512) on a line by itself.
Then, print a string consisting of the letters B, W and Q that correctly encodes the picture with the quadtree scheme.
Finally, terminate the string with a newline character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
If you ever tried to read a html document on a Macintosh, you know how hard it is if no Netscape is installed.
Now, who can forget to install a HTML browser? This is very easy because most of the times you don't need one on a MAC because there is a Acrobate Reader which is native to MAC. But if you ever need one, what do you do?
Your task is to write a small html-browser. It should only display the content of the input-file and knows only the html commands (tags)
Input
The input consists of a text you should display. This text consists of words and HTML tags separated by one or more spaces, tabulators or newlines.
A word is a sequence of letters, numbers and punctuation. For example, "abc,123" is one word, but "abc, 123" are two words, namely "abc," and "123". A word is always shorter than 81 characters and does not contain any '<' or '>'. All HTML tags are either
Output
You should display the the resulting text using this rules:
- If you read a word in the input and the resulting line does not get longer than 80 chars, print it, else print it on a new line.
- If you read a
- If you read a
The last line is ended by a newline character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
World-renowned Prof. A. N. Agram's current research deals with large anagram groups. He has just found a new application for his theory on the distribution of characters in English language texts. Given such a text, you are to find the largest anagram groups.
A text is a sequence of words. A word w is an anagram of a word v if and only if there is some permutation p of character positions that takes w to v. Then, w and v are in the same anagram group. The size of an anagram group is the number of words in that group. Find the 5 largest anagram groups.
Input
The input contains words composed of lowercase alphabetic characters, separated by whitespace. It is terminated by EOF.
Output
Output the 5 largest anagram groups. If there are less than 5 groups, output them all. Sort the groups by decreasing size. Break ties lexicographically by the lexicographical smallest element. For each group output, print its size and its member words. Sort the member words lexicographically and print equal words only once.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As you can deduce from the company name, their business is beads. Their PR department found out that customers are interested in buying colored bracelets. However, over 90 percent of the target audience insists that the bracelets be unique. (Just imagine what happened if two women showed up at the same party wearing identical bracelets!) It's a good thing that bracelets can have different lengths and need not be made of beads of one color. Help the boss estimating maximum profit by calculating how many different bracelets can be produced.
A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.
Input
Every line of the input file defines a test case and contains two integers: the number of available colors c followed by the length of the bracelets s. Input is terminated by c = s = 0. Otherwise, both are positive, and, due to technical difficulties in the bracelet-fabrication-machine, cs ≤ 32, i.e. their product does not exceed 32.
Output
For each test case output on a single line the number of unique bracelets. The figure below shows the 8 different bracelets that can be made with 2 colors and 5 beads.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are to write an interpreter for a simple computer. This computer uses a processor with a small number of machine instructions. Furthermore, it is equipped with 32 byte of memory, one 8-bit accumulator (accu) and a 5-bit program counter (pc). The memory contains data as well as code, which is the usual von Neumann architecture.
The program counter holds the address of the instruction to be executed next. Each instruction has a length of 1 byte - the highest 3 bits define the type of instruction and the lowest 5 bits define an optional operand which is always a memory address (xxxxx). For instructions that don't need an operand the lowest 5 bits have no meaning (-----). Here is a list of the machine instructions and their semantics:
000xxxxx STA x store the value of the accu into memory byte x
001xxxxx LDA x load the value of memory byte x into the accu
010xxxxx BEQ x if the value of the accu is 0 load the value x into the pc
011----- NOP no operation
100----- DEC subtract 1 from the accu
101----- INC add 1 to the accu
110xxxxx JMP x load the value x into the pc
111----- HLT terminate program
In the beginning, program counter and accumulator are set to 0. After fetching an instruction but before its execution, the program counter is incremented. You can assume that programs will terminate.
Input
The input file contains several test cases. Each test case specifies the contents of the memory prior to execution of the program. Byte 0 through 31 are given on separate lines in binary representation. A byte is denoted by its highest-to-lowest bits. Input is terminated by EOF
Output
For each test case, output on a line the value of the accumulator on termination in binary representation, again highest bits first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.
Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!
Input
The input file contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h = w = 0. Otherwise, 1 ≤ h, w ≤ 11.
Output
For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Alice and Bob haven't met for some time. Bob isn't very happy about this, so he urges Alice to finally make time for a meeting. Let's listen to an extract from a phone call:
Alice: ... maybe we should meet on neutral territory.
Bob: I've already heard this from you --- two years ago.
Alice: I know ; I just haven't found yet a suitable place that is roughly at the same distance from both yours and mine.
Bob: Well, the geometric place of the points that are equidistant from two given points on the surface of a sphere (and the earth is a sphere rather than a disc) is a great circle (namely the one which intersects the great circle through the given points orthogonally at the center of them). If you insist only on approximately equal distances though, we get a zone of some kilometers width and about 40000 km length. Not everything in this zone is water. Thus I think it is a feasible task to find a fitting place.
Alice: Now, if I tell you to pick any, we'll certainly land up in Honolulu.
Bob: Which is not a too bad idea. So, may I pick any ?
Alice: As long as I don't have to accept --- but I'm open to suggestions.
Bob: Honolulu ?
Alice: Is it situated on aforementioned geometric place at all ??!
Bob: Not quite ...
Nice. Now let's stop the preliminaries and come to the facts: Given two locations on the earth's surface you can find the geometric place of all equidistant points on the surface. For another given location calculate its distance on the surface to this geometric place. Assume that the earth is a sphere with a radius of 6378 km.
Input
The input file consists of two parts: a list of locations and a list of queries.
The location list consists of up to 100 lines, one line per location. Each contains a string and two floating-point numbers, separated by whitespace, representing the name of the location, its latitude and its longitude. Names are unique and shorter than 30 characters and do not contain whitespace. Latitudes are between -90 (South Pole) and 90 (North Pole) inclusive. Longitudes are between -180 and 180 inclusive where negative numbers denote locations west of the meridian and positive numbers denote locations east of the meridian. (The meridian passes through Greenwich, London.) The location list is terminated by a line consisting of a single "#".
Each line in the query list contains three names of locations. You can assume the first location to be Alice's home, the second location to be Bob's home and the third location to be a possible meeting point. The query list is terminated by a line consisting of a single "#".
Output
For each query, output a line saying "M is x km off A/B equidistance." with M,x,A,B appropriately replaced by the location names and the calculated distance rounded to the nearest integer.
If one of the locations in the query didn't occur in the list of locations print "?" instead of the distance.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Recall the definition of the Fibonacci numbers:
f1 := 1
f2 := 2
fn := fn - 1 + fn - 2 (n ≥ 3)
Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b].
Input
The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a ≤ b ≤ 10100. The numbers a and b are given with no superfluous leading zeros.
Output
For each test case output on a single line the number of Fibonacci numbers fi with a ≤ fi ≤ b.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Among other things, Computational Molecular Biology deals with processing genetic sequences. Considering the evolutionary relationship of two sequences, we can say that they are closely related if they do not differ very much. We might represent the relationship by a tree, putting sequences from ancestors above sequences from their descendants. Such trees are called phylogenetic trees.
Whereas one task of phylogenetics is to infer a tree from given sequences, we'll simplify things a bit and provide a tree structure - this will be a complete binary tree. You'll be given the n leaves of the tree. Sure you know, n is always a power of 2. Each leaf is a sequence of amino acids (designated by the one-character-codes you can see in the figure). All sequences will be of equal length l. Your task is to derive the sequence of a common ancestor with minimal costs.
|
|
|
The costs are determined as follows: every inner node of the tree is marked with a sequence of length l, the cost of an edge of the tree is the number of positions at which the two sequences at the ends of the edge differ, the total cost is the sum of the costs at all edges. The sequence of a common ancestor of all sequences is then found at the root of the tree. An optimal common ancestor is a common ancestor with minimal total costs.
Input
The input file contains several test cases. Each test case starts with two integers n and l, denoting the number of sequences at the leaves and their length, respectively. Input is terminated by n = l = 0. Otherwise, 1 ≤ n ≤ 1024 and 1 ≤ l ≤ 1000. Then follow n words of length l over the amino acid alphabet. They represent the leaves of a complete binary tree, from left to right.
Output
For each test case, output a line containing some optimal common ancestor and the minimal total costs.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
“Hike on a Graph” is a game that is played on a board on which an undirected graph is drawn. The graph is complete and has all loops, i.e. for any two locations there is exactly one arrow between them. The arrows are coloured. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players may do a move. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same colour as the arrow between the two opponents' pieces.
In the sixties (“make love not war”) a one-person variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.
Input
The input file contains several test cases. Each test case starts with the number n. Input is terminated by n = 0. Otherwise, 1 ≤ n ≤ 50. Then follow three integers p1, p2, p3 with 1 ≤ pi ≤ n denoting the starting locations of the game pieces. The colours of the arrows are given next as a n × n matrix of whitespace-separated lower-case letters. The element mij denotes the colour of the arrow between the locations i and j. Since the graph is undirected, you can assume the matrix to be symmetrical.
Output
For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word “impossible” if that is not possible for the given board and starting locations.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A relay is a race for two or more teams of runners. Each member of a team runs one section of the race. Your task is to help to evaluate the results of a relay race.
You have to process several teams. For each team you are given a list with the running times for every section of the race. You are to compute the average time per kilometer over the whole distance. That's easy, isn't it?
So if you like the fun and challenge competing at this contest, perhaps you like a relay race, too. Students from Ulm participated e.g. at the "SOLA" relay in Zurich, Switzerland. For more information visit http://www.sola.asvz.ethz.ch/ after the contest is over.
Input
The first line of the input specifies the number of sections n followed by the total distance of the relay d in kilometers. You may safely assume that 1 ≤ n ≤ 20 and 0.0 ≤ d ≤ 200.0. Every following line gives information about one team: the team number t (an integer, right-justified in a field of width 3) is followed by the n results for each section, separated by a single space. These running times are given in the format "h:mm:ss" with integer numbers for the hours, minutes and seconds, respectively. In the special case of a runner being disqualified, the running time will be denoted by "-:--:--". Finally, the data on every line is terminated by a newline character. Input is terminated by EOF.
Output
For each team output exactly one line giving the team's number t right aligned in a field of width 3, and the average time for this team rounded to whole seconds in the format "m:ss". If at least one of the team's runners has been disqualified, output "-" instead. Adhere to the sample output for the exact format of presentation.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant phase: "But I want to use feet, not meters!"). Each signal seems to come in two parts: a sequence of n integer values and a non-negative integer t. We'll not go into details, but researchers found out that a signal encodes two integer values. These can be found as the lower and upper bound of a subrange of the sequence whose absolute value of its sum is closest to t.
You are given the sequence of n integers and the non-negative target t. You are to find a non-empty range of the sequence (i.e. a continuous subsequence) and output its lower index l and its upper index u. The absolute value of the sum of the values of the sequence from the l-th to the u-th element (inclusive) must be at least as close to t as the absolute value of the sum of any other non-empty range.
Input
The input file contains several test cases. Each test case starts with two numbers n and k. Input is terminated by n = k = 0. Otherwise, 1 ≤ n ≤ 100000 and there follow n integers with absolute values ≤ 10000 which constitute the sequence. Then follow k queries for this sequence. Each query is a target t with 0 ≤ t ≤ 1000000000.
Output
For each query output 3 numbers on a line: some closest absolute sum and the lower and upper indices of some range where this absolute sum is achieved. Possible indices start with 1 and go up to n.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, ..., n is given. The "Prufer" code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the obtained graph, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n - 1 numbers is called the Prufer code of the tree. Your task is, given a tree, to compute its Prufer code. The tree is denoted by a word of the language specified by the following grammar:
T ::= "(" N S ")"
S ::= " " T S
| empty
N ::= number
That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample input. To generate further sample input, you may use your solution to Problem 7455.
Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an "unrooted tree".
Input
The input contains several test cases. Each test case specifies a tree as described above on one line of the input file. Input is terminated by EOF. You may assume that 1 ≤ n ≤ 50.
Output
For each test case generate a single line containing the Prufer code of the specified tree. Separate numbers by a single space. Do not print any spaces at the end of the line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A tree (i.e. a connected graph without cycles) with vertices numbered by the integers 1, 2, ..., n is given. The "Prufer" code of such a tree is built as follows: the leaf (a vertex that is incident to only one edge) with the minimal number is taken. This leaf, together with its incident edge is removed from the graph, while the number of the vertex that was adjacent to the leaf is written down. In the obtained graph, this procedure is repeated, until there is only one vertex left (which, by the way, always has number n). The written down sequence of n - 1 numbers is called the Prufer code of the tree.
Your task is, to reconstruct a tree, given its Prufer code. The tree should be denoted by a word of the language specified by the following grammar:
T ::= "(" N S ")"
S ::= " " T S
| empty
N ::= number
That is, trees have parentheses around them, and a number denoting the identifier of the root vertex, followed by arbitrarily many (maybe none) subtrees separated by a single space character. As an example, take a look at the tree in the figure below which is denoted in the first line of the sample output. To generate further sample input, you may use your solution to Problem 7454.
Note that, according to the definition given above, the root of a tree may be a leaf as well. It is only for the ease of denotation that we designate some vertex to be the root. Usually, what we are dealing here with is called an "unrooted tree".
Input
The input contains several test cases. Each test case specifies the Prufer code of a tree on one line. You will find n - 1 numbers separated by a single space. Input is terminated by EOF. You may assume that 1 ≤ n ≤ 50.
Output
For each test case generate a single line containing the corresponding tree, denoted as described above. Note that, in general, there are many ways to denote such a tree: choose your favourite one.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The relative frequency of characters in natural language texts is very important for cryptography. However, the statistics vary for different languages. Here are the top 9 characters sorted by their relative frequencies for several common languages:
English: ETAOINSHR
German: ENIRSATUD
French: EAISTNRUL
Spanish: EAOSNRILD
Italian: EAIONLRTS
Finnish: AITNESLOK
Just as important as the relative frequencies of single characters are those of pairs of characters, so called digrams. Given several text samples, calculate the digrams with the top relative frequencies.
Input
The input contains several test cases. Each starts with a number n on a separate line, denoting the number of lines of the test case. The input is terminated by n=0. Otherwise, 1<=n<=64, and there follow n lines, each with a maximal length of 80 characters. The concatenation of these n lines, where the end-of-line characters are omitted, gives the text sample you have to examine. The text sample will contain printable ASCII characters only.
Output
For each test case generate 5 lines containing the top 5 digrams together with their absolute and relative frequencies. Output the latter rounded to a precision of 6 decimal places. If two digrams should have the same frequency, sort them in (ASCII) lexicographical order. Output a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Several startup companies have decided to build a better Internet, called the "FiberNet". They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes.
Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.
Input
The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.
After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.
Output
For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output "-" instead. Output a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A great deal in today's mobile communication depends on having a direct view to a satellite. For communication providers it is therefore crucial to know where their services are available.
You are to identify locations which have a direct view to a particular satellite, i.e. this satellite must be above the horizon. To make things easier you may assume that the earth is a perfect sphere with a radius of 6378 km (mountains will be added next year...). The satellite is a pointlike object above the earth's surface.
Input
The input file consists of several test cases. For each test case the first line contains the number of locations n to be checked followed by the position of the satellite: its latitude, its longitude (both in degrees) and its height (in km) above the earth's surface.
Each of the following n lines contains a location on the earth's surface: the location's label (a sequence of less than 60 printable ASCII characters containing no whitespace characters) followed by its latitude and longitude (both in degrees).
Input is terminated by n=0.
Output
For each test case output the number of the test case as formatted in the sample output. Then, output the locations from where the satellite is visible by printing the corresponding labels on separate lines in the same order as they appear in the input file.
Output a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The fight goes on, whether to store numbers starting with their most significant digit or their least significant digit. Sometimes this is also called the "Endian War". The battleground dates far back into the early days of computer science. Joe Stoy, in his (by the way excellent) book "Denotational Semantics", tells following story:
"The decision which way round the digits run is, of course, mathematically trivial. Indeed, one early British computer had numbers running from right to left (because the spot on an oscilloscope tube runs from left to right, but in serial logic the least significant digits are dealt with first). Turing used to mystify audiences at public lectures when, quite by accident, he would slip into this mode even for decimal arithmetic, and write things like 73+42=16. The next version of the machine was made more conventional simply by crossing the x-deflection wires: this, however, worried the engineers, whose waveforms were all backwards. That problem was in turn solved by providing a little window so that the engineers (who tended to be behind the computer anyway) could view the oscilloscope screen from the back.
[C. Strachey - private communication.]"
You will play the role of the audience and judge on the truth value of Turing's equations.
Input
The input contains several test cases. Each specifies on a single line a Turing equation. A Turing equation has the form "a+b=c", where a, b, c are numbers made up of the digits 0,...,9. Each number will consist of at most 7 digits. This includes possible leading or trailing zeros. The equation "0+0=0" will finish the input and has to be processed, too. The equations will not contain any spaces.
Output
For each test case generate a line containing the word "True" or the word "False", if the equation is true or false, respectively, in Turing's interpretation, i.e. the numbers being read backwards.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.
Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.
Input
The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace. Input is terminated by EOF.
Output
For each test case output, if s is a subsequence of t.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Computer scientists live on pizza. Now the doctors say this is no good. We ought to eat more balanced. So you put your really large pizza onto your table and eat slice-by-slice carefully watching that the rest of your meal stays where it is - on the table.
Since computer scientists love pizza, their favourite table is shaped like a slice of pizza. However, different people may have different-sized tables. Everyone has his own preference for the number of slices a pizza has to be cut to. However, all agree that the slices must have identical size. Write a program to help the poor pizza lovers!
Input
The input file contains several test cases. Each test case starts with the number of slices n the pizza is cut to. Input is terminated by n=0. Otherwise, 1<=n<=9. Then follow 9 floating-point numbers px, py, r, tx, ty, ux, uy, vx, vy specifying the coordinates of the center p of the pizza, its radius, and the coordinates of three points t, u, v. They define the three corners of the slice-shaped table in counter-clockwise order, with t being the center.
The pizza is a homogeneous two-dimensional circular object. There is always a cut from its center parallel to the x-axis towards increasing x-values. The remaining pizza stays connected during the whole process, no matter what slices are removed. The distances from t to u, v are equal except for very small rounding errors. Tables are never larger than a half-circle.
Output
For each test case output on a line some possible ordering of slices, so that during the whole process of eating the pizza it does not fall down the table. Slices are numbered counter-clockwise starting with 1 directly above the positive x-axis.
If no ordering of slices exists, so that the pizza does not fall down, output a line containing the word "impossible" instead.
Remark
A connected, rigid, flat object remains fixed on a convex, flat surface if and only if the object's center of gravity lies above the surface. The x-coordinate, for example, of the center of gravity of an object s can be calculated by (∫sxds) / (∫sds). Likewise, the y-coordinate can be expressed as (∫syds) / (∫sds). Note that the denominator of these expressions gives the area of s.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
California Jones (the sister of famous Indiana Jones) once again faced a seemingly intractable problem. Her only hope was in you. She knew you were a computer scientist and you might have a clue.
Jones calls you on the video-phone and tells you the facts: she walked into a trap and now stands in front of a huge gate. On the left side strange signs can be seen while n stones lie on the right side. In front of the gate there are exactly n/2 holes. Says Jones, "I suppose I have to take exactly half of the stones from the right side and put them into the holes." Ancient writings confirm her conjecture. According to the writings it does not matter which hole a stone is placed into. It is only important that the right stones are chosen.
Nearby, Jones found a stone board, too, but was unable to interpret. It made sense to you though. It was a hint on how to sort the various possibilities of chosing n/2 stones.
But you couldn't yet figure out about the zeros and the ones. So you asked Jones who replied that "the same symbols I saw on the left side of the gate - only they were somewhat longer sequences. But I haven't met such a primitive civilization yet."
Now everything was clear to you: the symbols were the representation of a binary number - and it indicated which stones to choose. Simply ingenious! Jones was enthusiastic about you.
But it was impossible for Jones to calculate for a given binary number the corresponding stones. So she instructed you to write a program to solve the task and help her through the gate to freedom. Five hours later, she would call back.
Take a thorough look at the figure to the left depicting the stone board, as well as the sample input and output, to figure out how to solve Jones' problem.
Input
The input contains several testcases. Each starts with the number of stones n. Input is terminated by n=0. Otherwise, n is even and 2<=n<=32. The next n integers identify the stones. A test case is further subdivided into k (sub-) test cases, k being the next number in the input file. Then follow k times a bit string b (encoding a non-negative integer) and n/2 distinct integers identifying the set of chosen stones. No invalid stones will be chosen and the length of b will not exceed 30.
Output
For each (sub-) test case generate a line containing TRUE, if the chosen stones may be laid into the holes, and FALSE otherwise.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In an effort to minimize the expenses for foreign affairs the countries of the world have argued as follows. It is not enough that each country maintains diplomatic relations with at most one other country, for then, since there are more than two countries in the world, some countries cannot communicate with each other through (a chain of) diplomats.
Now, let us assume that each country maintains diplomatic relations with at most two other countries. It is an unwritten diplomatic "must be" issue that every country is treated in an equal fashion. It follows that each country maintains diplomatic relations with exactly two other countries.
International topologists have proposed a structure that fits these needs. They will arrange the countries to form a circle and let each country have diplomatic relations with its left and right neighbours. In the real world, the Foreign Office is located in every country's capital. For simplicity, let us assume that its location is given as a point in a two-dimensional plane. If you connect the Foreign Offices of the diplomatically related countries by a straight line, the result is a polygon.
It is now necessary to establish locations for bilateral diplomatic meetings. Again, for diplomatic reasons, it is necessary that both diplomats will have to travel equal distances to the location. For efficiency reasons, the travel distance should be minimized. Get ready for your task!
Input
The input contains several testcases. Each starts with the number n of countries involved. You may assume that n>=3 is an odd number. Then follow n pairs of x- and y-coordinates denoting the locations of the Foreign Offices. The coordinates of the Foreign Offices are integer numbers whose absolute value is less than 1012. The countries are arranged in the same order as they appear in the input. Additionally, the first country is a neighbour of the last country in the list. Input is terminated by EOF.
Output
For each test case output the number of meeting locations (=n) followed by the x- and y-coordinates of the locations. The order of the meeting locations should be the same as specified by the input order. Start with the meeting locations for the first two countries up to the last two countries. Finally output the meeting location for the n-th and the first country.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Read the statement of Diplomatic License! Given a list of meeting locations as specified in the description of Diplomatic License, you have to calculate the locations of the Foreign Offices.
Input
See the input specification of Diplomatic License for the format, and the output specification of Diplomatic License for the meaning of the input.
Output
See the output specification of Diplomatic License for the format, and the input specification of Diplomatic License for the meaning of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider a regular triangular area, divide it into four equal triangles of half height and remove the one in the middle. Apply the same operation recursively to each of the three remaining triangles. If we repeated this procedure infinite times, we'd obtain something with an area of zero. The fractal that evolves this way is called the Sierpinski Triangle. Although its topological dimension is 2, its Hausdorff-Besicovitch dimension is log(3)/log(2)~1.58, a fractional value (that's why it is called a fractal). By the way, the Hausdorff-Besicovitch dimension of the Norwegian coast is approximately 1.52, its topological dimension being 1.
For this problem, you are to outline the Sierpinski Triangle up to a certain recursion depth, using just ASCII characters. Since the drawing resolution is thus fixed, you'll need to grow the picture appropriately. Draw the smallest triangle (that is not divided any further) with two slashes, to backslashes and two underscores like this:
/
/__
To see how to draw larger triangles, take a look at the sample output.
Input
The input contains several testcases. Each is specified by an integer n. Input is terminated by n=0. Otherwise 1<=n<=10 indicates the recursion depth.
Output
For each test case draw an outline of the Sierpinski Triangle with a side's total length of 2n characters. Align your output to the left, that is, print the bottom leftmost slash into the first column. The output must not contain any trailing blanks. Print an empty line after each test case.
http://poj.org/problem?id=1941
連結
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Imagine you are attending your math lesson at school. Once again, you are bored because your teacher tells things that you already mastered years ago (this time he's explaining that (a+b)2=a2+2ab+b2). So you decide to waste your time with drawing modern art instead.
Fortunately you have a piece of squared paper and you choose a rectangle of size n×m on the paper. Let's call this rectangle together with the lines it contains a grid. Starting at the lower left corner of the grid, you move your pencil to the upper right corner, taking care that it stays on the lines and moves only to the right or up. The result is shown on the left:
Really a masterpiece, isn't it? Repeating the procedure one more time, you arrive with the picture shown on the right. Now you wonder: how many different works of art can you produce?
Input
The input contains several testcases. Each is specified by two unsigned 32-bit integers n and m, denoting the size of the rectangle. As you can observe, the number of lines of the corresponding grid is one more in each dimension. Input is terminated by n=m=0.
Output
For each test case output on a line the number of different art works that can be generated using the procedure described above. That is, how many paths are there on a grid where each step of the path consists of moving one unit to the right or one unit up? You may safely assume that this number fits into a 32-bit unsigned integer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Museum of Modern Art has a really exciting exhibition: a kind of a longish hall composed of a sequence of quadratic-shaped rooms. Each room is equipped with a water fountain. Each fountain is characterized by a number p and acts independent of the others. It will be turned on for exactly p seconds, then it will be turned off for exactly p seconds, then on again, then off again, and so on for good. However, different fountains may have different values of p. And even if they share the same value, they still may perform not identically, for they might have been started at different times.
You stand in front of the first room, and want to cross the hall to the other end. Each of your steps takes exactly 1 second. You are able to move one room forward (unless you already reached the other end), one room backward (unless you are at the beginning), or just stay at your current position. Calculate the shortest time to reach the other end, if it is possible at all.
Since you do not want to get wet, you can only move into a room where the water fountain will be off during the second after your step. For example, suppose that the fountain in the next room behaves so, that it is on at times 0, 1, 2, then off at times 3, 4, 5, 6, then on at times 7, 8, 9, 10, then off again (which indicates p=4 with an offset of 7). Then, you can move at time 2 into the room, arriving there at time 3, when the fountain is off. But you cannot move at time 6 into the room, because at time 7 it will be on.
Input
The input contains several test cases. Each test case starts with the number of fountains n. Input is terminated by n=0. Otherwise, 1<=n<=100. Then follow n numbers pi denoting the time each fountain is on and off, where 0<=pi<=10. A value of 0 for pi indicates that fountain i is out of order (i.e. constantly off). Then follow n numbers qi denoting the offset of each fountain, where 0<=qi<2*pi, unless the fountain is out of order, in which case qi is meaningless. Otherwise it means that fountain i will be on at time qi, but off just one second before.
Output
For each test case output on a line a single number t denoting the shortest time needed to reach the end of the hall (i.e. to enter the place after the last room). Assume, that you are in front of the first room at time 0 (i.e. you can enter the first room at time 1, if the fountain is off at time 1). If it is impossible to go through the hall of fountains, print 0 instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After the 1997/1998 Southwestern European Regional Contest (which was held in Ulm) a large contest party took place. The organization team invented a special mode of choosing those participants that were to assist with washing the dirty dishes. The contestants would line up in a queue, one behind the other. Each contestant got a number starting with 2 for the first one, 3 for the second one, 4 for the third one, and so on, consecutively.
The first contestant in the queue was asked for his number (which was 2). He was freed from the washing up and could party on, but every second contestant behind him had to go to the kitchen (those with numbers 4, 6, 8, etc). Then the next contestant in the remaining queue had to tell his number. He answered 3 and was freed from assisting, but every third contestant behind him was to help (those with numbers 9, 15, 21, etc). The next in the remaining queue had number 5 and was free, but every fifth contestant behind him was selected (those with numbers 19, 35, 49, etc). The next had number 7 and was free, but every seventh behind him had to assist, and so on.
Let us call the number of a contestant who does not need to assist with washing up a lucky number. Continuing the selection scheme, the lucky numbers are the ordered sequence 2, 3, 5, 7, 11, 13, 17, etc. Find out the lucky numbers to be prepared for the next contest party.
Input
The input contains several test cases. Each test case consists of an integer n. You may assume that 1<=n<=3000. A zero follows the input for the last test case.
Output
For each test case specified by n output on a single line the n-th lucky number.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e., bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.
Input
The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.
Output
For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A technique used in early programming contest strategies involved partitioning the available intellectual capacity of a team into a number of members with each member having a fixed amount of intelligence, different members potentially having different amounts. The sum of the brightness of all members equals the total intellectual capacity of the team.
Given a set of problems, it was the task of the team to assign the problems to different team members, so that they could be solved concurrently. This was made difficult due to the fact that the solution time of a problem might depend on the amount of intelligence available to it. Every problem has a minimum intelligence requirement, but if assigned to a brighter member its solution time might increase or decrease.
In this task, you have to determine optimal assignments of problems to team members. Your program is given the intellectual capacities of the team members available for the solution of problems, and for each problem a description of how its solution time depends on the amount of intelligence available to it. Your program has to find the solution schedule of the problems that minimizes the average solution time for the problems. A solution schedule is an assignment of problems to team members and times, such that no two problems use the same member at the same time, and no problem is assigned to a team member with less brightness than its minimum requirement. The solution time of the problem is the difference between the time when the problem was submitted to be solved (which is the start of the contest at time zero for all problems in this task), and the time that the problem is solved.
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 team members (1 <= m <= 3), and n specifies the number of problems to be solved (1 <= n <= 10).
The next line contains m positive integers giving the intelligence amounts of the m team members. Following this are n lines, describing the time-brightness tradeoffs for each of the n problems. Each line starts with a positive integer k (k <= 10), followed by k pairs of positive integers s1,t1,s2,t2,...,sk,tk that satisfy si < si+1 for 1 <= i < k. The minimum intelligence requirement of the problem is s1, i.e. it cannot be solved by a member with less intellectual capacity than this number. If the problem is solved by a team member with brightness s, where si <= s < si+1 for some i, then its solution time will be ti. Finally, if the problem is solved by a team member with intellectual capacity sk or more, then its execution time will be tk.
A pair of zeroes will follow the input for the last test case.
You may assume that each problem will be solved in exactly the time specified for the given brightness, regardless of the number of other problems being solved by other team members at the same time. No problem will have an intelligence requirement larger than that of the brightest team member.
Output
For each test case, first display the case number (starting with 1 and increasing sequentially). Then print the minimum average solution time for the set of problems with two digits to the right of the decimal point. Follow this by the description of a solution schedule that achieves this average solution time. Display one line for each problem, in the order they were given in the input, that identifies the problem number, the member used to solve it (numbered in the order given in the input), the time when the member started to solve the problem, and the time when the problem was solved. Follow the format shown in the sample output, and print a blank line after each test case. If special judge has problem please contact kerker.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A good drink is always served on ice. That said, the amount of ice is what makes the difference. If it is too much, the drink will be well cooled, however, this is a bit of fraud as there could be less ice (and more Vodka for example). On the other hand, if there is too little ice the drink is warm which is unacceptable. You are to help the bartender, of course neither with mixing nor drinking, but with calculating the expected outcome of such mixtures.
To make things easier, we assume that pure water is mixed with ice in a closed system, i.e., there is no problem with the outside temperature or the warming of the bottle, etc. Therefore, after a some time has passed, the system may be regarded as balanced (there is no further change in temperature and no more melting or freezing). Your job is to calculate the final temperature of this balanced system and the amount of ice and water in this equilibrium state.
As you know from physics, it takes 4.19 Joule to heat one gram of water one Kelvin, whereas it takes 2.09 Joule if it is ice. We define the capacities cw = 4.19 J/(g*K) and ci = 2.09 J/(g*K). Melting one gram of ice takes 335 Joule, where the temperature remains constant at zero. We define the constant em = 335 J/g. The total thermal energy of the ice and the water before the experiment is equal to the thermal energy of the final mixture.
The figure below shows the energy of one gram of ice, ice-water-mixture, or water, where the temperature is measured relative to -30 degrees Celsius. The jump at 0 degrees represents the melting of ice to water. The amount of energy gained is proportional to the amount of ice already melted.
Input
The input contains several test cases. Each test case consists of four real numbers mw, mi, tw, ti. The mass of water mw and the mass of ice mi are both non-negative, given in grams, and mw + mi > 0. The water temperature tw and the ice temperature ti follow, both given in degrees Celsius, and you may assume that -30 < ti <= 0 <= tw < 100. The last test case is followed by four zeroes.
Output
For each test case output the amount of ice and water in grams and the final temperature of the mixture in degrees Celsius. All numbers must be rounded to one digit. Adhere to the sample output for the exact format to use.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
For products that are wrapped in small packings it is necessary that the sheet of paper containing the directions for use is folded until its size becomes small enough. We assume that a sheet of paper is rectangular and only folded along lines parallel to its initially shorter edge. The act of folding along such a line, however, can be performed in two directions: either the surface on the top of the sheet is brought together, or the surface on its bottom. In both cases the two parts of the rectangle that are separated by the folding line are laid together neatly and we ignore any differences in thickness of the resulting folded sheet.
After several such folding steps have been performed we may unfold the sheet again and take a look at its longer edge holding the sheet so that it appears as a one-dimensional curve, actually a concatenation of line segments. If we move along this curve in a fixed direction we can classify every place where the sheet was folded as either type A meaning a clockwise turn or type V meaning a counter-clockwise turn. Given such a sequence of classifications, produce a drawing of the longer edge of the sheet assuming 90 degree turns at equidistant places.
Input
The input contains several test cases, each on a separate line. Each line contains a nonempty string of characters A and V describing the longer edge of the sheet. You may assume that the length of the string is less than 200. The input file terminates immediately after the last test case.
Output
For each test case generate a PostScript drawing of the edge with commands placed on separate lines. Start every drawing at the coordinates (300,420) with the command "300 420 moveto". The first turn occurs at (310,420) using the command "310 420 lineto". Continue with clockwise or counter-clockwise turns according to the input string, using a sequence of "x y lineto" commands with the appropriate coordinates. The turning points are separated at a distance of 10 units. Do not forget the end point of the edge and finish each test case by the commands stroke and showpage.
You may display such drawings with the gv PostScript interpreter, optionally after a conversion using the ps2ps utility.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Read the statement of problem E: Edge to understand how to fold a sheet of paper and how to interpret the input. We define a "stripe" to be a maximally large part of the sheet that has no folding line going through. Since the turns occur at equidistant places, all stripes are congruent.
In this problem you are given the description of the result of performing several folding steps as in problem E: Edge, i.e., in the unfolded state. Additionally, you know that the length of the sheet in its folded state is exactly the length of 1 stripe (again, we ignore thickness).
Find the minimum number of folding steps necessary to generate the described sheet from an initially flat sheet of paper. Note that performing a folding step may create more than one turn in the result because parts of the sheet already overlay due to previous folding steps. When a step is carried out, however, all overlaying parts of the sheet are affected, i.e., it is not allowed to fold, say, only the top three layers.
Finally, note that every result can be obtained by iterating through the turns in a fixed direction and performing a folding step at each turn, thereby accumulating a 1 stripe long stack of all stripes. If n is the number of turns in the input description, this procedure in fact requires n folding steps, which is not necessarily minimal as can be observed in the sample output.
Input
The input contains several test cases, each on a separate line. Each line contains a nonempty string of characters A and V describing the longer edge of the sheet. You may assume that the length of the string is less than 200. The input file terminates immediately after the last test case.
Output
For each test case print on a line the minimum number of folding steps required to produce the described sheet of paper.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The connections between mathematics and biology are complicated. Most of the time they do not run along nice-looking links that merrily join at first glance, but they are abstract and not always easily established.
Lake Vostok - about 14000 square kilometers large, up to 650 meters deep, and covered by 3743 meters of ice - was recently discovered on the Antarctic continent. The lake remained under conditions of high pressure and no sunlight for several millions of years. It is believed that ordinary life has evolved to a more efficient form using a genetic code composed of only three bases (the current state of ignorance proclaims the four bases adenine, cytosine, guanine, and thymine). Until reasonable names are found, the three bases will be abbreviated as N, O, and P.
Moreover, the genome is single-stranded and directed, i.e., we may see it as a sequence over the alphabet {N,O,P}. Unless risking instability, it is necessary that the genome is a Thue-sequence, due to the Norwegian mathematician A. Thue (1863-1922). Define a subsegment of a sequence to be a connected subsequence, and call two subsegments adjacent if one follows immediately after the other in the sequence. A Thue-sequence is a sequence where no adjacent subsegments are equal. For example, NOPNO is and NOPNPNO is not a Thue-sequence, so that the first may be a genome whereas the second may not.
To be able to simulate experiments with the new genomes, you are asked to generate genomes of certain lengths.
Input
The input contains several test cases. Each test case consists of an integer n. You may assume that 1<=n<=5000. The last test case is followed by a zero.
Output
For each test case specified by n output on a single line any genome of length n. If no genome of length n exists, output a blank line instead.
wait for special judge
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Operating systems are large software artefacts composed of many packages, usually distributed on several media, e.g., discs. You probably remember the time when your favourite operating system was delivered on 21 floppy discs, or, a few years later, on 6 CDs. Nowadays, it will be shipped on several DVDs, each containing tens of thousands of packages.
The installation of certain packages may require that other packages have been installed previously. Therefore, if the packages are distributed on the media in an unsuitable way, the installation of the complete system requires you to perform many media changes, provided that there is only one reading device available, e.g., one DVD-ROM drive. Since you have to start the installation somehow, there will of course be one or more packages that can be installed independently of all other packages.
Given a distribution of packages on media and a list of dependences between packages, you have to calculate the minimal number of media changes required to install all packages. For your convenience, you may assume that the operating system comes on exactly 2 DVDs.
Input
The input contains several test cases. Every test case starts with three integers N1, N2, D. You may assume that 1<=N1,N2<=50000 and 0<=D<=100000. The first DVD contains N1 packages, identified by the numbers 1, 2, ..., N1. The second DVD contains N2 packages, identified by the numbers N1+1, N1+2, ..., N1+N2. Then follow D dependence specifications, each consisting of two integers xi, yi. You may assume that 1<=xi,yi<=N1+N2 for 1<=i<=D. The dependence specification means that the installation of package xi requires the previous installation of package yi. You may assume that there are no circular dependences. The last test case is followed by three zeros.
Output
For each test case output on a line the minimal number of DVD changes required to install all packages. By convention, the DVD drive is empty before the installation and the initial insertion of a disc counts as one change. Likewise, the final removal of a disc counts as one change, leaving the DVD drive empty after the installation.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Propositions are logical formulas consisting of proposition symbols and connecting operators. They are recursively defined by the following rules:
1. All proposition symbols (in this problem, lower-case alphabetic characters, e.g., a and z) are propositions.
2. If P is a proposition, (!P) is a proposition, and P is a direct subformula of it.
3. If P and Q are propositions, (P&Q), (P|Q), (P-->Q), and (P<->Q) are propositions, and P and Q are direct subformulas of them.
4. Nothing else is a proposition.
The operations !, &, |, -->, and <-> denote logical negation, conjunction, disjunction, implication, and equivalence, respectively. A proposition P is a subformula of a proposition R if P=R or P is a direct subformula of a proposition Q and Q is a subformula of R.
Let P be a proposition and assign boolean values (i.e., 0 or 1) to all proposition symbols that occur in P. This induces a boolean value to all subformulas of P according to the standard semantics of the logical operators:
negation conjunction disjunction implication equivalence
!0=1 0&0=0 0|0=0 0-->0=1 0<->0=1
!1=0 0&1=0 0|1=1 0-->1=1 0<->1=0
1&0=0 1|0=1 1-->0=0 1<->0=0
1&1=1 1|1=1 1-->1=1 1<->1=1
This way, a value for P can be calculated. This value depends on the choice of the assignment of boolean values to the proposition symbols. If P contains n different proposition symbols, there are 2n different assignments. To evaluate all possible assignments we may use truth tables.
A truth table contains one line per assignment (i.e., 2n lines in total). Every line contains the values of all subformulas under the chosen assignment. The value of a subformula is aligned with the proposition symbol, if the subformula is a proposition symbol, and with the center of the operator otherwise.
Input
The input contains several test cases, each on a separate line. Every test case denotes a proposition and may contain arbitrary amounts of spaces in between. The input file terminates immediately after the newline symbol following the last test case.
Output
For each test case generate a truth table for the denoted proposition. Start the truth table by repeating the input line. Evaluate the proposition (and its subformulas) for all assignments to its variables, and output one line for each assignment. The line must have the same length as the corresponding input line and must consist only of spaces and the characters 0 and 1. Output an empty line after each test case.
Let s1,...,sn be the proposition symbols in the denoted proposition sorted in alphabetic order. Then, all assignments of 0 to s1 must precede the assignments of 1 to s1. Within each of these blocks of assignments, all assignments of 0 to s2 must precede the assignments of 1 to s2, and so on.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need a key but you are required to enter the correct n-digit code on a keypad (as if this were something new!). There are several models available, from toy safes for children (with a 2-digit code) to the military version (with a 6-digit code).
The safe will open as soon as the last digit of the correct code is entered. There is no "enter" key. When you enter more than n digits, only the last n digits are significant. For example (in the 4-digit version), if the correct code is 4567, and you plan to enter the digit sequence 1234567890, the door will open as soon as you press the 7 key.
The software to create this effect is rather simple. In the n-digit version the safe is always in one of 10n-1 internal states. The current state of the safe simply represents the last n-1 digits that have been entered. One of these states (in the example above, state 456) is marked as the unlocked state. If the safe is in the unlocked state and then the right key (in the example above, 7) is pressed, the door opens. Otherwise the safe shifts to the corresponding new state. For example, if the safe is in state 456 and then you press 8, the safe goes into state 568.
A trivial strategy to open the safe is to enter all possible codes one after the other. In the worst case, however, this will require n * 10n keystrokes. By choosing a good digit sequence it is possible to open the safe in at most 10n + n - 1 keystrokes. All you have to do is to find a digit sequence that contains all n-digit sequences exactly once. KEY Inc. claims that for the military version (n=6) the fastest computers available today would need billions of years to find such a sequence - but apparently they don't know what some programmers are capable of...
Input
The input contains several test cases. Every test case is specified by an integer n. You may assume that 1<=n<=6. The last test case is followed by a zero.
Output
For each test case specified by n output a line containing a sequence of 10n + n - 1 digits that contains each n-digit sequence exactly once.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Flavius Josephus and 40 fellow rebels were trapped by the Romans. His companions preferred suicide to surrender, so they decided to form a circle and to kill every third person and to proceed around the circle until no one was left. Josephus was not excited by the idea of killing himself, so he calculated the position to be the last man standing (and then he did not commit suicide since nobody could watch).
We will consider a variant of this "game" where every second person leaves. And of course there will be more than 41 persons, for we now have computers. You have to calculate the safe position. Be careful because we might apply your program to calculate the winner of this contest!
Input
The input contains several test cases. Each specifies a number n, denoting the number of persons participating in the game. To make things more difficult, it always has the format "xyez" with the following semantics: when n is written down in decimal notation, its first digit is x, its second digit is y, and then follow z zeros. Whereas 0<=x,y<=9, the number of zeros is 0<=z<=6. You may assume that n>0. The last test case is followed by the string 00e0.
Output
For each test case generate a line containing the position of the person who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2. For example, if there are 5 persons in the circle, counting proceeds as 2, 4, 1, 5 and person 3 is staying alive.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Your task is to write a program that performs a simple form of run-length encoding, as described by the rules below.
Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones.
Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the sequence, it is escaped with a 1, thus two 1 characters are output.
Input
The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input.
Output
Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
To play the "fraction game" corresponding to a given list f1, f2, ..., fk of fractions and starting integer N, you repeatedly multiply the integer you have at any stage (initially N) by the earliest fi in the list for which the answer is integral. Whenever there is no such fi, the game stops.
Formally, we define a sequence by S0=N, and Sj+1=fiSj, if for 1<=i<=k, the number fiSj is an integer but the numbers f1Sj, ..., fi-1Sj are not.
For example, if we have the list of eight fractions f1=170/39, f2=19/13, f3=13/17, f4=69/95, f5=19/23, f6=1/19, f7=13/7, f8=1/3, and start with N=21, we produce the (finite) sequence (21,39,170,130,190,138,114,6,2). In general, the sequence may be infinite.
Given a fraction list and a starting integer calculate a part of the defined sequence. Actually, we are interested only in the powers of 2 that appear in the sequence.
Input
The input contains several test cases. Every test case starts with three integers m, N, k. You may assume that 1<=m<=40, 1<=N<=1000, and 1<=k<=100. Then follow k fractions f1, ..., fk. For each fraction, first its numerator is given, followed by its denominator. You may assume that both are positive integers less than 1000 and their greatest common divisor is 1. The last test case is followed by a zero.
Output
For each test case output on a line m numbers e1, ..., em, separated by one space character, such that 2e1, ..., 2ek are the first m numbers in the defined sequence that are powers of 2. You may assume that there are at least m powers of 2 among the first 7654321 elements of the sequence.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the following we define the basic terminology of trees. A tree is defined inductively: It has a root which is either an external node (a leaf), or an internal node having a sequence of trees as its children. An internal node is also called the parent of the roots of its child trees. The level of a node in a tree is defined inductively: The root has level 0, and the level of a node is 1 more than the level of its parent node.
Every internal node of a binary tree has precisely two children, its left sub-tree and its right sub-tree. Every internal node of a labelled binary tree is additionally marked with a string, its label. A binary search tree is a labelled binary tree where every internal node t satisfies the following condition: All labels of nodes in the left sub-tree of t are less than the label of t which is, in turn, less than all labels of nodes in the right sub-tree of t. For this condition, we assume lexicographic, i.e., alphabetic order on the strings.
An inorder traversal of a tree is defined recursively: A leaf is just visited, and for an internal node first its left sub-tree is traversed inorder, then the node itself is visited, finally its right sub-tree is traversed inorder. It follows that an inorder traversal of a binary search tree yields the labels in lexicographic order. Note that binary search trees whose shapes differ may nevertheless yield the same sequence of strings while being traversed inorder.
When a given string s is looked for in a binary search tree, we compare s to the label l of the root. We are done if s=l, otherwise if s
The number of comparisons performed in such a search procedure depends on s and the actual shape of the search tree. Therefore, there is an interest in constructing binary search trees that store a given sequence of strings but provide as efficient access as possible. Of course, we don't know in advance which strings will be looked up in the tree, so we need to make some assumptions.
Let n be the number of strings that are to be stored in the binary search tree. Let K1,...,Kn be these strings in lexicographic order. Let p1,...,pn and q0,...,qn be 2n+1 non-negative real numbers such that ∑i=1..n pi + ∑i=0..n qi = 1. The interpretation of these numbers is:
• pi = probability that the search argument s is Ki.
• qi = probability that s lies (lexicographically) strictly between Ki and Ki+1.
By convention, q0 is the probability that s is less than K1, and qn is the probability that s is greater than Kn. We want to find a binary search tree containing nodes with labels K1,...,Kn that minimises the expected number of comparisons in the search, namely
cost = ∑i=1..n pi*(1 + level of internal node Ki) + ∑i=0..n qi*(level of leaf between Ki and Ki+1).
The leaf between Ki and Ki+1 is that leaf reached in the search for a string s that lies (lexicographically) strictly between Ki and Ki+1. Adhere to the convention stated above for the border cases.
The following figure illustrates the first test case of the sample input. It shows the two possible binary search trees, the probabilities and the associated costs. 
.bmp)
Input
The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=200. Then follow 2n+1 non-negative integers denoting frequencies. Let s be the sum of all frequencies. You may assume that 1<=s<=1000000. The probabilities p1,...,pn and q0,...,qn are calculated in this order by dividing the frequencies by s. The last test case is followed by a zero.
Output
For each test case devise a binary search tree whose cost is minimal for the specified probabilities. Output the integer cost*s for such a tree.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Read the statement of problem G for the definitions concerning trees. In the following we define the basic terminology of heaps. A heap is a tree whose internal nodes have each assigned a priority (a number) such that the priority of each internal node is less than the priority of its parent. As a consequence, the root has the greatest priority in the tree, which is one of the reasons why heaps can be used for the implementation of priority queues and for sorting.
A binary tree in which each internal node has both a label and a priority, and which is both a binary search tree with respect to the labels and a heap with respect to the priorities, is called a treap. Your task is, given a set of label-priority-pairs, with unique labels and unique priorities, to construct a treap containing this data.
Input
The input contains several test cases. Every test case starts with an integer n. You may assume that 1<=n<=50000. Then follow n pairs of strings and numbers l1/p1,...,ln/pn denoting the label and priority of each node. The strings are non-empty and composed of lower-case letters, and the numbers are non-negative integers. The last test case is followed by a zero.
Output
For each test case output on a single line a treap that contains the specified nodes. A treap is printed as (