Description
ICPC (International Collegiate Programming Contest), as you might know, is a team programming contest for college students. Each team consists of exactly three students and they will work on a number of programming problems.
Andi, Budi and Chandra plan to participate in this year ICPC as a team. As for their team strategy, they come up with a simple one:
In the first 20 minutes of 5 hours contest, they will read through all problems. Then each of them will assign a number to each problem. This number indicates how many minute(s) it will take for him to get the problem accepted (correct solution). Then they will start to code, meaning that they only have 280 minutes to really work on the problems. You may assume that they always get accepted on time whenever they work on a problem.
There's only one computer for each team, so it's not possible for them to code two different problems simultaneously.
To avoid any brain fatigue and adrenaline rush (because they attend competitions so frequently), they decided to switch role after each problem, such that none of them will work at the computer for more than one problem consecutively.
They want to solve as many problems as they can. The order of problem to be solved does not matter.
Input
The first line of input contains an integer T , number of test cases to follow. Each case begins with an integer N (1N12) in one line, denoting the number of problems. The second line contains N integers, A1..N (1Ai300) , denoting the total time (in minutes) needed by Andi to solve ith problem. The third and fourth line will correspond to the total time needed by Budi and Chandra respectively and will have the same input format as the second line.
Output
For each case, print in a single line containing the maximum total number of problem that can be solved by that team.
Explanation for 1st sample case:
Actually Andi could solve all the three problems alone, but the team has decided that none of them should work at the computer for more than one problem consecutively.
Explanation for 2nd sample case:
The team can solve all the problems. Here is one solution:
Let Budi work on Problem-2 (100 minutes).
Switch to Andi and let him work on Problem-1 (50 minutes).
Switch to Budi again and let him work on Problem-3 (30 minutes).
Finally, switch to Chandra and let him work on Problem-4 which (100 minutes).
Overall, they need 100 + 50 + 30 + 100 = 280 minutes.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Tetris Battle is a hot and funny game on the 
that you can train your skill and challenge your friend.
At the last of the story, you will receive the name that “God of Tetris” and everybody’s respecting. But this problem is not about Tetris Battle.
We will talk the other funny game, “Step Mania”!
“Step Mania” is an engine of the music game.
For each meter, there is four floating up arrows, and we can use keyboard to “hit” it on fixed positions. And there is a system for rewarding, we called “Combo” if you hit arrows in continued meter and get extra score.
NOW there is a new “Step Mania EX” had at most 10 arrows you should hit for each meter.(It’s OK because the keyboard has 108 keys and you have ten fingers.)
You are an extreme player of the “Step Mania” and you can hit every arrow in every meter!
But your keyboard is so bad that is unlike your skill, it cannot detect the continued hits on same key.
Now there is a score for a song in “Step Mania EX”, what score you will have?
PS1. You have gotten one point if you hit an arrow and (#theNumberOfCombo-1) for bonus.
PS2. If the computer does not detect any arrow in a meter, the number of combo will be reset.
PS3. Though you will get higher score if you do not hit some arrow, you still hit EVERY arrow because the spirit of “Step Mania” tell you not to do it!
PS4. At fact, it not yet sells.
PS5. You can buy the keyboard called “RealForce” and you can win the game easily though it’s very expensive.
HINT: Each arrow hiting will have its bonus score.
For sample data,
you will get score as following:
1 0 0 1
0 2 2 0
0 X 0 1
1 X 1 0
HINT2:
If there a meter contains no arrow, you will not hit any key and the number of combos will be same such that it can be higher when you have a nice hiting in next meter.
Input
There is multiple dataset, for each data:
The first line contains two integers n, m , which mean the number of meters and the number of the arrow type. (0 < n ≤ 105, 0 < m ≤ 10)
The line 2 to the line n+1, each line has m numbers split by space means the arrows if the number is 1.
Output
Print out a line contains the number of the score for each dataset.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase ``domino effect'' comes from).
While this is somewhat pointless with only a few dominoes, some people went to the opposite extreme in the early Eighties. Using millions of dominoes of different colors and materials to fill whole halls with elaborate patterns of falling dominoes, they created (short-lived) pieces of art. In these constructions, usually not only one but several rows of dominoes were falling at the same time. As you can imagine, timing is an essential factor here.
It is now your task to write a program that, given such a system of rows formed by dominoes, computes when and where the last domino falls. The system consists of several ``key dominoes'' connected by rows of simple dominoes. When a key domino falls, all rows connected to the domino will also start falling (except for the ones that have already fallen). When the falling rows reach other key dominoes that have not fallen yet, these other key dominoes will fall as well and set off the rows connected to them. Domino rows may start collapsing at either end. It is even possible that a row is collapsing on both ends, in which case the last domino falling in that row is somewhere between its key dominoes. You can assume that rows fall at a uniform rate.
Input
The input file contains descriptions of T domino systems (T ≤ 30). The first line of each description contains two integers: the number n of key dominoes (1 ≦ n < 500) and the number m of rows between them. The key dominoes are numbered from 1 to n. There is at most one row between any pair of key dominoes and the domino graph is connected, i.e. there is at least one way to get from a domino to any other domino by following a series of domino rows.
The following m lines each contain three integers a, b, and l, stating that there is a row between key dominoes a and b that takes l seconds to fall down from end to end.
Each system is started by tipping over key domino number 1.
The file ends with an empty system (with n = m = 0), which should not be processed.
Output
For each case output a line stating the number of the case (`System #1', `System #2', etc.). Then output a line containing the time when the last domino falls, exact to one digit to the right of the decimal point, and the location of the last domino falling, which is either at a key domino or between two key dominoes. If the last domino is between key domino A and key domino B, you should output the smaller one first and then the larger one. For example, if A = 5, B = 3, and the falling time of last domino is 3.0, you should output "The last domino falls after 3.0 seconds, between key dominoes 3 and 5.". Adhere to the format shown in the output sample. It is guaranteed that only one such output exists. Output a blank line after each system.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
ADP is a cute caterpillar living in the SK (Shik Kingdom). According to the tradition, every caterpillar in SK must go to the LAND once in the lifetime, hence ADP has just decided to make a journey. However, it's not that easy to go to the LAND, ADP will encounter birds, which will eat caterpillars, during the trip. Luckily, birds will only appear on roads between cities, so ADP can just stay in city for a while to wait for birds to fly away. ADP wrote a program to analyze the behavior of birds and find out when those birds will show up. Unfortunately, ADP is not familiar with Dijkstra
hence just can't write a program to figure out how much time this trip will takes. In order to accomplish her dream, she asks her smartest friend, you, to write the program. Can you help her?
Input
There's only one integer T in the first line, representing the number of test cases. The first line of each test case contains two integers N, M, the number of cities and the number of roads. city0 is ADP's hometown and cityn-1 is the LAND. Each of the next M lines describes one road. There're at least four integers in each line, V1, V2, C, D, indicating that it's a bidirectional road between cityv1 , cityv2 and ADP will need C units of time to crawl through it. The next D integers T1, T2… TD in the line represents that birds will show up at this road at time T1, T2… TD. ADP will be eaten if she's still crawling on this road while birds show up. We guarantee that there's a path to get to the LAND.
1<=T<=10
1<=N, M, ΣD<=2*10^5
1<=C<=2000
0<=Ti<=2^31-1
Output
Output the minimum units of time that ADP needs to get to the LAND for each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In an infinite binary tree:
- In an infinite binary tree:
- If a node is labeled with the integer X, then its left child is labeled 2X and its right child 2X+1.
- The root of the tree is labeled 1.
A walk on the binary tree starts in the root. Each step in the walk is either a jump onto the left child, onto the right child, or pause for rest (stay in the same node). A walk is described with a string of letters 'L', 'R' and 'P':
- 'L' represents a jump to the left child;
- 'R' represents a jump to the right child;
- 'P' represents a pause.
The value of the walk is the label of the node we end up on. For example, the value of the walk LR is 5, while the value of the walk RPP is 3.
A set of walks is described by a string of characters 'L', 'R', 'P' and '*'. Each '*' can be any of the three moves; the set of walks contains all walks matching the pattern.
For example, the set L*R contains the walks LLR, LRR and LPR. The set ** contains the walks LL, LR, LP, RL, RR, RP, PL, PR and PP.
Finally, the value of a set of walks is the sum of values of all walks in the set. Calculate the value of the given set of walks.
Input
The first line of the input is an integer Z (1 <= Z <= 15), which means the number of test cases. For each test case, one line containing a string describing the set. Only characters 'L', 'R', 'P' and '*' will appear and there will be at most 10000 of them.
Output
For each test case, output the test case number and the value of the set.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:
Deletion: a letter in x is missing in y at a corresponding position.
Insertion: a letter in y is missing in x at a corresponding position.
Change: letters at corresponding positions are distinct
Certainly, we would like to minimize the number of all possible operations.
Illustration
A G T A A G T * A G G C
| | | | | | |
A G T * C * T G A C G C
Deletion: * in the bottom line
Insertion: * in the top line
Change: when the letters at the top and bottom are distinct
This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we could be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like
A G T A A G T A G G C
| | | | | | |
A G T C T G * A C G C
and 4 moves would be required (3 changes and 1 deletion).
In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≤ m.
Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.
Write a program that would minimize the number of possible operations to transform any string x into a string y.
Input
Input contains several datasets. Each dataset consists of the strings x and y prefixed by their respective lengths, one in each line.
Output
For each dataset, an integer representing the minimum number of possible operations to transform any string x into a string y.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Singapore will host a Formula One race in 2008. The race will be held on a 5.067km long street circuit, consisting of 14 left hand turns and 10 right hand turns. In the run up to the F1 race, the number of illegal night street racing activities have been on the rise. Such races consists of several rounds around a designated street circuit.
The authorities would like to deploy a new vehicle monitoring system in order to catch these illegal Saint Andrew's Road, part of the Formula One circuit racers. The system consists of a (Kenny Pek, Piccom) number of cameras mounted along various roads. For the system to be effective, there should be at least one camera along each of the possible circuits.
The Singapore road system can be represented as a series of junctions and connecting bidirectional roads (see Figure 5). A possible racing circuit consists of a start junction followed by a path consisting of three or more roads that eventually leads back to the start junction. Each road in a racing circuit can be traversed only in one direction, and only once.
Your task is to write a program that computes the optimal placement of the vehicle-monitoring cameras. You will be provided with a description of a connected road network to be monitored in terms of the roads and junctions. The junctions are identified by the bigger numbers in Figure 5. A camera can be deployed on the roads (and not the junctions).
The cost of deploying a camera depends on the road on which it is placed. The smaller numbers by the roads in Figure 5 indicate the cost of deploying a camera on that road. Your job is to select a set of roads that minimizes the total cost of deployment while ensuring that there is at least one camera along every possible racing circuit (i.e. loop in the road network).
Input
The input consists of a line containing the number c of datasets, followed by c datasets, followed by a line containing the number `0'.
The first line of each dataset contains two positive integers, n and m , separated by a blank, which represent the number of junctions and number of roads, respectively. You may assume that 0 < n < 10000 and 0 < m < 100000 . For simplicity, we label each of the n junctions from 1 to n . The following m lines of each dataset each describes one road. Each line consists of three positive integers which are the labels of two different junctions and the cost of deploying a camera on this road. The cost of deploying a camera is between 1 and 1000.
Output
The output consists of one line for each dataset. The c -th line contains one single number, representing the minimal cost of setting up the vehicle monitoring system such that there is at least one camera along every possible circuit.
Note: This data set depicts the situation shown in Figure 5. The two cameras show where cameras might be placed in order to monitor each circuit at minimal cost. Since each of the cameras have a cost of 3, the total minimal cost is 6.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2565
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3835
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You live in a small well-planned rectangular town in Phuket. The size of the central area of the town is H kilometers x W kilometers. The central area is divided into HW unit blocks, each of size 1 x 1 km2. There are H + 1 streets going in the West to East direction, and there are W + 1 avenue going in the North-South direction. The central area can be seen as a rectangle on the plane, as shown below.
We can identify each intersection by its co-ordinate on the plane. For example, on the Figure above the bottom-left corner is intersection (0,0), and the top-right corner is intersection (6,3).
Your house is at the bottom-left corner (i.e., intersection (0,0)) and you want to go to the university at the top-right corner (i.e., intersection (W,H)). More over, you only want to go to the university with wasting any efforts; therefore, you only want to walk from West-to-East and South-to-North directions. Walking this way, in the example above there are 84 ways to reach the university.
You want to go to the university for K days. Things get more complicated when each morning, the city blocks parts of streets and avenues to do some cleaning. The blocking is done in such a way that it is not possible to reach parts of the streets or avenues which is blocked from some other part which is blocked as well through any paths containing only West-to-East and South-to-North walks.
You still want to go to the university using the same West-to-East and South-to-North strategy. You want to find out for each day, how many ways you can reach the university by only walking West-to-East and South-to-North. Since the number can be very big, we only want the result modulo 2552.
Input
The first line contains an integer T, the number of test cases (1 < T < 5). Each test case is in the following format.
The first line of each test case contains 3 integers: W, H, and K (1 < W < 1,000; 1 < H < 1,000; 1 < K < 10,000). W and H specify the size of the central area. K denotes the number of days you want to go to the university.
The next K lines describe the information on broken parts of streets and avenues. More specifically, line 1 + i, for 1 < i < K, starts with an integer Qi (1 < Qi < 100) denoting the number of parts which are blocked. Then Qi sets of 4 integers describing the blocked parts follow. Each part is described with 4 integers, A, B, C, and D (0 < A < C < W; 0 < B < D < H) meaning that the parts connecting intersection (A,B) and (C,D) is blocked. It is guaranteed that that part is a valid part of the streets or avenues, also C - A < 1, and D - B < 1, i.e., the part is 1 km long.
Output
For each test case, for each day, your program must output the number of ways to go to the university modulo 2552 on a separate line. i.e., the output for each test case must contains K lines.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Alfred wants to plan what to cook in the next days. He can cook various dishes. For each dish the costs of the ingredients and the benefit value is known. If a dish is cooked the second time in a row, the benefit value for the second time is 50 percent of the benefit value of first time, if it is prepared for the third or higher time in a row, the benefit value is 0. For example cooking a dish with benefit value v three times in a row leads to a total benefit value of 1.5*v.
Help him to build the menu which maximizes the benefit value under the constraint that his budget is not exceeded.
Input
The input consists of several test cases. Each test case begins with 3 integers in a line: The number of days k (1<=k<=21) Alfred wants to plan for, the number of dishes n (1<=n<=50) he can cook and his budget m (0<=m<=100).
The following n lines describe the dishes Alfred can cook. The i-th line contains two integers: the costs c (1<=c<=50) and the benefit value v (1<=v<=10000) of the i-th dish.
The end of the input is signaled by a test case with k = n = m = 0. You don't need to process this test case.
Output
For each output, print the maximum benefit value reachable with 1 digit after the decimal point. Then print k integers with i-th integer being the number of the dish to cook on day i. Dishes are numbered from 1 to n. Print at least one space or new line character after each integer.
If there are several possible menus reaching the maximum benefit value, select the one with minimum costs, if there are several with minimum costs, you can print any of them.
If every menu exceeds the budget, print only the benefit value of 0.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Our friend Victor participates as an instructor in an environmental volunteer program. His boss asked Victor to distribute N T-shirts to M volunteers, one T-shirt each volunteer, where N is multiple of six, and N>=M. There are the same number of T-shirts of each one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of the T-shirts suit each volunteer.
You must write a program to decide if Victor can distribute T-shirts in such a way that all volunteers get a T-shirt that suit them. If N != M, there can be some remaining T-shirts.
Input
The first line of the input contains the number of test cases. For each test case, there is a line with two numbers N and M. N is multiple of 6, 1<=N<=36, and indicates the number of T-shirts. Number M, 1<=M<=30, indicates the number of volunteers, with N>=M. Subsequently, M lines are listed where each line contains, separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).
Output
For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
For any positive integer N , N = a1
2 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.
Your task is to print the smallest `n ' such that N = a12 + a22 +...+ an2 .
Input
The first line of the input will contain an integer `t ' which indicates the number of test cases to follow.
Each test case will contain a single integer `N ' (1
N10000) on a line by itself.
Output
Print an integer which represents the smallest `n ' such that
N = a12 + a22 +...+ an2 .
Explanation for sample test cases:
5 - > number of test cases
1 = 12 (1 term)
2 = 12 + 12 (2 terms)
3 = 12 + 12 + 12 (3 terms)
1 = 22 (1 term)
2 = 52 + 52 (2 terms)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the late XIXth century the German mathematician George Cantor argued that the set of positive fractions Q+ is equipotent to the set of positive integers N, meaning that they are both infinite, but of the same class. To justify this, he exhibited a mapping from N to Q+ that is onto. This mapping is just traversal of the N x N plane that covers all the pairs:
The first fractions in the Cantor mapping are:
Write a program that finds the i-th Cantor fraction following the mapping outlined above.
Input
The inputs consists of several lines with a positive integer number i each one.
Output
The output consists of a line per input case, that contains the i-th fraction, with numerator and denominator separed by a slash (/). The fraction should not be in the most simple form.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A transport company often needs to deliver goods from one city to another city. The transport company has made a special deal with a hotel chain which allows its drivers to stay in the hotels of this chain for free. Drivers are only allowed to drive up to 10 hours a day. The transport company wants to find a route from the starting city to the destination city such that a driver can always spend the night in one of the hotels of the hotel chain, and that he needs to drive at most 10 hours from one hotel to the next hotel (or the destination). Of course, the number of days needed to deliver the goods should also be minimized.
Input
The input file contains several test cases. Each test case starts with a line containing an integer n, (2 ≤ n ≤ 10000), the number of cities to be considered when planning the route. For simplicity, cities are numbered from 1 to n, where 1 is the starting city, and n is the destination city. The next line contains an integer h followed by the numbers c1, c2, ..., ch indicating the numbers of the cities where hotels of the hotel chain are located. You may assume that 0 ≤ h ≤ min(n, 100). The third line of each test case contains an integer m (1 ≤ m ≤ 105), the number of roads to be considered for planning the route. The following m lines describe the roads. Each road is described by a line containing 3 integers a, b, t (1 ≤ a, b ≤ n and 1 ≤ t ≤ 600), where a, b are the two cities connected by the road, and t is the time in minutes needed by the driver to drive from one end of the road to the other. Input is terminated by n = 0.
Output
For each test case, print one line containing the minimum number of hotels the transport company has to book for a delivery from city 1 to city n. If it is impossible to find a route such that the driver has to drive at most 10 hours per day, print -1 instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Plants versus Zombies HD Super Pro is a game played not on a grid, but on a connected graph G with no cycles (i.e., a tree). Zombies live on edges of the tree and chew through edges so that tree falls apart! Plants can be purchased and placed on vertices of the tree to protect the tree from falling apart. It is not possible to plant more than one plant on the same vertex. A plant protects one or more adjacent edges, depending on the strength and capabilities of the plant.
The Almanac offers you to buy any of three different types of plants:
- PEASHOOTERS: These are your first line of defense and can shoot peas along any one edge (of your choosing) adjacent to the vertex upon which it is placed. Cost: $100 per plant.
- SPLIT PEAS: These are hard working pea shooters and can shoot peas along any two edges (of your choosing) adjacent to the vertex upon which it is placed. Cost: $175 per plant.
- STARFRUIT: Having just visited the dentist, a STARFRUIT is very upset and shoots stars along all edges adjacent to the vertex upon which it is placed. Cost: $500 per plant.
Your goal is to protect the tree from the Zombies by having every edge covered by at least one plant, and doing so spending the least amount of money. You can buy more than one of each type of plant, but you can only plant at most one plant on each vertex.
Input
The input starts with an integer T - the number of test cases (T ≤ 100). T cases follow, each starting with the integer N on the first line, the number of vertices in G (2 ≤ N ≤ 10,000). N − 1 line follows, each containing two space separated integers u and v (0 ≤ u, v ≤ N − 1, u ≠ v) - describing an edge.
Output
For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
長短腳叔叔在爬樓的時候為了避免跌倒，他的左腳只爬奇數個階梯(1, 3, 5, ...)，右腳只爬偶數個階梯(2, 4, 6, ...)，最多可以一次爬2K個階梯
當然身為一個正常的大叔，走路不會故意連續走兩個左腳或連續走兩個右腳，一定是一左一右交替著走，
在一個不知名的山上寺廟前有N階樓梯，請問他有幾種走法可以爬到山上？
舉例來說，假如N=5, K = 2
長短腳叔叔可以{左腳1階, 右腳4階}, {左腳3階, 右腳2階}, {右腳2階, 左腳3階}, {右腳2階, 左腳1階, 右腳2階}, {右腳4階, 左腳1階}
一共有5種走法
Input
輸入第一行包含一個整數T (T < 100) 表示接下來有幾筆測資。
接下來的每組測資都有兩個數字：
N (1 <= N <= 1000)表示有幾階樓梯,
K (1 <= K <= 50)表示他左腳可以走{1, 3, 5, ..., 2K-1}階樓梯，右腳可以走{2, 4, 6, ... 2K}階樓梯
Output
每組輸出一行輸出有幾種走法可以爬到山上，因為走法可能太多，
假設一共有X種走法，請輸出X%12345678來表示所有走法
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.
Input
The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as
P Q
where P is the number of prison cells and Q is the number of prisoners to be released.
This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.
1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.
1 ≤ P ≤ 10000
1 ≤ Q ≤ 100
Output
For each test case, output one line in the format
Case #X: C
where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:
The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions 
. A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn't be stacked.
Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.
Input
The input file will contain one or more test cases. The first line of each test case contains an integer n, representing the number of different blocks in the following data set. The maximum value for n is 30. Each of the next n lines contains three integers representing the values 
, 
and 
.
Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format "Case case: maximum height = height"
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an undirected weighted graph G , you should find one of spanning trees specified as follows.
The graph G is an ordered pair (V, E) , where V is a set of vertices {v1, v2,..., vn} and E is a set of undirected edges {e1, e2,..., em} . Each edge e 
E has its weight w(e) .
A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with n - 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the n - 1 edges of T .
For example, a graph G in Figure 5(a) has four vertices {v1, v2, v3, v4} and five undirected edges {e1, e2, e3, e4, e5} . The weights of the edges are w(e1) = 3 , w(e2) = 5 , w(e3) = 6 , w(e4) = 6 , w(e5) = 7 as shown in Figure 5(b).
There are several spanning trees for G . Four of them are depicted in Figure 6(a)∼(d). The spanning tree Ta in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree Ta is 4. The slimnesses of spanning trees Tb , Tc and Td shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree Td in Figure 6(d) is one of the slimmest spanning trees whose slimness is 1.
Your job is to write a program that computes the smallest slimness.
Input
The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.
n m
a1 b1 w1
am bm wm
Every input item in a dataset is a non-negative integer. Items in a line are separated by a space.
n is the number of the vertices and m the number of the edges. You can assume 2
n100 and 0mn(n - 1)/2 . ak and bk (k = 1,..., m) are positive integers less than or equal to n , which represent the two vertices vak and vbk connected by the k -th edge ek . wk is a positive integer less than or equal to 10000, which indicates the weight of ek . You can assume that the graph G = (V, E) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).
Output
For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, `-1' should be printed. An output should not contain extra characters.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
在科學實驗的過程中，量測溫度與溫差是很常見的工作，不過因為有華氏(度F)與攝氏(度C)兩種常見的溫度表示法，所以有時候會有點麻煩。兩者的轉換公式如下：
本題會給定以攝氏表示的初始溫度C，與以華氏表示的溫差F，請你以攝氏溫度表示新的溫度為何。
Input
輸入第一列有一個整數 T (<= 100)表示測式資料的組數。每組資料有兩個整數 C 與 d ( 0 <= C, d <= 100)，C表示初始溫度(以攝氏溫度表示)，d表示溫差(以華氏溫度表示)。
Output
請以攝氏溫度為單位輸出新的溫度為何，請輸出到小數點後兩位。
Sample Input Download
Sample Output Download
Tags
Discuss
Description
你認為email的PGP加密法不夠安全，所以你決定在你的信件以PGP加密前先把明文轉為Pig Latin以加強安全性。
Input
你必須寫支可以讀入任意行的文字並以Pig Latin的文法輸出的程式。文字的每一行包含一或更多個單字。一個單字的定義是一系列連續的``字母"（大寫 或/和 小寫）。單字必須以下列規則轉換為Pig Latin（沒有任何單字會以它們在input中的樣子輸出）：
1.以母音（大小寫的a,e,i,o,u）為首的單字必須在它們後面加上字串``ay"（不含引號）。例如：``apple"變成``appleay"。
2.以子音（除了大小寫的a,e,i,o,u外的所有字母）為首的單字必須先把第一個字母移到最後面，然後在單字後頭也加上字串``ay"。例如：``hello"變成``ellohay"。
3.不可以改變字母的大小寫。
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A taxi driver, Nakamura, was so delighted because he got a passenger who wanted to go to a city thousands of kilometers away. However, he had a problem. As you may know, most taxis in Japan run on liquefied petroleum gas (LPG) because it is cheaper than gasoline. There are more than 50,000 gas stations in the country, but less than one percent of them sell LPG. Although the LPG tank of his car was full, the tank capacity is limited and his car runs 10 kilometer per liter, so he may not be able to get to the destination without filling the tank on the way. He knew all the locations of LPG stations.
Your task is to write a program that finds the best way from the current location to the destination without running out of gas.
Input
The input consists of several datasets, and each dataset is in the following format.
N M cap
src dest
c1,1 c1,2 d1
c2,1 c2,2 d2
...
cN,1 cN,2 dN
s1
s2
...
sM
The first line of a dataset contains three integers (N,M,cap), where N is the number of roads (1 <= N <= 3000), M is the number of LPG stations (1 <= M <= 300), and cap is the tank capacity (1 <= cap <= 200) in liter. The next line contains the name of the current city (src) and the name of the destination city (dest). The destination city is always different from the current city.
The following N lines describe roads that connect cities. The road i (1 <= i <= N) connects two different cities ci;1 and ci;2 with an integer distance di (0 < di <= 2000) in kilometer, and he can go from either city to the other. You can assume that no two different roads connect the same pair of cities. The columns are separated by a single space. The next M lines (s1, s2, ... sM) indicate the names of the cities with LPG station. You can assume that a city with LPG station has at least one road.
The name of a city has no more than 15 characters. Only English alphabet (`A' to `Z' and `a' to `z', case sensitive) is allowed for the name.
A line with three zeros terminates the input.
Output
For each dataset, output a line containing the length (in kilometer) of the shortest possible journey from the current city to the destination city. If Nakamura cannot reach the destination, output -1" (without quotation marks). You must not output any other characters.
The actual tank capacity is usually a little bit larger than that on the specification sheet, so you can assume that he can reach a city even when the remaining amount of the gas becomes exactly zero. In addition, you can always fill the tank at the destination so you do not have to worry about the return trip.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
你的一個朋友正在做一個關於西洋棋中騎士旅行問題（Traveling Knight Problem）的研究，他希望你幫他解決一個問題：就是給你2個格子的位置X及Y，請你找出騎士從X走到Y最少需要走幾步。
Input
每筆測試資料一列。每列有2個西洋棋的座標位置。每個位置座標是由一個英文字母（a-h，代表棋盤的第幾欄）及一個數字（1-8，代表棋盤的第幾列）組成。
Output
對每一列輸入，請輸出 "To get from xx to yy takes n knight moves.".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Johnny drives a steam roller, which like all steam rollers is slow and takes a relatively long time to start moving, change direction, and brake to a full stop. Johnny has just finished his day's work and is driving his steam roller home to see his wife. Your task is to find the fastest path for him and his steam roller.
The city where Johnny lives has a regular structure (the streets form an orthogonal system). The city streets are laid out on a rectangular grid of intersections. Each intersection is connected to its neighbors (up to four of them) by a street. Each street is exactly one block long. When Johnny enters a street, he must always travel to the other end (continue to the next intersection). From that point, he can continue in any of the four possible directions to another intersection, and so on.
By studying the road conditions of the streets, Johnny has calculated the time needed to go from one end to the other of every street in town. The time is the same for both directions. However, Johnny's calculations hold only under the ideal condition that the steam roller is already in motion when it enters a street and does not need to accelerate or brake. Whenever the steam roller changes direction at a intersection directly before or after a street, the estimated ideal time for that street must be doubled. The same holds if the roller begins moving from a full stop (for example at the beginning of Johnny's trip) or comes to a full stop (for example at the end of his trip).
The following picture shows an example. The numbers show the ``ideal" times needed to drive through the corresponding streets. Streets with missing numbers are unusable for steam rollers. Johnny wants to go from the top-left corner to the bottom-right one.
The path consisting of streets labeled with 9's seems to be faster at the first sight. However, due to the braking and accelerating restrictions, it takes double the estimated time for every street on the path, making the total time 108. The path along the streets labeled with 10's is faster because Johnny can drive two of the streets at the full speed, giving a total time of 100.
Input
The input consists of several test cases. Each test case starts with six positive integer numbers: R , C , r1 , c1 , r2 , and c2 . R and C describe the size of the city, r1 , c1 are the starting coordinates, and r2 , c2 are the coordinates of Johnny's home. The starting coordinates are different from the coordinates of Johnny's home. The numbers satisfy the following condition: 1<=r1, r2<=R<=100 , 1<=c1, c2<=C<=100 .
After the six numbers, there are C - 1 non-negative integers describing the time needed to drive on streets between intersections (1,1) and (1,2), (1,2) and (1,3), (1,3) and (1,4), and so on. Then there are C non-negative integers describing the time need to drive on streets between intersections (1,1) and (2,1), (1,2) and (2,2), and so on. After that, another C - 1 non-negative integers describe the next row of streets across the width of the city. The input continues in this way to describe all streets in the city. Each integer specifies the time needed to drive through the corresponding street (not higher than 10000), provided the steam roller proceeds straight through without starting, stopping, or turning at either end of the street. If any combination of one or more of these events occurs, the time is multiplied by two. Any of these integers may be zero, in which case the corresponding street cannot be used at all
The last test case is followed by six zeroes.
All numbers are separated with at least one whitespace character (space, tab, or newline), but any amount of additional whitespace (including empty lines) may be present to improve readability.
Output
For each test case, print the case number (beginning with 1) followed by the minimal time needed to go from intersection r1, c1 to r2, c2 . If the trip cannot be accomplished (due to unusable streets), print the word `Impossible' instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Once upon a time, in a giant piece of cheese, there lived a cheese mite named Amelia Cheese Mite. Amelia should have been truly happy because she was surrounded by more delicious cheese than she could ever eat. Nevertheless, she felt that something was missing from her life.
One morning, her dreams about cheese were interrupted by a noise she had never heard before. But she immediately realized what it was — the sound of a male cheese mite, gnawing in the same piece of cheese! (Determining the gender of a cheese mite just by the sound of its gnawing is by no means easy, but all cheese mites can do it. That’s because their parents could.)
Nothing could stop Amelia now. She had to meet that other mite as soon as possible. Therefore she had to find the fastest way to get to the other mite. Amelia can gnaw through one millimeter of cheese in ten seconds. But it turns out that the direct way to the other mite might not be the fastest one. The cheese that Amelia lives in is full of holes. These holes, which are bubbles of air trapped in the cheese, are spherical for the most part. But occasionally these spherical holes overlap, creating compound holes of all kinds of shapes. Passing through a hole in the cheese takes Amelia essentially zero time, since she can fly from one end to the other instantly. So it might be useful to travel through holes to get to the other mite quickly.
For this problem, you have to write a program that, given the locations of both mites and the holes in the cheese, determines the minimal time it takes Amelia to reach the other mite. For the purposes of this problem, you can assume that the cheese is infinitely large. This is because the cheese is so large that it never pays for Amelia to leave the cheese to reach the other mite (especially since cheese-mite eaters might eat her). You can also assume that the other mite is eagerly anticipating Amelia’s arrival and will not move while Amelia is underway.
Input
The input file contains descriptions of several cheese mite test cases. Each test case starts with a line containing a single integer n (0 <=n<=100), the number of holes in the cheese. This is followed by n lines containing four integers xi, yi, zi, ri each. These describe the centers (xi, yi, zi) and radii ri (ri > 0) of the holes. All values here (and in the following) are given in millimeters.
The description concludes with two lines containing three integers each. The first line contains the values xA, yA, zA, giving Amelia’s position in the cheese, the second line containing xO, yO, zO, gives the position of the other mite.
The input file is terminated by a line containing the number –1.
Output
For each test case, print one line of output, following the format of the sample output. First print the number of the test case (starting with 1). Then print the minimum time in seconds it takes Amelia to reach the other mite, rounded to the closest integer. The input will be such that the rounding is unambiguous.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Wolfgang Puck has two very peculiar habits:
I. He only makes two shapes of cakes. One is square and has an area of one unit. The other is L-shaped and has an area of three units.
II. He will only deliver cakes packed in very specific box sizes. The boxes are always 2 units wide and are of varying length.
One day Wolfgang wondered in how many different ways he can pack his cakes into certain sized boxes. Can you help him?
.png)
The precise sizes of the cakes Wolfgang makes and one way to pack them in a box of length 6.
The five ways to pack a box of length 2.
Input
The input begins with t, the number of different box lengths. The following t lines contain an integer n (1 <= n <= 40).
Output
For each n output on a separate line the number of different ways to pack a 2-by-n box with cakes described above. Output is guaranteed to be less than 1018.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The gopher family, having averted the canine threat, must face a new predator.
There are n gophers and m gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity v. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.
The input contains several cases. The first line of each case contains four positive integers less than 100: n, m, s, and v. The next n lines give the coordinates of the gophers; the following m lines give the coordinates of the gopher holes. All distances are in meters; all times are in seconds; all velocities are in meters per second.
Output consists of a single line for each case, giving the number of vulnerable gophers.
Input
Output
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
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
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
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
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
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
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
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
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
http://uva.onlinejudge.org/external/126/12639.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2682
uva 這題壞了先不要寫OAO
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=475
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
https://www.dropbox.com/s/zlp5aoq7e06bipm/mid1.pdf
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3468
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3264
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3320
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://poj.org/problem?id=3061
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2588
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=183
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
'We fought far under the living earth, where time is not counted. Ever he clutched me, and
ever I hewed him, till at last he
ed into dark tunnels. Ever up now we went, until we
came to the Endless Stair. Out he sprang, and even as I came behind, he burst into new
flame. Those that looked up from afar thought that the mountain was crowned with storm.
Thunder they heard, and lightning, they said, smote upon Celebdil, and leaped back broken
into tongues of re.'
- Gandalf, describing his ght against the Balrog.
Although Gandalf would not go into the details of his battle, they can be summarized into the
following simpli ed form: both Gandalf and the Balrog have a set of N attacks they can use (spells,
swords, brute-force strength etc.). These attacks are numbered from 1 to N in increasing order of
Power. When each has chosen an attack, in general, the one with the higher power wins. However,
there are a few (M) anomalous pairs of attacks, in which the lesser-powered attack wins.
Initially, Gandalf picks an attack. Then the Balrog counters it with one of the remaining attacks.
If the Balrog's counter does not defeat Gandalf's, then we say Gandalf receives a score of 2. If however
it does, then Gandalf has exactly one more opportunity to pick an attack that will defeat the Balrog's.
If he manages to defeat him now, his score will be 1, whereas if he is still unable to defeat him, his
score will be 0.
Your task is to determine, given N and the M anomalous pairs of attacks, what will be Gandalf's
score, given that both play optimally. Further, in case Gandalf gets a score of 2, you must also determine
which attack he could have chosen as his rst choice.
Note 1: The Balrog can choose only one attack, whereas Gandalf can choose upto two.
Note 2: The relation A defeats B is not transitive within the attacks. For example, attack A can
defeat attack B, attack B can defeat attack C, and attack C can defeat attack A.
Note 3: Between any two attacks A and B, either attack A defeats attack B or attack B defeats
attack A
Input
The rst line will consist of the integer T, the number of test-cases.
Each test case begins with a single line containing two integers N and M. This is followed by M
lines consisting of 2 integers each x and y, denoting that x and y are an anomalous pair.
Output
For each test-case, output a single line either
2 A, if Gandalf can defeat any attack the Balrog chooses if he picks attack A,
1, if Gandalf can choose an attack such that even if the Balrog chooses an attack to defeat him, he can
choose an attack to defeat the Balrog's chosen card,
0, if none of the above two options are possible for all possible choices of Gandalf's attack(s). Between
successive test cases, there should not be any blank lines in the output.
Constraints:
1<=T<=15
3<=N<=1, 000, 000
0<=M<=min(N(N - 1)/2, 300, 000)
1<=x < y<=N for all the anomalous pairs (x, y)
The sum of M over all test-cases will not exceed 300,000.
Notes/Explanation of Sample Input:
In the first case, attack 3 can beat both attacks 1 and 2. So Gandalf just chooses attack 3.
In the second case, attack 1 beats 3 which beats 2 which beats 1. No matter which attack Gandalf chooses, the Balrog can pick the one which defeats his, but then he can pick the remaining attack and defeat the Balrog's.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Lately, there is one serious problem with Panda Land Safe Box: several safes have been robbed! The safes are using old 4-digits rolling lock combination (you only have to roll the digit, either up or down, until all four of them match the key). Each digit is designed to roll from 0 to 9. Rolling-up at 9 will make the digit become 0, and rolling-down at 0 will make the digit become 9. Since there are only 10000 possible keys, 0000 through 9999, anyone can try all the combinations until the safe is unlocked.
.jpg)
What's done is done. But in order to slow down future robbers' attack, Panda Security Agency (PSA) has devised a new safer lock with multiple keys. Instead of using only one key combination as the key, the lock now can have up to N
- Initially the digits are at 0000.
- Keys can be unlocked in any order, by setting the digits in the lock to match the desired key and then pressing the UNLOCK button.
- A magic JUMP button can turn the digits into any of the unlocked keys without doing any rolling.
- The safe will be unlocked if and only if all the keys are unlocked in a minimum total amount of rolling, excluding JUMP (yes, this feature is the coolest one).
- If the number of rolling is exceeded, then the digits will be reset to 0000 and all the keys will be locked again. In other word, the state of the lock will be reset the cracking is failed.
PSA is quite confident that this new system will slow down the cracking, giving them enough time to identify and catch the robbers. In order to determine the minimum number of rolling needed, PSA wants you to write a program. Given all the keys, calculate the minimum number of rolls needed to unlock the safe.
Input
The first line of input contains an integer T , the number of test cases follow. Each case begins with an integer N(1<=N<=500) , the number of keys. The next N lines, each contains exactly four digits number (leading zero allowed) representing the keys to be unlocked.
Output
For each case, print in a single line the minimum number of rolls needed to unlock all the keys.
Explanation for the 2nd case:
- Turn 0000 into 1111, rolls: 4
- Turn 1111 into 1155, rolls: 8
- Jump 1155 into 1111, we can do this because 1111 has been unlocked before.
- Turn 1111 into 5511 rolls: 8
Total rolls = 4 + 8 + 8 = 20
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Gamebox is developing a new augmented reality game for young kids. Players interact with the virtual object on screen through movements of markers. A marker is a square playing card with special marking. Markers all have different markings. The game is played by showing a marker to the game console. The game console has a hidden video camera that can automatically locate and take a snapshot of the marker being played. Depending on how the card is being held and the distance from the game console, the captured image of the marker maybe displaced from the upright position. Furthermore, noise may be introduced during the imaging process. The marker is then recognized and the game is played accordingly. Obviously, if the marker were incorrectly recognized, then the game would not be played correctly. You are hired as a game programmer to make sure that the markers are recognized correctly.
Constraints:
- All the images are binary images (containing only two colors: black and white). 0 denotes black pixel and 1 denotes white pixel.
- There are 5 markers. Each has been digitized into a 100 x 100 image. The images are shown and described below in graphical form.
- The captured image (test images) can be
- Rotated: in 0, 90, 180, or 270 degree angle.
- Enlarged/shrunk: image size can be of size 50 x 50, 100 x 100, 150 x 150, or 200 x 200.
- Contains random noise: at most 3% of the pixels in the input image are reverted. Black becomes white or vise versa.
- Any combination of the above conditions.
Input
The input file contains a set of test images. Each test image is defined by a single integer n on one line to indicate the image size ( n x n). This number is either 0, 50, 100, 150, or 200. 0 indicates the end of the test data. This is followed by n rows of n consecutive 0s and 1s, which defines the captured image to be processed.
Output
For each input case, output a single integer on one line indicating the marker that matches with the given input image.
Figure 3: Markers 1, 2, 3, 4, and 5 from left to right.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We would like to place n rooks, 1 ≤ n ≤ 5000, on a n×n board subject to the following restrictions
- The i-th rook can only be placed within the rectangle given by its left-upper corner (xli, yli) and its right-lower corner (xri, yri), where 1 ≤ i ≤ n, 1 ≤ xli ≤ xri ≤ n, 1 ≤ yli ≤ yri ≤ n.
- No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.
The input consists of several test cases. The first line of each of them contains one integer number, n, the side of the board. n lines follow giving the rectangles where the rooks can be placed as described above. The i-th line among them gives xli, yli, xri, and yri. The input file is terminated with the integer `0' on a line by itself.
Your task is to find such a placing of rooks that the above conditions are satisfied and then output n lines each giving the position of a rook in order in which their rectangles appeared in the input. If there are multiple solutions, any one will do. Output IMPOSSIBLE if there is no such placing of the rooks.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Back to year 3024, humans finally developed a new technology that enables them to conquer the alien races. The new technology made it possible to produce huge spaceships known as Saber Tooth spaceships as powerful as the aliens' defending mammoths. At that time, humans ruled several planets while some others were under control of the aliens. Using Saber Tooth ships, humans finally defeated aliens and this became the first Planet War in history. Our goal is to run a simulation of the ancient war to verify some historical hypotheses.
Producing each spaceship takes an amount of time which is constant for each planet but may vary among different planets. We call the number of spaceships each planet can produce in a year, the production rate of that planet. Note that each planet has a number of spaceships in it initially (before the simulation starts). The planets start producing ships when the simulation starts, so if a planet has n ships initially, and has the production rate p , it will have n + p ships at the beginning of year 1, and n + i×p ships at the beginning of year i (years are started from zero).
Bradley Bennett, the commander in chief of the human armies, decided a strategy for the war. For each alien planet A, he chooses a corresponding human planet P, and produces spaceships in P until a certain moment at which he sends all spaceships in P to invade the planet A. No alien planet is invaded by two human planets and no human planet sends its spaceships to two different alien planets.
The defense power of the alien planets comes from their powerful mammoths. Each alien planet contains a number of mammoths initially and produces a number of mammoths each year (called the production rate of the planet). When a fight between spaceships and mammoths takes place, the side having the greater number of troops is the winner. If the spaceships win, the alien planet is defeated. In case the number of mammoths and spaceships are equal, the spaceships win.
The difficulty with planning this strategy is that it takes some time for the spaceships to reach the alien planets, and during this time, the aliens produce mammoths. The time required for spaceships to travel from each human planet to each alien planet is known. The ships can leave their planets only at the beginning of years (right after the ships are produced) and reach the alien planets at the beginning of years too (right after the mammoths are produced).
As an example, consider a human planet with two initial spaceships and production rate three invading an alien planet with two initial mammoths and production rate two. The time required to travel between the two planets is two years and the ships are ordered to leave at year one. In this case, five ships leave the human planet. When they reach the alien planet, they confront eight mammoths and will be defeated during the fight.
Bennett decided to prepare a plan that destroys every alien planet in the shortest possible time. Your task is to write a program to generate such a plan. The output is the shortest possible time (in years) in which every alien planet is defeated.
Input
There are multiple test cases in the input. The first line of each test case contains two numbers H and A which are the number of planets under the control of humans and aliens respectively (both between 1 and 250). The second line of the test case contains H pairs of non-negative integers n1 m1 n2 m2...nH mH . The number ni is the initial number of Saber Tooth spaceships in the i -th human planet and mi is the production rate of that planet. The third line contains A pairs of non-negative integers which specify the initial number of mammoths and the production rate of the alien planets in the same format as the second line. After the third line, there are H lines each containing A positive integers. The j -th number on the i -th line shows how many years it takes a spaceship to travel from the i -th human planet to the j -th alien planet. The last line of the input contains two zero numbers. Every number in the input except H and A is between 0 and 40000.
Output
The output for each test case contains a single integer which is the minimum time in which all alien planets can be defeated. If it is impossible to destroy all alien planets, the output should be `IMPOSSIBLE'.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a string, output all different possible set of K characters in the string. And sort them in the dictionary order. For example, if K=2 and the given string is ‘CDBABBD’, output
AB
AC
AD
BB
BC
BD
CD
DD
Input
The first line of input contains a positive integer t (t <= 30), which indicates the number of test cases. For each case, there are one strings and a positive integer K in a line. The length of the string is less than 100 and strings contain only 'A'-'K'; The number K, less than or equal to 10, indicates the length of substrings.
Output
For each test case, output all different possible set of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a 2D point, answer if the point is inside a simple 2D polygon of N vertices?
Note that points lie on the vertices or edges of polygon are not considered inside.
Input
The first line is an integer t which indicates the number of test cases.
For each case, the first line is an integer N that denotes the number of vertices of a polygon followed by a list of n pairs of vertices' 2D coordinates (x, y) in counter-clockwise order. All vertices on the polygon are in the rectangle [-20000, 20000]x[-20000,20000].
The next line is an integer q(1 <= q <= 100) indicates the number of test point followed by a list of q pairs of points' 2D coordinates. The bound of x and y coordinate of query points is between -106 and 106.
Size of each data:
Data set 1: N <= 100
Data set 2: N <= 100
Data set 3: N <= 10000
Data set 4: N <= 10000
Output
The output is a line with 'Yes' if the test point is inside the polygon, otherwise output a line with 'No'(without quote).