Description
Jobz is a special kid. He likes painting. One day, he paints a lot of segments in 1-D line with many color pens. In every round, he will choose one color c and one integer interval [xi, yi]. Then he draws the interval with the color. Now, we know what he did in every round. And we want to know the final result what 1-D line looks like. Please write a program to solve the problem.
Input
The input contains multiple test cases. The first line contains one integer n. In the next n lines, every line contains three integers ci, xi and yi. It represents he draw the interval [xi, yi] with the color ci in the i-th round.
n ≤ 100000
0 ≤ xi < yi ≤ 200000
ci is a 32-bit signed integer.
Output
Output every maximum-length intervals with the same color.
Sort them by the increasing order of the xi value.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Citizens of the ice kingdom plan to build an ice arena, which is a rectangular area of N x M ice grids. However, they find that the original heights of the ice cubes on the grids are not equal, and given the time constraints it is difficult for them to modify the original height too much. Thus, only one of the three possible actions can be taken on the ice cube for each grid: digging it (decreasing its height by 1), filling it (increasing its height by 1), or doing nothing.
After taking one and only one action for each grid, the citizens choose grids with the same modified height for ice skating to prevent getting hurt on an uneven surface, and place barriers on the grids that are not chosen.
To form a safe area for ice skating , the citizens hope to use the chosen grids that are connected through vertical or horizontal walks. Please find the maximum possible safe area, that is, the maximum number of chosen grids that are connected.
Input
The first line of input data contains an integer T(1 <= T <= 1000) specifying the number of the cases.
The first line of each test case contains two integers N and M (1<=N, M<=100) indicating the dimensions of the ice arena. Each of the next N lines contains M integers H (1<=H<=10000) denoting the original height of each gird.
Output
For each test case, display a single line containing the maximum number of chosen grids (after taking the actions) that are connected.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Walking around the campus has become a part of our life. We attend class in CS building, have a meal in restaurant, and go back to sleep in your dorm.
Peter thinks that it takes too much time to move between two places. He always wants to reach a place as fast as possible. So he often cuts the corner between two places by passing lawn. However, it is harmful to walk on lawn. Since he doesn’t want to do more harm on lawn, Peter makes a trade-off. He hopes to reach destination without using more than a certain time, so he might not need to pass every short-cut. As a friend of Peter, you want to compute the minimum number of short-cut he has to take to encourage him.
Input
There are no more than 50 test cases. The first line of each test case contains an integer n, indicating the number of places. (1 ≤ n ≤ 100) The parts are numbered from 1 to n. The second line contains an integer M, indicating the number of roads. Then M lines in the form "a b c", which mean there is a road between the ath place and the bth place and takes c minutes to walk along it. Then an integer S and S lines follow, describing the short-cuts with the same way as the roads. The next contains two integers indicating the places to which the start and the destination. The last line contains one integer T, the time limit to reach the destination. (0 ≤ T ≤ 1,000,000,000)
The roads and the shortcuts are all bidirectional. There is at most one road between any two places. There is at most one shortcut between any two places. The time cost of each road or shortcut do not exceed 1,500,000 but at least 1.
Output
Output the minimum number of short-cuts Peter has to take in one line. If it’s impossible to reach on time, print “Impossible” in a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
People lost their jobs during the great depression. In that time, people didn’t care about anything except power and money. They also used both to control another one. If some one's power and money are both less than yours, then you can control him. We have some data of many people. For every one, please compute how many people he can control.
Input
The first line of the input is an integer Z (Z ≤ 10), which means the number of test cases.
For each test case, one line contains one positive integer N (N ≤ 105).
There are N lines following. For each line, there are two integers Pi, Mi (|Pi|, |Mi| ≤ 106).
Output
For each test case, output the test case number in the first line, and then N lines follows.
Every line contains one integer representing the number of the people the person can control. Output one blank line between every two test cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Giving a binary tree, please find the pre-order traversal of the tree
pre-order
Input
The first line of each case consists of two positive integers n (n<=100) and r denoting the number of nodes and the root of the tree. The next n line consists of three integers denoting the number of the node, left child, and right child (-1 denoting NULL).
Output
Print the pre-order traversal of the tree.
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 several domino systems. 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. Adhere to the format shown in the output sample. If you find several solutions, output only one of them. Output a blank line after each system.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A group of terrorists have taken hostages on the former prison island Alcatraz (now a tourist attraction) outside San Francisco, and is demanding a big ransom from the US government. If they are not paid within 40 hours, they will launch 15 rockets of V.X. poison gas at San Francisco, each rocket capable of killing 70,000 people.
The Pentagon is planning on sending a SEAL team to Alcatraz to destroy the rockets. They intend to penetrate the island through the tunnels under the prison building, but because the prison has been rebuilt so many times, all the maps of the tunnels are useless. The only man who can help them is John Mason, a former inmate who once successfully escaped from Alcatraz through the tunnels.
However, Mason is getting old so he doesn't remember all the details of the tunnels. More precisely, he knows that there is exactly one wall whose location he doesn't remember. Since they're running out of time, they want to make sure that they take a path which will guarantee the shortest possible time to reach the exit of the tunnels no matter where this extra wall is. Since you're the top program writer at the Pentagon, it's your job to write the program to find this shortest path!
For simplicity, we can assume that the tunnels below Alcatraz can be described as a rectangular grid, where each grid square is either wall or open space, and walking is permitted only between adjacent non-wall squares. Two squares are adjacent if they have one side in common. The additional, unknown, wall occupies exactly one square, and the team will not notice this wall until they've reached an adjacent square to it.
Example:
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
If the team walks straight ahead from the entrance (E), they may face a wall at row 4 column 3, in which case they have to turn around and the length of the path will be 17. It's better to walk to the right immediately, as this will ensure a path of length at most 15.
Input
The first line in the input will contain one integer n (n ≤ 10) which is the number of maps to process. Then follows the n map descriptions.
Each map description starts with a blank line, followed by a line with two integers, describing the number of rows and columns in the map, respectively. The map then follows one row on each line. '#' is used for walls, '.' for open space, 'E' is the entrance and 'X' is the exit. The number of rows and columns in the map is at least 3 and at most 40.
You may assume that the map is valid and that there will be exactly one entrance and one exit square. You may also assume that there exist at least two disjoint paths (sharing no squares except the entrance and exit) from the entrance to the exit and that the additional wall will neither be on the entrance nor exit square.
Output
For each map, output a single line containing the length of the shortest path according to the description above.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Mr. G. works as a tourist guide. His current assignment is to take some tourists from one city to another. Some two-way roads connect the cities. For each pair of neighboring cities there is a bus service that runs only between those two cities and uses the road that directly connects them. Each bus service has a limit on the maximum number of passengers it can carry. Mr. G. has a map showing the cities and the roads connecting them. He also has the information regarding each bus service. He understands that it may not always be possible for him to take all the tourists to the destination city in a single trip. For example, consider the following road map of 7 cities. The edges connecting the cities represent the roads and the number written on each edge indicates the passenger limit of the bus service that runs on that road.
Now, if he wants to take 99 tourists from city 1 to city 7, he will require at least 5 trips, since he has to ride the bus with each group, and the route he should take is : 1 - 2 - 4 - 7.
But, Mr. G. finds it difficult to find the best route all by himself so that he may be able to take all the tourists to the destination city in minimum number of trips. So, he seeks your help.
Input
The input will contain one or more test cases. The first line of each test case will contain two integers: N (N<= 100) and R representing respectively the number of cities and the number of road segments. Then R lines will follow each containing three integers: C1, C2 and P. C1 and C2 are the city numbers and P (P> 1) is the limit on the maximum number of passengers to be carried by the bus service between the two cities. City numbers are positive integers ranging from 1 to N. The (R + 1)-th line will contain three integers: S, D and T representing respectively the starting city, the destination city and the number of tourists to be guided.
The input will end with two zeroes for N and R.
Output
For each test case in the input first output the scenario number. Then output the minimum number of trips required for this case on a separate line. Print a blank line after the output of each test case.
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
For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.
Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.
To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.
Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.
Input
* Line 1: Four space-separated integers: N, T, S, and E
* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i
Output
* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The 1999 World Finals Contest included a problem based on a “dice maze.” At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last year’s problem statement. But we are happy to report that Mr. Abbott has offered his expertise to this year’s contest with his original and unpublished “walk-through arrow mazes.”
As are most mazes, a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited. These directions are always left, forward or right, or any combination of these.
Figure 1 illustrates a walk-through arrow maze. The intersections are identified as “(row, column)” pairs, with the upper left being (1,1). The “Entrance” intersection for Figure 1 is (3,1), and the “Goal” intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit (1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from (1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual (unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).
You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course. But if there are several solutions which are equally long, you can chose any of them.
Input
The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9. The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.
All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is N, S, E or W to indicate in what direction of travel the sign would be seen. For example, S indicates that this is the sign that is seen when travelling south. (This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be L, F or R indicating left, forward, and right, respectively.
The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word END on a single line by itself.
Output
For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase “No Solution Possible”. Maze names should start in column 1, and all other lines should start in column 3, i.e., indented two spaces. Solutions should be output as a list of intersections in the format “(R,C)” in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.
The first maze in the following sample input is the maze in Figure 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Like everyone else, FJ is always thinking up ways to increase his revenue. To this end, he has set up a series of tolls that the cows will pay when they traverse the cowpaths throughout the farm.
The cows move from any of the N (1 <= N <= 250) pastures conveniently numbered 1..N to any other pasture over a set of M (1 <= M <= 10,000) bidirectional cowpaths that connect pairs of different pastures A_j and B_j (1 <= A_j <= N; 1 <= B_j <= N). FJ has assigned a toll L_j (1 <= L_j <= 100,000) to the path connecting pastures A_j and B_j.
While there may be multiple cowpaths connecting the same pair of pastures, a cowpath will never connect a pasture to itself. Best of all, a cow can always move from any one pasture to any other pasture by following some sequence of cowpaths.
In an act that can only be described as greedy, FJ has also assigned a toll C_i (1 <= C_i <= 100,000) to every pasture. The cost of moving from one pasture to some different pasture is the sum of the tolls for each of the cowpaths that were traversed plus a *single additional toll* that is the maximum of all the pasture tolls encountered along the way, including the initial and destination pastures.
The patient cows wish to investigate their options. They want you to write a program that accepts K (1 <= K <= 10,000) queries and outputs the minimum cost of trip specified by each query. Query i is a pair of numbers s_i and t_i (1 <= s_i <= N; 1 <= t_i <= N; s_i != t_i) specifying a starting and ending pasture.
Consider this example diagram with five pastures:
The 'edge toll' for the path from pasture 1 to pasture 2 is 3.
Pasture 2's 'node toll' is 5.
To travel from pasture 1 to pasture 4, traverse pastures 1 to 3 to 5 to 4. This incurs an edge toll of 2+1+1=4 and a node toll of 4 (since pasture 5's toll is greatest), for a total cost of 4+4=8.
The best way to travel from pasture 2 to pasture 3 is to traverse pastures 2 to 5 to 3. This incurs an edge toll of 3+1=4 and a node toll of 5, for a total cost of 4+5=9.
Input
* Line 1: Three space separated integers: N, M, and K
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..N+M+1: Line j+N+1 contains three space separated
integers: A_j, B_j, and L_j
* Lines N+M+2..N+M+K+1: Line i+N+M+1 specifies query i using two
space-separated integers: s_i and t_i
Output
* Lines 1..K: Line i contains a single integer which is the lowest
cost of any route from s_i to t_i
Sample Input Download
Sample Output Download
Tags
Discuss
Description
"Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story.
"Prince Remmarguts lives in his kingdom UDF – United Delta of Freedom. One day their neighboring country sent them Princess Uyuw on a diplomatic mission."
"Erenow, the princess sent Remmarguts a letter, informing him that she would come to the hall and hold commercial talks with UDF if and only if the prince go and meet her via the K-th shortest path. (in fact, Uyuw does not want to come at all)"
Being interested in the trade development and such a lovely girl, Prince Remmarguts really became enamored. He needs you - the prime minister's help!
DETAILS: UDF's capital consists of N stations. The hall is numbered S, while the station numbered T denotes prince' current place. M muddy directed sideways connect some of the stations. Remmarguts' path to welcome the princess might include the same station twice or more than twice, even it is the station with number S or T. Different paths with same length will be considered disparate.
Input
The first line contains two integer numbers N and M (1 <= N <= 1000, 0 <= M <= 100000). Stations are numbered from 1 to N. Each of the following M lines contains three integer numbers A, B and T (1 <= A, B <= N, 1 <= T <= 100). It shows that there is a directed sideway from A-th station to B-th station with time T.
The last line consists of three integer numbers S, T and K (1 <= S, T <= N, 1 <= K <= 1000).
Output
A single line consisting of a single integer number: the length (time required) to welcome Princess Uyuw using the K-th shortest path. If K-th shortest path does not exist, you should output "-1" (without quotes) instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There is a travel agency in Adelton town on Zanzibar Island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route.
In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ... , y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different. The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible, because there is no sightseeing route in the town.
Input
The first line of input contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500).
Output
There is only one line in output. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x_1 to x_k from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There is a group of adventurers who like to travel in the desert. Everyone knows travelling in desert can be very dangerous. That's why they plan their trip carefully every time. There are a lot of factors to consider before they make their final decision.
One of the most important factors is the weather. It is undesirable to travel under extremely high temperature. They always try to avoid going to the hottest place. However, it is unavoidable sometimes as it might be on the only way to the destination. To decide where to go, they will pick a route that the highest temperature is minimized. If more than one route satisfy this criterion, they will choose the shortest one.
There are several oases in the desert where they can take a rest. That means they are travelling from oasis to oasis before reaching the destination. They know the lengths and the temperatures of the paths between oases. You are to write a program and plan the route for them
Input
Input consists of several test cases. Your program must process all of them.
The first line contains two integers N and E (1 ≤ N ≤ 100; 1 ≤ E ≤ 10000) where N represents the number of oasis and E represents the number of paths between them. Next line contains two distinct integers S and T (1 ≤ S, T ≤ N) representing the starting point and the destination respectively. The following E lines are the information the group gathered. Each line contains 2 integers X, Y and 2 real numbers R and D (1 ≤ X, Y ≤ N; 20 ≤ R ≤ 50; 0 < D ≤ 40). It means there is a path between X and Y, with length D km and highest temperature R oC. Each real number has exactly one digit after the decimal point. There might be more than one path between a pair of oases.
Output
Print two lines for each test case. The first line should give the route you find, and the second should contain its length and maximum temperature.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Write a program that changes an infix expression to a postfix expression according to the following specifications.
1. The infix expression to be converted is in the input file in the format of one character per line, with a maximum of 50 lines in the file. For example, (3+2)*5 would be in the form:
(
3
+
2
)
*
5
2. The input starts with an integer on a line by itself indicating the number of test cases. Several infix expressions follows, preceded by a blank line.
3. The program will only be designed to handle the binary operators +, -, *, /.
4. The operands will be one-digit numerals.
5. The operators * and / have the highest priority. The operators + and - have the lowest priority. Operators at the same precedence level associate from left to right. Parentheses act as grouping symbols that over-ride the operator priorities.
6. The output file will have each postfix expression all on one line. Print a blank line between different expressions.
7. Each testcase will be an expression with valid syntax.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediately falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.
Input
The first line of input contains one integer giving the number of cases that follow.
The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.
Output
For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A skyscraper has no more than 100 floors, numbered from 0 to 99. It has n (1<=n<=5) elevators which travel up and down at (possibly) different speeds. For each i in {1, 2,... n}, elevator number i takes Ti (1<=Ti<=100) seconds to travel between any two adjacent floors (going up or down). Elevators do not necessarily stop at every floor. What's worse, not every floor is necessarily accessible by an elevator.
You are on floor 0 and would like to get to floor k as quickly as possible. Assume that you do not need to wait to board the first elevator you step into and (for simplicity) the operation of switching an elevator on some floor always takes exactly a minute. Of course, both elevators have to stop at that floor. You are forbiden from using the staircase. No one else is in the elevator with you, so you don't have to stop if you don't want to. Calculate the minimum number of seconds required to get from floor 0 to floor k (passing floor k while inside an elevator that does not stop there does not count as "getting to floor k").
Input
The input will consist of a number of test cases. Each test case will begin with two numbers, n and k, on a line. The next line will contain the numbers T1, T2,... Tn. Finally, the next n lines will contain sorted lists of integers - the first line will list the floors visited by elevator number 1, the next one will list the floors visited by elevator number 2, etc.
Output
For each test case, output one number on a line by itself - the minimum number of seconds required to get to floor k from floor 0. If it is impossible to do, print "IMPOSSIBLE" instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
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
In order to understand early civilizations, archaeologists often study texts written in ancient languages. One such language, used in Egypt more than 3000 years ago, is based on characters called hieroglyphs. Figure C.1 shows six hieroglyphs and their names. In this problem, you will write a program to recognize these six characters.
Figure C.1: Six hieroglyphs
Input
The input consists of several test cases, each of which describes an image containing one or more hieroglyphs chosen from among those shown in Figure C.1. The image is given in the form of a series of horizontal scan lines consisting of black pixels (represented by 1) and white pixels (represented by 0). In the input data, each scan line is encoded in hexadecimal notation. For example, the sequence of eight pixels 10011100 (one black pixel, followed by two white pixels, and so on) would be represented in hexadecimal notation as 9c. Only digits and lowercase letters a through f are used in the hexadecimal encoding. The first line of each test case contains two integers, H and W. H (0 < H
200) is the number of scan lines in the image. W (0 < W50) is the number of hexadecimal characters in each line. The next H lines contain the hexadecimal characters of the image, working from top to bottom. Input images conform to the following rules:
- The image contains only hieroglyphs shown in Figure C.1.
- Each image contains at least one valid hieroglyph.
- Each black pixel in the image is part of a valid hieroglyph.
- Each hieroglyph consists of a connected set of black pixels and each black pixel has at least one other black pixel on its top, bottom, left, or right side.
- The hieroglyphs do not touch and no hieroglyph is inside another hieroglyph.
- Two black pixels that touch diagonally will always have a common touching black pixel.
- The hieroglyphs may be distorted but each has a shape that is topologically equivalent to one of the symbols in Figure C.1. (Two figures are topologically equivalent if each can be transformed into the other by stretching without tearing.)
The last test case is followed by a line containing two zeros.
Output
For each test case, display its case number followed by a string containing one character for each hieroglyph recognized in the image, using the following code:
Ankh: A
Wedjat: J
Djed: D
Scarab: S
Was: W
Akhet: K
In each output string, print the codes in alphabetic order. Follow the format of the sample output.
The sample input contains descriptions of test cases shown in Figures C.2 and C.3. Due to space constraints not all of the sample input can be shown on this page.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Allied Chute Manufacturers is a company that builds trash chutes. A trash chute is a hollow tube installed in buildings so that trash dropped in at the top will fall down and be collected in the basement. Designing trash chutes is actually highly nontrivial. Depending on what kind of trash people are expected to drop into them, the trash chute needs to have an appropriate size. And since the cost of manufacturing a trash chute is proportional to its size, the company always would like to build a chute that is as small as possible. Choosing the right size can be tough though.
We will consider a 2-dimensional simplification of the chute design problem. A trash chute points straight down and has a constant width. Objects that will be dropped into the trash chute are modeled as polygons. Before an object is dropped into the chute it can be rotated so as to provide an optimal fit. Once dropped, it will travel on a straight path downwards and will not rotate in flight. The following figure shows how an object is first rotated so it fits into the trash chute.
Your task is to compute the smallest chute width that will allow a given polygon to pass through.
Input
The input contains several test cases. Each test case starts with a line containing an integer n (3
n100), the number of points in the polygon that models the trash item.
The next n lines then contain pairs of integers xi and yi (0xi, yi104), giving the coordinates of the polygon vertices in order. All points in one test case are guaranteed to be mutually distinct and the polygon sides will never intersect. (Technically, there is one inevitable exception of two neighboring sides sharing their common vertex. Of course, this is not considered an intersection.)
The last test case is followed by a line containing a single zero.
Output
For each test case, display its case number followed by the width of the smallest trash chute through which it can be dropped. Display the minimum width with exactly two digits to the right of the decimal point, rounding up to the nearest multiple of 1/100. Answers within 1/100 of the correct rounded answer will be accepted.
Follow the format of the sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
New Zealand currency consists of $100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c coins. Write a program that will determine, for any given amount, in how many ways that amount may be made up. Changing the order of listing does not increase the count. Thus 20c may be made up in 4 ways: 1 x 20c, 2 x 10c, 10c+2 x 5c, and 4 x 5c.
Input
Input will consist of a series of real numbers no greater than $300.00 each on a separate line. Each amount will be valid, that is will be a multiple of 5c. The file will be terminated by a line containing zero (0.00).
Output
Output will consist of a line for each of the amounts in the input, each line consisting of the amount of money (with two decimal places and right justified in a field of width 6), followed by the number of ways in which that amount may be made up, right justified in a field of width 17.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After making a purchase at a large department store, Mel's change was 17 cents. He received 1 dime, 1 nickel, and 2 pennies. Later that day, he was shopping at a convenience store. Again his change was 17 cents. This time he received 2 nickels and 7 pennies. He began to wonder ' "How many stores can I shop in and receive 17 cents change in a different configuration of coins? After a suitable mental struggle, he decided the answer was 6. He then challenged you to consider the general problem.
Write a program which will determine the number of different combinations of US coins (penny: 1c, nickel: 5c, dime: 10c, quarter: 25c, half-dollar: 50c) which may be used to produce a given amount of money.
Input
The input will consist of a set of numbers between 0 and 30000 inclusive, one per line in the input file.
Output
The output will consist of the appropriate statement from the selection below on a single line in the output file for each input value. The number m is the number your program computes, n is the input value.
There are m ways to produce n cents change.
There is only 1 way to produce n cents change.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The language PigEwu has a very simple syntax. Each word in this language has exactly 4 letters. Also each word contains exactly two vowels (y is consider a vowel in PigEwu). For instance, "maar" and "even" are legitimate words, "arts" is not a legal word.
In the game boggle, you are given a 4x4 array of letters and asked to find all words contained in it. A word in our case (PigEwu) will thus be a sequence of 4 distinct squares (letters) that form a legal word and such that each square touches (have a corner or edge in common) the next square.
For example:
A S S D S B E Y G F O I H U U K
In this board a (partial) list of legal words include:
ASGU SABO FOIK FOYD SYDE HUFO
BEBO is a legal word but it is not on this boggle board (there are no two B's here).
Write a program that reads a pair of Boggle boards and lists all PigEwu words that are common to both boards.
Input
The input file will include a few data sets. Each data set will be a pair of boards as shown in the sample input. All entries will be upper case letters. Two consecutive entries on same board will be separated by one blank. The first row in the first board will be on the same line as the first row of the second board. They will be separated by four spaces, the same will hold for the remaining 3 rows. Board pairs will be separated by a blank line. The file will be terminated by `#'.
Output
For each pair of boggle boards, output an alphabetically-sorted list of all common words, each word on a separate line; or the statement "There are no common words for this pair of boggle boards."
Separate the output for each pair of boggle boards with a blank line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an amount of money and unlimited (almost) numbers of coins (we will ignore notes for this problem) we know that an amount of money may be made up in a variety of ways. A more interesting problem arises when goods are bought and need to be paid for, with the possibility that change may need to be given. Given the finite resources of most wallets nowadays, we are constrained in the number of ways in which we can make up an amount to pay for our purchases--assuming that we can make up the amount in the first place, but that is another story.
The problem we will be concerned with will be to minimise the number of coins that change hands at such a transaction, given that the shopkeeper has an adequate supply of all coins. (The set of New Zealand coins comprises 5c, 10c, 20c, 50c, $1 and $2.) Thus if we need to pay 55c, and we do not hold a 50c coin, we could pay this as 2*20c + 10c + 5c to make a total of 4 coins. If we tender $1 we will receive 45c in change which also involves 4 coins, but if we tender $1.05 ($1 + 5c), we get 50c change and the total number of coins that changes hands is only 3.
Write a program that will read in the resources available to you and the amount of the purchase and will determine the minimum number of coins that change hands.
Input
Input will consist of a series of lines, each line defining a different situation. Each line will consist of 6 integers representing the numbers of coins available to you in the order given above, followed by a real number representing the value of the transaction, which will always be less than $5.00. The file will be terminated by six zeroes (0 0 0 0 0 0). The total value of the coins will always be sufficient to make up the amount and the amount will always be achievable, that is it will always be a multiple of 5c.
Output
Output will consist of a series of lines, one for each situation defined in the input. Each line will consist of the minimum number of coins that change hands right justified in a field 3 characters wide.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two arrays A and B, we can determine the array C = A B using the standard definition of matrix multiplication:
The number of columns in the A array must be the same as the number of rows in the B array. Notationally, let's say that rows(A) and columns(A) are the number of rows and columns, respectively, in the A array. The number of individual multiplications required to compute the entire C array (which will have the same number of rows as A and the same number of columns as B) is then rows(A) columns(B) columns(A). For example, if A is a 10x20 array, and B is a 20x15 array, it will take 10 x15 , or 3000 multiplications to compute the C array.
To perform multiplication of more than two arrays we have a choice of how to proceed. For example, if X, Y, and Z are arrays, then to compute X Y Z we could either compute (X Y) Z or X (Y Z). Suppose X is a 5x10 array, Y is a 10x20 array, and Z is a 20x35 array. Let's look at the number of multiplications required to compute the product using the two different sequences:
(X Y) Z
- 5x20x10=1000 multiplications to determine the product (X Y), a 5x20 array.
- Then 5x35x20=3500 multiplications to determine the final result.
- Total multiplications: 4500.
X (Y Z)
- 10x35x20=7000 multiplications to determine the product (Y Z), a 10x35 array.
- Then 5x35x10=1750 multiplications to determine the final result.
- Total multiplications: 8750.
Clearly we'll be able to compute (X Y) Z using fewer individual multiplications.
Given the size of each array in a sequence of arrays to be multiplied, you are to determine an optimal computational sequence. Optimality, for this problem, is relative to the number of individual multiplications required.
Input
For each array in the multiple sequences of arrays to be multiplied you will be given only the dimensions of the array. Each sequence will consist of an integer N which indicates the number of arrays to be multiplied, and then N pairs of integers, each pair giving the number of rows and columns in an array; the order in which the dimensions are given is the same as the order in which the arrays are to be multiplied. A value of zero for N indicates the end of the input. N will be no larger than 10.
Output
Assume the arrays are named 
. Your output for each input case is to be a line containing a parenthesized expression clearly indicating the order in which the arrays are to be multiplied. Prefix the output for each case with the case number (they are sequentially numbered, starting with 1). Your output should strongly resemble that shown in the samples shown below. If, by chance, there are multiple correct sequences, any of these will be accepted as a valid answer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It's commonly known that the Dutch have invented copper-wire. Two Dutch men were fighting over a nickel, which was made of copper. They were both so eager to get it and the fighting was so fierce, they stretched the coin to great length and thus created copper-wire.
Not commonly known is that the fighting started, after the two Dutch tried to divide a bag with coins between the two of them. The contents of the bag appeared not to be equally divisible. The Dutch of the past couldn't stand the fact that a division should favour one of them and they always wanted a fair share to the very last cent. Nowadays fighting over a single cent will not be seen anymore, but being capable of making an equal division as fair as possible is something that will remain important forever...
That's what this whole problem is about. Not everyone is capable of seeing instantly what's the most fair division of a bag of coins between two persons. Your help is asked to solve this problem.
Given a bag with a maximum of 100 coins, determine the most fair division between two persons. This means that the difference between the amount each person obtains should be minimised. The value of a coin varies from 1 cent to 500 cents. It's not allowed to split a single coin.
Input
A line with the number of problems n, followed by n times:
a line with a non negative integer m (m<=100) indicating the number of coins in the bag
a line with m numbers separated by one space, each number indicates the value of a coin.
Output
The output consists of n lines. Each line contains the minimal positive difference between the amount the two persons obtain when they divide the coins from the corresponding bag.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Different types of electoral systems exist. In a block voting system the members of a party do not vote individually as they like, but instead they must collectively accept or reject a proposal. Although a party with many votes clearly has more power than a party with few votes, the votes of a small party can nevertheless be crucial when they are needed to obtain a majority. Consider for example the following five-party system:
Coalition {A,B} has 7 + 4 = 11 votes, which is not a majority. When party C joins coalition {A,B}, however, {A,B,C} becomes a winning coalition with 7+4+2 = 13 votes. So even though C is a small party, it can play an important role.
As a measure of a party's power in a block voting system, John F. Banzhaf III proposed to use the power index. The key idea is that a party's power is determined by the number of minority coalitions that it can join and turn into a (winning) majority coalition. Note that the empty coalition is also a minority coalition and that a coalition only forms a majority when it has more than half of the total number of votes. In the example just given, a majority coalition must have at least 13 votes.
In an ideal system, a party's power index is proportional to the number of members of that party.
Your task is to write a program that, given an input as shown above, computes for each party its power index.
Input
The first line contains a single integer which equals the number of test cases that follow. Each of the following lines contains one test case.
The first number on a line contains an integer P in [1 tex2html_wrap_inline36 20] which equals the number of parties for that test case. This integer is followed by P positive integers, separated by spaces. Each of these integers represents the number of members of a party in the electoral system. The i-th number represents party number i. No electoral system has more than 1000 votes.
Output
For each test case, you must generate P lines of output, followed by one empty line. P is the number of parties for the test case in question. The i-th line (i in [ 1...P ]) contains the sentence:
party i has power index I
where I is the power index of party i.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Sequence 1: 
Sequence 2:
Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:
abcdgh aedfhr
is adh of length 3.
Input consists of pairs of lines. The first line of a pair contains the first string and the second line contains the second string. Each string is on a separate line and consists of at most 1,000 characters
For each subsequent pair of input lines, output a line containing one integer number which satisfies the criteria stated above.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are planning to take some rest and to go out on vacation, but you really don't know which cities you should visit. So, you ask your parents for help. Your mother says "My son, you MUST visit Paris, Madrid, Lisboa and London. But it's only fun in this order." Then your father says: "Son, if you're planning to travel, go first to Paris, then to Lisboa, then to London and then, at last, go to Madrid. I know what I'm talking about."
Now you're a bit confused, as you didn't expected this situation. You're afraid that you'll hurt your mother if you follow your father's suggestion. But you're also afraid to hurt your father if you follow you mother's suggestion. But it can get worse, because you can hurt both of them if you simply ignore their suggestions!
Thus, you decide that you'll try to follow their suggestions in the better way that you can. So, you realize that the "Paris-Lisboa-London" order is the one which better satisfies both your mother and your father. Afterwards you can say that you could not visit Madrid, even though you would've liked it very much.
If your father have suggested the "London-Paris-Lisboa-Madrid" order, then you would have two orders, "Paris-Lisboa" and "Paris-Madrid", that would better satisfy both of your parent's suggestions. In this case, you could only visit 2 cities.
You want to avoid problems like this one in the future. And what if their travel suggestions were bigger? Probably you would not find the better way very easy. So, you decided to write a program to help you in this task. You'll represent each city by one character, using uppercase letters, lowercase letters, digits and the space. Thus, you can have at most 63 different cities to visit. But it's possible that you'll visit some city more than once.
If you represent Paris with "a", Madrid with "b", Lisboa with "c" and London with "d", then your mother's suggestion would be "abcd" and you father's suggestion would be "acdb" (or "dacb", in the second example).
The program will read two travel sequences and it must answer how many cities you can travel to such that you'll satisfy both of your parents and it's maximum.
Input
The input will consist on an arbitrary number of city sequence pairs. The end of input occurs when the first sequence starts with an "#"character (without the quotes). Your program should not process this case. Each travel sequence will be on a line alone and will be formed by legal characters (as defined above). All travel sequences will appear in a single line and will have at most 100 cities.
Output
For each sequence pair, you must print the following message in a line alone:
Case #d: you can visit at most K cities.
Where d stands for the test case number (starting from 1) and K is the maximum number of cities you can visit such that you'll satisfy both you father's suggestion and you mother's suggestion.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
``Commander! Commander! Please wake up commander!''
``... mmmph. What time is it?''
``4:07 am, Commander. The following message just arrived on the emergency zeta priority classified scrambler, marked your eyes only.''
You grudgingly take the letter, rub the sleep from your eyes, fleetingly wish that the 'Backer closed at an earlier hour, and start to read.
``Dear StarWars SDI Commander, Bad news, buddy. Crazy Boris had a bit too much vodka last night and when he woke up this morning, instead of the snooze button on his alarm clock, he ... well, let me put it this way: we've got tons of nuclear missles flying this way. Unfortunately, all that we have is a chart of the altitudes at which the missles are flying, arranged by the order of arrivals. Go for it, buddy. Good luck. Secretary of Defense P.S. Hilly and Bill say hi.''
To make things worse, you remeber that SDI has a fatal flaw due to the budget cuts. When SDI sends out missles to intercept the targets, every missle has to fly higher than the previous one. In other words, once you hit a target, the next target can only be among the ones that are flying at higher altitudes than the one you just hit.
For example, if the missles are flying toward you at heights of 1, 6, 2, 3, and 5 (arriving in that order), you can try to intercept the first two, but then you won't be able to get the ones flying at 2, 3, 5 because they are lower than 6. Your job is to hit as many targets as possible. So you have to quickly write a program to find the best sequence of targets that the flawed SDI program is going to destroy.
Russian war tactics are fairly strange; their generals are stickers for mathematical precision. Their missles will always be fired in a sequence such that there will only be one solution to the problem posed above.
Input and Output
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
each input to your program will consist of a sequence of integer altitudes, each on a separate line.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Output from your program should contain the total number of targets you can hit, followed by the altitudes of those targets, one per line, in the order of their arrivals.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
BackGround
Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its ``lower-class'' cousin.
The Problem
Consider an n-dimensional ``box'' given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box 
(length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.
In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes 
such that each box 
nests in box 
( 
.
A box D = ( 
) nests in a box E = ( 
) if there is some rearrangement of the 
such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).
For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.
Formally, we define nesting as follows: box D = ( ) nests in box E = ( ) if there is a permutation 
of 
such that ( 
) ``fits'' in ( ) i.e., if 
for all 
.
Input
The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)
This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The 
line in the sequence ( 
) gives the measurements for the box.
There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).
In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.
Output
For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The ``smallest'' or ``innermost'' box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.
The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).
If there is more than one longest nesting string then any one of them can be output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Background
Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) -- finding whether all the cities in a salesperson's route can be visited exactly once with a specified limit on travel time -- is one of the canonical examples of an NP-complete problem; solutions appear to require an inordinate amount of time to generate, but are simple to check.
This problem deals with finding a minimal path through a grid of points while traveling only from left to right.
The Problem
Given an 
matrix of integers, you are to write a program that computes a path of minimal weight. A path starts anywhere in column 1 (the first column) and consists of a sequence of steps terminating in column n (the last column). A step consists of traveling from column i to column i+1 in an adjacent (horizontal or diagonal) row. The first and last rows (rows 1 and m) of a matrix are considered adjacent, i.e., the matrix ``wraps'' so that it represents a horizontal cylinder. Legal steps are illustrated below.
The weight of a path is the sum of the integers in each of the n cells of the matrix that are visited.
For example, two slightly different 
matrices are shown below (the only difference is the numbers in the bottom row).
The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.
Input
The input consists of a sequence of matrix specifications. Each matrix specification consists of the row and column dimensions in that order on a line followed by 
integers where m is the row dimension and n is the column dimension. The integers appear in the input in row major order, i.e., the first n integers constitute the first row of the matrix, the second n integers constitute the second row and so on. The integers on a line will be separated from other integers by one or more spaces. Note: integers are not restricted to being positive. There will be one or more matrix specifications in an input file. Input is terminated by end-of-file.
For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits.
Output
Two lines should be output for each matrix specification in the input file, the first line represents a minimal-weight path, and the second line is the cost of a minimal path. The path consists of a sequence of n integers (separated by one or more spaces) representing the rows that constitute the minimal path. If there is more than one path of minimal weight the path that is lexicographically smallest should be output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Just like every fall, the organizers of the Southwestern Europe Dice Simulation Contest are busy again this year. In this edition you have to simulate a 3-sided die that outputs each of three possible outcomes (which will be denoted by 1; 2 and 3) with a given probability, using three dice in a given set. The simulation is performed this way: you choose one of the given dice at random, roll it, and report its outcome. You are free to choose the probabilities of rolling each of the given dice, as long as each probability is strictly greater than zero. Before distributing the materials to the contestants, the organizers have to verify that it is actually possible to solve this task.
For example, in the first test case of the sample input you have to simulate a die that yields outcome 1; 2 and 3 with probabilities 3/10 ; 4/10 and 3/10 . We give you three dice, and in this case the i-th of them always yields outcome i, for each i = 1; 2; 3. Then it is possible to simulate the given die in the following fashion: roll the first die with probability 3/10, the second one with probability 4/10 and the last one with probability 3/10.
.png)
Input
The input consists of several test cases, separated by single blank lines. Each test case consists of four lines: the First three of them describe the three dice you are given and the last one describes the die you have to simulate. Each of the four lines contains 3 space-separated integers between 0 and 10 000 inclusive. These numbers will add up to 10 000, and represent 10 000 times the probability that rolling the die described in that line yields outcome 1, 2 and 3, respectively. The test cases will Finish with a line containing only the number zero repeated three times (also preceded with a blank line).
Output
For each case, your program should output a line with the word YES if it is feasible to produce the desired die from the given ones, and NO otherwise.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1x1or greater located within the whole array. As an example, the maximal sub-rectangle of the array:
| 0 | -2 | -7 | 0 |
| 9 | 2 | -6 | 2 |
| -4 | 1 | -4 | 1 |
| -1 | 8 | 0 | -2 |
is in the lower-left-hand corner:
| 9 | 2 |
| -4 | 1 |
| -1 | 8 |
and has the sum of 15.
Input and Output
The input consists of an NxN array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by N2 integers separated by white-space (newlines and spaces). These N2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 500. The numbers in the array will be in the range [-127, 127].
The output is the sum of the maximal sub-rectangle.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A palindrome is a symmetrical string, that is, a string read identically from left to right
as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to
obtain a palindrome.
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
Input
The first line contains one integer: the length of the input string N, 3<=N<=5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.
Output
The first line contains one integer, which is the desired minimal number.
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
Toss is an important part of any event. When everything becomes equal toss is the ultimate decider. Normally a fair coin is used for Toss. A coin has two sides head(H) and tail(T). Superstition may work in case of choosing head or tail. If anyone becomes winner choosing head he always wants to choose head. Nobody believes that his winning chance is 50-50. However in this problem we will deal with a fair coin and n times tossing of such a coin. The result of such a tossing can be represented by a string. Such as if 3 times tossing is used then there are possible 8 outcomes.
HHH HHT HTH HTT THH THT TTH TTT
As the coin is fair we can consider that the probability of each outcome is also equal. For simplicity we can consider that if the same thing is repeated 8 times we can expect to get each possible sequence once.
The Problem
In the above example we see 1 sequence has 3 consecutive H, 3 sequences have 2 consecutive H and 7 sequences have at least single H. You have to generalize it. Suppose a coin is tossed n times. And the same process is repeated 2^n times. How many sequences you will get which contains a consequence of H of length at least k.
Input
The input will start with two positive integer, n and k (1<=k<=n<=100). Input is terminated by EOF.
Output
For each test case show the result in a line as specified in the problem statement.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
Input
The input begins with the number t of test cases in a single line. In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John has discovered the secret to making the sweetest butter in all of Wisconsin: sugar. By placing a sugar cube out in the pastures, he knows the N (1 <= N <= 500) cows will lick it and thus will produce super-sweet butter which can be marketed at better prices. Of course, he spends the extra money on luxuries for the cows.
FJ is a sly farmer. Like Pavlov of old, he knows he can train the cows to go to a certain pasture when they hear a bell. He intends to put the sugar there and then ring the bell in the middle of the afternoon so that the evening's milking produces perfect milk.
FJ knows each cow spends her time in a given pasture (not necessarily alone). Given the pasture location of the cows and a description of the paths the connect the pastures, find the pasture in which to place the sugar cube so that the total distance walked by the cows when FJ rings the bell is minimized. FJ knows the fields are connected well enough that some solution is always possible.
Input
Line 1: Three space-separated integers: N, the number of pastures: P (2 <= P <= 800), and the number of connecting paths: C (1 <= C <= 1,450). Cows are uniquely numbered 1..N. Pastures are uniquely numbered 1..P.
Lines 2..N+1: Each line contains a single integer that is the pasture number in which a cow is grazing. Cow i's pasture is listed on line i+1.
Lines N+2..N+C+1: Each line contains three space-separated integers that describe a single path that connects a pair of pastures and its length. Paths may be traversed in either direction. No pair of pastures is directly connected by more than one path. The first two integers are in the range 1..P; the third integer is in the range (1..225).
Output
Line 1: A single integer that is the minimum distance the cows must walk to a pasture with a sugar cube.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
During the Annual Interstellar Competition for Tuned Spaceships, N spaceships will be competing. Each spaceship i is tuned in such a way that it can accelerate in zero time to its maximum speed Vi and remain cruising at that speed. Due to past achievements, each spaceship starts at a starting position Xi, specifying how many kilometers the spaceship is away from the starting line. The race course is infinitely long. Because of the high speeds of the spaceships, the race course goes straight all the time. On that straight course, spaceships can pass one another very easily, without interfering with each other.
Many people in the audience have not realized yet that the outcome of the race can be determined in advance. It is your task to show this to them, by telling them how many times spaceships will pass one another, and by predicting the first 10 000 times that spaceships pass in chronological order. You may assume that each spaceship starts at a different position. Furthermore, there will never be more than two spaceships at the same position of the course at any time.
Input
The first line of the input specifies the number of spaceships N (0 < N <= 250 000) that are competing. Each of the next N lines describes the properties of one spaceship. The i+1th line describes the ith ship with two integers Xi and Vi, representing the starting position and the velocity of the ith spaceship (0 <= Xi <= 1 000 000, 0 < Vi < 100). The spaceships are ordered according to the starting position, i.e. X1 < X2 < . . . < XN. The starting position is the number of kilometers past the starting line where the spaceship starts, and the velocity is given in kilometers per second.
Output
The first line of the output should contain the number of times that spaceships pass one another during the race modulo 1 000 000. By publishing the number of passes only modulo 1 000 000, you can at the same time prove your knowledge of it and don’t spoil the party for the less intelligent people in the audience. Each of the subsequent lines should represent one passing, in chronological order. If there would be more than 10 000 passings, only output the first 10 000 passings. If there are less than 10 000 passings, output all passings. Each line should consist of two integers i and j, specifying that spaceship i passes spaceship j. If multiple passings occur at the same time, they have to be sorted by their position on the course. This means that passings taking place closer to the starting line must be listed first. The
time of a passing is the time when the two spaceships are at the same position.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Heroin (diacetylmorphine or morphine diacetate (INN)), also known as diamorphine (BAN), is an opiate analgesic synthesized by C.R. Alder Wright in 1874 by adding two acetyl groups to the molecule morphine found in the opium poppy. It is the 3,6-diacetyl ester of morphine, and functions as a morphine prodrug (meaning that it is metabolically converted to morphine inside the body in order for it to work).
When used in medicine it is typically used to treat severe pain, such as that resulting from a heart attack or a severe injury. The name "heroin" is only used when being discussed in its illegal form. When it is used in a medical environment, it is referred to as Diamorphine. The white crystalline form considered "pure heroin" is usually the hydrochloride salt, diacetylmorphine hydrochloride.
Illegally supplied heroin however is more often in freebase form, dulling the sheen and consistency to a matte-white powder. Because of its lower boiling point, the freebase form of heroin is also smokable. It is prevalent in heroin coming from Afghanistan, which as of 2004 produced roughly 87% of the world supply in illicit raw opium. However, production in Mexico has risen six-fold from 2007 to 2011, changing that percentage and placing Mexico as the second largest opium producer in the world.
Mexican cartels are known to produce a third type of illicit heroin, commonly called black tar, which results from a simplified, quicker synthesis procedure and contains a high percentage of morphine derivates other than heroin, such as 6-Monoacetylmorphine (6-MAM).
As with other opioids, diacetylmorphine is used as both an analgesic and a recreational drug. Frequent and regular administration is associated with tolerance and physical dependence, which may develop into addiction. Internationally, diacetylmorphine is controlled under Schedules I and IV of the Single Convention on Narcotic Drugs. It is illegal to manufacture, possess, or sell diacetylmorphine without a license in almost every country.
Under the chemical names diamorphine and diacetylmorphine, heroin is a legally prescribed controlled drug in the United Kingdom, and is supplied in tablet or injectable form for the same indications as morphine is, often being preferred over morphine due to its lower side-effect profile. It is also available for prescription to long-term users as a form of opioid replacement therapy in the Netherlands, United Kingdom, Switzerland, Germany, and Denmark, alongside psycho-social care—in the same manner that methadone or buprenorphine are used in the United States or Canada—and a similar programme is being campaigned for by liberal political parties in Norway.
Usage
Heroin (diacetylmorphine or morphine diacetate (INN)), also known as diamorphine (BAN), is an opiate analgesic synthesized by C.R. Alder Wright in 1874 by adding two acetyl groups to the molecule morphine found in the opium poppy. It is the 3,6-diacetyl ester of morphine, and functions as a morphine prodrug (meaning that it is metabolically converted to morphine inside the body in order for it to work).
When used in medicine it is typically used to treat severe pain, such as that resulting from a heart attack or a severe injury. The name "heroin" is only used when being discussed in its illegal form. When it is used in a medical environment, it is referred to as Diamorphine. The white crystalline form considered "pure heroin" is usually the hydrochloride salt, diacetylmorphine hydrochloride.
Illegally supplied heroin however is more often in freebase form, dulling the sheen and consistency to a matte-white powder. Because of its lower boiling point, the freebase form of heroin is also smokable. It is prevalent in heroin coming from Afghanistan, which as of 2004 produced roughly 87% of the world supply in illicit raw opium. However, production in Mexico has risen six-fold from 2007 to 2011, changing that percentage and placing Mexico as the second largest opium producer in the world.
Mexican cartels are known to produce a third type of illicit heroin, commonly called black tar, which results from a simplified, quicker synthesis procedure and contains a high percentage of morphine derivates other than heroin, such as 6-Monoacetylmorphine (6-MAM).
As with other opioids, diacetylmorphine is used as both an analgesic and a recreational drug. Frequent and regular administration is associated with tolerance and physical dependence, which may develop into addiction. Internationally, diacetylmorphine is controlled under Schedules I and IV of the Single Convention on Narcotic Drugs. It is illegal to manufacture, possess, or sell diacetylmorphine without a license in almost every country.
Under the chemical names diamorphine and diacetylmorphine, heroin is a legally prescribed controlled drug in the United Kingdom, and is supplied in tablet or injectable form for the same indications as morphine is, often being preferred over morphine due to its lower side-effect profile. It is also available for prescription to long-term users as a form of opioid replacement therapy in the Netherlands, United Kingdom, Switzerland, Germany, and Denmark, alongside psycho-social care—in the same manner that methadone or buprenorphine are used in the United States or Canada—and a similar programme is being campaigned for by liberal political parties in Norway.
Medical use
Under the chemical name diamorphine, diacetylmorphine is prescribed as a strong analgesic in the United Kingdom, where it is given via subcutaneous, intramuscular, intrathecal or intravenous route. Its use includes treatment for acute pain, such as in severe physical trauma, myocardial infarction, post-surgical pain, and chronic pain, including end-stage cancer and other terminal illnesses. In other countries it is more common to use morphine or other strong opioids in these situations. In 2004, the National Institute for Health and Clinical Excellence produced guidance on the management of caesarian section, which recommended the use of intrathecal or epidural diacetylmorphine for post-operative pain relief.
In 2005, there was a shortage of diacetylmorphine in the UK, because of a problem at the main UK manufacturers. Because of this, many hospitals changed to using morphine instead of diacetylmorphine. Although there is no longer a problem with the manufacturing of diacetylmorphine in the UK, some hospitals there have continued to use morphine (the majority, however, continue to use diacetylmorphine, and diacetylmorphine tablets are supplied for pain management).
Output the result of A plus B
Input
Output
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
Hardwoods are the botanical group of trees that have broad leaves, produce a fruit or nut, and generally go dormant in the winter.
America's temperate climates produce forests with hundreds of hardwood species -- trees that share certain biological characteristics. Although oak, maple and cherry all are types of hardwood trees, for example, they are different species. Together, all the hardwood species represent 40 percent of the trees in the United States.
On the other hand, softwoods, or conifers, from the Latin word meaning "cone-bearing," have needles. Widely available US softwoods include cedar, fir, hemlock, pine, redwood, spruce and cypress. In a home, the softwoods are used primarily as structural lumber such as 2x4s and 2x6s, with some limited decorative applications.
Using satellite imaging technology, the Department of Natural Resources has compiled an inventory of every tree standing on a particular day. You are to compute the total fraction of the tree population represented by each species.
The first line is the number of test cases, followed by a blank line. Each test case of your program consists of a list of the species of every tree observed by the satellite; one tree per line. No species name exceeds 30 characters. There are no more than 10,000 species and no more than 1,000,000 trees. There is a blank line between each consecutive test case.
For each test case print the name of each species represented in the population, in alphabetical order, followed by the percentage of the population it represents, to 4 decimal places. Print a blank line between 2 consecutive data sets.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:
- Emergency 911
- Alice 97 625 999
- Bob 91 12 54 26
In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.
Input
The first line of input gives a single integer, 1<=t<=40 , the number of test cases. Each test case starts with n , the number of phone numbers, on a separate line, 1<=n<=10000 . Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
Output
For each test case, output ``YES" if the list is consistent, or ``NO" otherwise.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John is stuck with another problem while feeding his cows. All of his N (1 ≤ N ≤ 100,000) cows (numbered 1..N) are lined up in front of the barn, sorted by their rank in their social hierarchy. Cow #1 has the highest rank; cow #N has the least rank. Every cow had additionally been assigned a non-unique integer number in the range 0..(221 - 1).
Help FJ choose which cows will be fed first by selecting a sequence of consecutive cows in the line such that the bitwise "xor" between their assigned numbers has the maximum value. If there are several such sequences, choose the sequence for which its last cow has the highest rank. If there still is a tie, choose the shortest sequence.
Input
Line 1: A single integer N
Lines 2..N+1: N integers ranging from 0 to 221 - 1, representing the cows' assigned numbers. Line j describes cow of social hierarchy j-1.
Output
Line 1: Three space-separated integers, respectively: the maximum requested value, the position where the sequence begins, the position where the sequence ends.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A word is a string of lowercases. A word pattern is a string of lowercases, '?'s and '*'s. In a pattern, a '?' matches any single lowercase, and a '*' matches none or more lowercases.
There are many word patterns and some words in your hand. For each word, your task is to tell which patterns match it.
Input
The first line of input contains two integers N (0 < N <= 100000) and M (0 < M <=100), representing the number of word patterns and the number of words. Each of the following N lines contains a word pattern, assuming all the patterns are numbered from 0 to N-1. After those, each of the last M lines contains a word.
You can assume that the length of patterns will not exceed 6, and the length of words will not exceed 20.
Output
For each word, print a line contains the numbers of matched patterns by increasing order. Each number is followed by a single blank. If there is no pattern that can match the word, print "Not match".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, "dad", "eye" and "racecar" are all palindromes, but "odd", "see" and "orange" are not palindromes.
Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes.
Input
The first line of input file contains the number of strings n. The following n lines describe each string:
The i+1-th line contains the length of the i-th string li, then a single space and a string of li small letters of English alphabet.
You can assume that the total length of all strings will not exceed 2,000,000. Two strings in different line may be the same.
Output
Print out only one integer, the number of palindromes.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A dam has n water gates to let out water when necessary. Each water gate has its own capacity, water path and affected areas in the downstream. The affected areas may have a risk of flood when the water gate is open. The cost of potential damage caused by a water gate is measured in number calculated from the number of people and areas estimated to get affected.
Suppose a water gate Gi has the volumetric flow rate of Fi m3/hour and the damage cost of Ci. In a certain situation, the dam has the volume V m3 of water to flush out within T hours. Your task is to manage the opening of the water gates in order to get rid of at least the specified volume of water within a limited time in condition that the damage cost is minimized.
For example, a dam has 4 water gates and their properties are shown in the following table.
|
Water Gate |
G1 |
G2 |
G3 |
G4 |
|
Flow rate (m3/hour) |
720,000 |
50,000 |
130,000 |
1,200,000 |
|
Cost |
120,000 |
60,000 |
50,000 |
150,000 |
Case 1: You have to flush out the water 5 million m3 within 7 hours. The minimum cost will be 120,000 by letting the water gate G1 open for 7 hours.
Case 2: You have to flush out the water 5 million m3 within 30 hours. The minimum cost will be 110,000 by letting the water gates G2 and G3 open, for example, G2 is open for 29 hours and G3 is open for 28 hours.
Note that each water gate is independent and it can be open only in a unit of whole hour (no fraction of hour).
Input
The first line includes an integer n indicating number of water gates (1 <= n <= 20). Then the next n lines contain, in each line, two integers: Fi and Ci corresponding to the flow rate (m3/hour) and the damage cost of the water gate Gi respectively. The next line contains the number m which is the number of test cases (1 <= m <= 50). The following m lines contain, in each line, two integers: V and T corresponding to the volume (m3) of water to let out within T hours.
1 ≤ Fi ,V, Ci ≤ 109 , 1 ≤ T ≤ 1000)
Output
For each test case, print out the minimum cost in the exact format shown in the sample output below. If it is not possible to let out the water of volume V in T hours from the dam, print out “IMPOSSIBLE” (without quotation marks).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider the problem called Fun Coloring below.
Fun Coloring Problem
Instance: A finite set U and sets S1, S2, S3,…,Sm 
U and |Si| ≤ 3.
Problem: Is there a function f : U 
{RED, BLUE} such that at least one member of each Si is assigned a different color from the other members?
Given an instance of Fun Coloring Problem, your job is to find out whether such function f exists for the given instance.
Input
In this problem U = {x1, x2, x3,…,xn}. There are k instances of the problem. The first line of the input file contains a single integer k and the following lines describe k instances, each instance separated by a blank line. In each instance the first line contains two integers n and m with a blank in between. The second line contains some integers i’s representing xi’s in S1, each i separated by a blank. The third line contains some integers i’s representing xi’s in S2 and so on. The line m+2 contains some integers i’s representing xi’s in Sm. Following a blank line, the second instance of the problem is described in the same manner and so on until the kth instance is described. In all test cases, 1 ≤ k ≤ 13, 4 ≤ n ≤ 22, and 6 ≤ m ≤ 111.
Output
For each instance of the problem, if f exists, print a Y. Otherwise, print N. Your solution will contain one line of k Y’s (or N’s) without a blank in between. The first Y (or N) is the solution for instance 1. The second Y (or N) is the solution for instance 2, and so on. The last Y (or N) is the solution for instance k.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and an ordering on the elements in V, then the bandwidth of a node v is defined as the maximum distance in the ordering between v and any node to which it is connected in the graph. The bandwidth of the ordering is then defined as the maximum of the individual bandwidths. For example, consider the following graph:
This can be ordered in many ways, two of which are illustrated below:
For these orderings, the bandwidths of the nodes (in order) are 6, 6, 1, 4, 1, 1, 6, 6 giving an ordering bandwidth of 6, and 5, 3, 1, 4, 3, 5, 1, 4 giving an ordering bandwidth of 5.
Write a program that will find the ordering of a graph that minimises the bandwidth.
Input
Input will consist of a series of graphs. Each graph will appear on a line by itself. The entire file will be terminated by a line consisting of a single #. For each graph, the input will consist of a series of records separated by `;'. Each record will consist of a node name (a single upper case character in the the range `A' to `Z'), followed by a `:' and at least one of its neighbours. The graph will contain no more than 8 nodes.
Output
Output will consist of one line for each graph, listing the ordering of the nodes followed by an arrow (->) and the bandwidth for that ordering. All items must be separated from their neighbours by exactly one space. If more than one ordering produces the same bandwidth, then choose the smallest in lexicographic ordering, that is the one that would appear first in an alphabetic listing.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?
The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:
| Input Code | Topping |
| A | Anchovies |
| B | Black Olives |
| C | Canadian Bacon |
| D | Diced Garlic |
| E | Extra Cheese |
| F | Fresh Broccoli |
| G | Green Peppers |
| H | Ham |
| I | Italian Sausage |
| J | Jalapeno Peppers |
| K | Kielbasa |
| L | Lean Ground Beef |
| M | Mushrooms |
| N | Nonfat Feta Cheese |
| O | Onions |
| P | Pepperoni |
Your friends provide you with a line of text that describes their pizza preferences. For example, the line
+O-H+P;
reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line
-E-I-D+A+J;
indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.
Input
The input consists of a series of pizza constraints.
A pizza constraint is a list of 1 to 12 topping constraint lists each on a line by itself followed by a period on a line by itself.
A topping constraint list is a series of topping requests terminated by a single semicolon.
An topping request is a sign character (+/-) and then an uppercase letter from A to P.
Output
For each pizza constraint, provide a description of a pizza that satisfies it. A description is the string ``Toppings: " in columns 1 through 10 and then a series of letters, in alphabetical order, listing the toppings on the pizza. So, a pizza with onion, anchovies, fresh broccoli and Canadian bacon would be described by:
Toppings: ACFO
If no combination toppings can be found which satisfies at least one request of every person, your program should print the string
No pizza can satisfy these requests.
on a line by itself starting in column 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.
Input
The input file will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers 
. If n = 0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.
Output
For each test case, first output a line containing `Sums of ', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Jahir is a student of NSU ( Nice Students' University ). He hates the chapter Permutation & Combination of the subject Discrete Math. But his teacher give him a assignment to generate all the r combination of a string. But he is too busy with his new girlfriend to do the assignment himself. So he went to Shabuj, a student of CSE ( Calculation Science and Engineering ) in BUET ( Bangladesh University of Extraordinary Talents ). He asked him to make a program to generate the combinations. But Shabuj is always lazy. He wants your help.
Your task is to print all different r combinations of a string s (a r combination of a string s is a collection of exactly r letters from different positions in s).
There may be different permutations of the same combination; consider only the one that has its r characters in non-decreasing order.
The string consists of only lowercase letters. Any letter can occur more than once.
Input
The input is consist of several test cases. Each test case consists of a string s ( the length of s is between 1 and 30 ) and an integer r ( 0 < r <= length of s ).
Output
For each test case you have to print all different r combinations of s in lexicographic order in separate line. You can assume there are at most 1000 different ones.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are given a sequence of n numbers a0,..., an-1. A cyclic shift by k positions ( 0<=k<=n - 1) results in the following sequence: ak, ak+1,..., an-1, a0, a1,..., ak-1. How many of the n cyclic shifts satisfy the condition that the sum of the first i numbers is greater than or equal to zero for all i with 1<=i<=n?
Input
Each test case consists of two lines. The first contains the number n ( 1<=n<=106), the number of integers in the sequence. The second contains n integers a0,..., an-1 ( -1000<=ai<=1000) representing the sequence of numbers. The input will finish with a line containing 0.
Output
For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above. For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A mobile is a type of kinetic sculpture constructed to take advantage of the principle of equilibrium. It consists of a number of rods, from which weighted objects or further rods hang. The objects hanging from the rods balance each other, so that the rods remain more or less horizontal. Each rod hangs from only one string, which gives it freedom to rotate about the string.
We consider mobiles where each rod is attached to its string exactly in the middle, as in the figure underneath. You are given such a configuration, but the weights on the ends are chosen incorrectly, so that the mobile is not in equilibrium. Since that's not aesthetically pleasing, you decide to change some of the weights.
What is the minimum number of weights that you must change in order to bring the mobile to equilibrium? You may substitute any weight by any (possibly non-integer) weight. For the mobile shown in the figure, equilibrium can be reached by changing the middle weight from 7 to 3, so only 1 weight needs to changed.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
• One line with the structure of the mobile, which is a recursively defined expression of the form:
::= | "[" "," "]"
with a positive integer smaller than 109 indicating a weight and [,] indicating a rod with the two expressions at the ends of the rod. The total number of rods in the chain from a weight to the top of the mobile will be at most 16.
Output
Per testcase:
• One line with the minimum number of weights that have to be changed.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A prefix of a string is a substring starting at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", "car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate" is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.
In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo".
An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car" , not for "carriage" or any of the other words in the list that begins with "car".
Input
The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.
Output
The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.
Input
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.
Output
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Many gas stations use plastic digits on an illuminated sign to indicate prices. When there is an insufficient quantity of a particular digit, the attendant may substitute another one upside down.
The digit ``6" looks much like ``9" upside down. The digits ``0", ``1" and ``8" look like themselves. The digit ``2" looks a bit like a ``5" upside down (well, at least enough so that gas stations use it).
Due to rapidly increasing prices, a certain gas station has used all of its available digits to display the current price. Fortunately, this shortage of digits need not prevent the attendant from raising prices. She can simply rearrange the digits, possibly reversing some of them as described above.
Input & Output
Your job is to compute, given the current price of gas, the next highest price that can be displayed using exactly the same digits. The input consists of several lines, each containing between 2 and 30 digits (to account for future prices) and a decimal point immediately before the last digit. There are no useless leading zeroes; that is, there is a leading zero only if the price is less than 1. You are to compute the next highest price that can be displayed using the same digits and the same format rules. An input line containing a decimal point alone terminates the input. If the price cannot be raised, print `The price cannot be raised.'
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.
Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.
|
V A S E S |
||||||
|
1 |
2 |
3 |
4 |
5 |
||
|
Bunches |
1 (azaleas) |
7 | 23 | -5 | -24 | 16 |
|
2 (begonias) |
5 | 21 | -4 | 10 | 23 | |
|
3 (carnations) |
-21 |
5 | -4 | -20 | 20 | |
According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.
To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.
Input
- The first line contains two numbers: F, V.
- The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file
- 1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.
- F <= V <= 100 where V is the number of vases.
- -50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.
Output
The first line will contain the sum of aesthetic values for your arrangement.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.
Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.
You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.
Input
The first line contains two integers: the first is the number of villages V, 1 <= V <= 300, and the second is the number of post offices P, 1 <= P <= 30, P <= V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1 <= X <= 10000.
Output
The first line contains one integer S, which is the sum of all distances between each village and its nearest post office.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 <= N <= 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size D_i (1 <= D_i <= N) and approach the front desk to check in. Each group i requests a set of D_i contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+D_i-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters X_i and D_i which specify the vacating of rooms X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 <= M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and D_i (b) Three space-separated integers representing a check-out: 2, X_i, and D_i
Output
* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
John is going on a fishing trip. He has h hours available (1 <= h <= 16), and there are n lakes in the area (2 <= n <= 25) all reachable along a single, one-way road. John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless he wishes to. For each i = 1,...,n - 1, the number of 5-minute intervals it takes to travel from lake i to lake i + 1 is denoted ti (0 < ti <=192). For example, t3 = 4 means that it takes 20 minutes to travel from lake 3 to lake 4. To help plan his fishing trip, John has gathered some information about the lakes. For each lake i, the number of fish expected to be caught in the initial 5 minutes, denoted fi( fi >= 0 ), is known. Each 5 minutes of fishing decreases the number of fish expected to be caught in the next 5-minute interval by a constant rate of di (di >= 0). If the number of fish expected to be caught in an interval is less than or equal to di , there will be no more fish left in the lake in the next interval. To simplify the planning, John assumes that no one else will be fishing at the lakes to affect the number of fish he expects to catch.
Write a program to help John plan his fishing trip to maximize the number of fish expected to be caught. The number of minutes spent at each lake must be a multiple of 5.
Input
You will be given a number of cases in the input. Each case starts with a line containing n. This is followed by a line containing h. Next, there is a line of n integers specifying fi (1 <= i <=n), then a line of n integers di (1 <=i <=n), and finally, a line of n - 1 integers ti (1 <=i <=n - 1). Input is terminated by a case in which n = 0.
Output
For each test case, print the number of minutes spent at each lake, separated by commas, for the plan achieving the maximum number of fish expected to be caught (you should print the entire plan on one line even if it exceeds 80 characters). This is followed by a line containing the number of fish expected.
If multiple plans exist, choose the one that spends as long as possible at lake 1, even if no fish are expected to be caught in some intervals. If there is still a tie, choose the one that spends as long as possible at lake 2, and so on. Insert a blank line between cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
| Window position | Minimum value | Maximum value |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
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
The rotation game uses a # shaped board, which can hold 24 pieces of square blocks (see Fig.1). The blocks are marked with symbols 1, 2 and 3, with exactly 8 pieces of each kind.
Initially, the blocks are placed on the board randomly. Your task is to move the blocks so that the eight blocks placed in the center square have the same symbol marked. There is only one type of valid move, which is to rotate one of the four lines, each consisting of seven blocks. That is, six blocks in the line are moved towards the head by one block and the head block is moved to the end of the line. The eight possible moves are marked with capital letters A to H. Figure 1 illustrates two consecutive moves, move A and move C from some initial configuration.
Input
The input consists of no more than 30 test cases. Each test case has only one line that contains 24 numbers, which are the symbols of the blocks in the initial configuration. The rows of blocks are listed from top to bottom. For each row the blocks are listed from left to right. The numbers are separated by spaces. For example, the first test case in the sample input corresponds to the initial configuration in Fig.1. There are no blank lines between cases. There is a line containing a single `0' after the last test case that ends the input.
Output
For each test case, you must output two lines. The first line contains all the moves needed to reach the final configuration. Each move is a letter, ranging from `A' to `H', and there should not be any spaces between the letters in the line. If no moves are needed, output `No moves needed' instead. In the second line, you must output the symbol of the blocks in the center square after these moves. If there are several possible solutions, you must output the one that uses the least number of moves. If there is still more than one possible solution, you must output the solution that is smallest in dictionary order for the letters of the moves. There is no need to output blank lines between cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Prince Remmarguts solved the CHESS puzzle successfully. As an award, Uyuw planned to hold a concert in a huge piazza named after its great designer Ihsnayish.
The piazza in UDF - United Delta of Freedom’s downtown was a square of [0, 10000] * [0, 10000]. Some basket chairs had been standing there for years, but in a terrible mess. Look at the following graph.
In this case we have three chairs, and the audiences face the direction as what arrows have pointed out. The chairs were old-aged and too heavy to be moved. Princess Remmarguts told the piazza's current owner Mr. UW, to build a large stage inside it. The stage must be as large as possible, but he should also make sure the audience in every position of every chair would be able to see the stage without turning aside (that means the stage is in the forward direction of their own).
To make it simple, the stage could be set highly enough to make sure even thousands of chairs were in front of you, as long as you were facing the stage, you would be able to see the singer / pianist – Uyuw.
Being a mad idolater, can you tell them the maximal size of the stage?
Input
In the first line, there's a single non-negative integer N (N <= 20000), denoting the number of basket chairs. Each of the following lines contains four floating numbers x1, y1, x2, y2, which means there’s a basket chair on the line segment of (x1, y1) – (x2, y2), and facing to its LEFT (That a point (x, y) is at the LEFT side of this segment means that (x – x1) * (y – y2) – (x – x2) * (y – y1) >= 0).
Output
Output a single floating number, rounded to 1 digit after the decimal point. This is the maximal area of the stage.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It's well known that DNA Sequence is a sequence only contains A, C, T and G, and it's very useful to analyze a segment of DNA Sequence. For example, if an animal's DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don't contain those segments.
Suppose that DNA sequences of a species is a sequence that consists of A, C, T and G, and the length of sequences is a given integer n.
Input
First line contains two integer m (0 ≤ m ≤ 10), n (1 ≤ n ≤ 2 × 109). Here, m is the number of genetic disease segment, and n is the length of sequences.
Each of the next m lines contains a DNA genetic disease segment, and lengths of these segments are not larger than 10.
Output
An integer, the number of DNA sequences, mod 100000.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers. The administrator finds that some links are vital to the network, because failure of any one of them can cause that data can't be transformed between some computers. He call such a link a bridge. He is planning to add some new links one by one to eliminate all bridges.
You are to help the administrator by reporting the number of bridges in the network after each new link is added.
Input
The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤ 200,000).
Each of the following M lines contains two integers A and B ( 1≤ A ≠ B ≤ N), which indicates a link between computer A and B. Computers are numbered from 1 to N. It is guaranteed that any two computers are connected in the initial network.
The next line contains a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links the administrator plans to add to the network one by one.
The i-th line of the following Q lines contains two integer A and B (1 ≤ A ≠ B ≤ N), which is the i-th added new link connecting computer A and B.
The last test case is followed by a line containing two zeros.
Output
For each test case, print a line containing the test case number( beginning with 1) and Q lines, the i-th of which contains a integer indicating the number of bridges in the network after the first i new links are added. Print a blank line after the output for each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In an extended version of the game Lights Out, is a puzzle with 5 rows of 6 buttons each (the actual puzzle has 5 rows of 5 buttons each). Each button has a light. When a button is pressed, that button and each of its (up to four) neighbors above, below, right and left, has the state of its light reversed. (If on, the light is turned off; if off, the light is turned on.) Buttons in the corners change the state of 3 buttons; buttons on an edge change the state of 4 buttons and other buttons change the state of 5. For example, if the buttons marked X on the left below were to be pressed,the display would change to the image on the right.
The aim of the game is, starting from any initial set of lights on in the display, to press buttons to get the display to a state where all lights are off. When adjacent buttons are pressed, the action of one button can undo the effect of another. For instance, in the display below, pressing buttons marked X in the left display results in the right display.Note that the buttons in row 2 column 3 and row 2 column 5 both change the state of the button in row 2 column 4,so that, in the end, its state is unchanged.
Note:
1. It does not matter what order the buttons are pressed.
2. If a button is pressed a second time, it exactly cancels the effect of the first press, so no button ever need be pressed more than once.
3. As illustrated in the second diagram, all the lights in the first row may be turned off, by pressing the corresponding buttons in the second row. By repeating this process in each row, all the lights in the first
four rows may be turned out. Similarly, by pressing buttons in columns 2, 3 ?, all lights in the first 5 columns may be turned off.
Write a program to solve the puzzle.
Input
The first line of the input is a positive integer n which is the number of puzzles that follow. Each puzzle will be five lines, each of which has six 0 or 1 separated by one or more spaces. A 0 indicates that the light is off, while a 1 indicates that the light is on initially.
Output
For each puzzle, the output consists of a line with the string: "PUZZLE #m", where m is the index of the puzzle in the input file. Following that line, is a puzzle-like display (in the same format as the input) . In this case, 1's indicate buttons that must be pressed to solve the puzzle, while 0 indicate buttons, which are not pressed. There should be exactly one space between each 0 or 1 in the output puzzle-like display.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.
Input
The input file contains several lines, one for each number to be displayed. Each line contains two integers s, n (1<=s<=10, 0<=n<=99999999), where n is the number to be displayed and s is the size in which it shall be displayed.
The input file will be terminated by a line containing two zeros. This line should not be processed.
Output
Output the numbers given in the input file in an LC-display-style using s ``-'' signs for the horizontal segments and s ``|'' signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.
Output a blank line after each number. (You will find a sample of each digit in the sample output.)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
.png)
One day, you want to practice jogging on the playground. But some items usually run into the track where you are jogging. For example, footballs, baseballs, and other people are the majority of the items. You want to know the situation of the track every time. To simplify this problem, the track looks like an array of n grids. There are q events that happen on the track. Looks like
1. “c x y” means “counting the number of items on the interval [x, y]”
2. “p x y” means “x items (run into) / (are picked up) on the grid y”
For every type-1 event, please out the number of items.
Input
Each test case starts with a line containing two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 2 ∗ 105) indicating the length of the track and the number of events.
Following this are q lines, each containing one character c and two integers x, y. The first character c specifies the type of the event. For the type-1 event, x and y mean the interval you want to check. (1 ≤ x ≤ y ≤ n) For the type-2 event, x means the number of the items running into the track (when x > 0) or the number of the items been taken out (when x < 0).
Output
For every type-1 event, output the number of the items on the interval [x, y].
Sample Input Download
Sample Output Download
Tags
Discuss
Description
.png)
You are the host of the restaurant Wagnaria. Some rainy day, because of the broken roofs, there are n dripping positions. You need to put some bowls to catch the rain. So, you order k employees to clean the bowls at every moment. Every employee will put the large trashcan to a best position. At every moment, he will take an empty bowl to some bowl’s location assigned to him to swap the empty bowl and bowl filled of water. You want these employees to find the best allocation. Please write a program to minimize the total distance every employee needs to walk.
For example, there are 9 dripping location {1, 2, 3, 7, 8, 9, 13, 14, 15} and 3 employees.
The best allocation is:
Employee 1 is at position 2. Employee 2 is at position 8. Employee 3 is at position 14.
Then the actions of the employee 1:
1. Take an empty bowl to the bowl 1 to swap the two bowls. (Distance: 1)
2. Go to the position of the employee 1’s trashcan to throw rain in the bowl. (Distance: 1)
3. Take an empty bowl to the bowl 2 to swap the two bowls. (Distance: 0)
4. Go to the position of the employee 1’s trashcan to throw rain in the bowl. (Distance: 0)
5. Take an empty bowl to the bowl 3 to swap the two bowls. (Distance: 1)
6. Go to the position of the employee 1’s trashcan to throw rain in the bowl. (Distance: 1)
The total distance employee 1 needs to walk is 4. The total minimize distances all employee need to walk is 12.
To simplify this problem, the employees can ONLY put the trashcan at the position with integer number.
Input
Each test case starts with a line containing two integers n(1 ≤ n ≤ 1000) and k (1 ≤ k ≤ 1000) indicating the number of the dripping positions and the number of employees. Following this is one line, containing n integers xi specifies the dripping position.
1 ≤ x1 < x2 < x3 < ⋯ < xn ≤ 1000
Output
Output the minimum total distance all employees need to walk.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Farmer John owns a large number of fences that must be repaired annually. He traverses the fences by riding a horse along each and every one of them (and nowhere else) and fixing the broken parts. Farmer John is as lazy as the next farmer and hates to ride the same fence twice. Your program must read in a description of a network of fences and tell Farmer John a path to traverse each fence length exactly once, if possible. Farmer J can, if he wishes, start and finish at any fence intersection.
Every fence connects two fence intersections, which are numbered inclusively from 1 through 500 (though some farms have far fewer than 500 intersections). Any number of fences (>=1) can meet at a fence intersection. It is always possible to ride from any fence to any other fence (i.e., all fences are "connected").
Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude.
There will always be at least one solution for each set of input data supplied to your program for testing.
Input
Line 1: The number of fences, F (1 <= F <= 1024)
Line 2..F+1: A pair of integers (1 <= i, j <= 500) that tell which pair of intersections
this fence connects
Output
The output consists of F+1 lines, each containing a single integer. Print the number of the starting intersection on the first line, the next intersection's number on the next line, and so on, until the final intersection on the last line. There might be many possible answers to any given input set, but only one is ordered correctly.
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
Finding the convex hull of a set of points is an important problem that is often part of a larger problem. There are many algorithms for finding the convex hull. Since problems involving the convex hull sometimes appear in the ACM World Finals, it is a good idea for contestants to know some of these algorithms.
Finding the convex hull of a set of points in the plane can be divided into two sub-tasks. First, given a set of points, find a subset of those points that, when joined with line segments, form a convex polygon that encloses all of the original points. Second, output the points of the convex hull in order, walking counter-clockwise around the polygon.
Input
The first line of each test case contains a single integer 3 <= n <= 100000, the number of points. The following n lines of the test case each describe a point. Each of these lines contains two integers, separated by spaces. The two integers specify the x- and y-coordinates of the point. The x- and y-coordinates of each point will be no less than -1000000000 and no greater than 1000000000. No point will appear more than once in the same test case. The points in a test case will never all lie on a line
Output
For each test case, generate the following output. First, output a line containing a single integer m, the number of points on the convex hull. Next output m lines, each describing a point on the convex hull, in counter-clockwise order around the hull. Each of these lines should contain the x-coordinate of the point, followed by a space, followed by the y-coordinate of the point. Start with the point on the hull whose x-coordinate is minimal. If there are multiple such points, start with the one whose y-coordinate is minimal.
Print blank line between two cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Give you a simple polygon, please count its area.
Input
Each test case starts with a line containing n (1<= n <= 100000), the number of points. The following n lines of the test case each describe a point, in counter-clockwise order around the hull.
The x- and y-coordinates of each point will be no less than -1000000000 and no greater than 1000000000.
There is a blank between cases.
Output
Output the area of the polygon one decimal places.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Give you many distinct numbers, please find the maximum number of the pairs (a, b) such that the sum of a and b is a prime number.
One number can only use once.
For example, the set is 4, 5, 6, and 7. The maximum number of the set is 2. The groups are {4, 7} and {5, 6}. Their summations are both 11.
Input
Each test case starts with a line containing n (1<= n <= 400), the number of points. The following n lines are n numbers (1<=number<=1000000)
One number will only appear one time.
Output
Print the maximum pair number.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed w kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.
Pete and Billy are great fans of even numbers, that's why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that's why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.
Input
Input line contains integer number w (1 ≤ w ≤ 1000000000) — the weight of the watermelon bought by the boys.
Output
Print YES, if the boys can divide the watermelon into two parts, each of them weighing even number of kilos; and NO in the opposite case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the ancient pirate ages, the Pirate Land was divided into two teams of pirates, namely, the Buccaneer and the Barbary pirates. Each pirate’s team was not fixed, sometimes the opponent pirates attacked and he was taken away to the other pirate team. All on a sudden a magician appeared in the Pirate Land, where he was making transition of pirates from their team to other team at his own will. Of course, handy spells were used. The process of changing team was known as mutating.
There were N pirates and all of the pirates have a unique id from 0 to N-1. The great magician could mutate a bunch of pirates with consecutive id’s to another one.
Suppose there were 100 pirates in the pirate land and all of them were Barbary pirates, then the magician could cast a spell to change pirates with id’s from 10 to 33 to Buccaneer pirates. Then the whole pirate land would have 24 Buccaneer and 76 Barbary pirates.
The magician was very fast casting the spell. Once, God started to dislike this. God had favor for the Buccaneer pirates and God asked the magician, “Tell me, how many of the pirates of index from 2 to 30 are Buccaneer pirates?”. Now the magician was puzzled as he was only efficient in casting spells, not in counting J
Being clever enough, the magician captured a clever man from the Earth Land. And unfortunately it’s you! Now you have to answer the God’s questions.
Input
The first line of input will contain number of test cases T.
For each test case:
The first part of the description will be of the pirate land. There could be up to N (1<=N<=1024000) pirates. Each pirate is either assigned to Buccaneer or Barbary Pirate. Buccaneer pirates are described by ‘1’ (ONE) and Barbary pirates are described by ‘0’ (ZERO). You have to build a string of the pirates’ description. Each case starts with an integer M (M<=100), where M pair lines follow. In each pair of lines (we call it a set), first has an integer T (T <= 200) and next one has a nonempty string Pirates (consisting of 0 and 1, 0 for Barbary, 1 for Buccaneer, has maximum length of 50). For each pair concatenate the string Pirates, T times. Concatenate all the resulting M sets of strings to build the pirate description. The final concatenated string describes the pirates from index 0 to end (N-1 for N pirates).
Now the next part of the input will contain queries. First line of next part has an integer Q describing number of queries. Each subsequence Q (1<=Q<=1000) lines describe each query. Each query has a string F or E or I or S and two integers, a and b denoting indexes. The meaning of the query string are follows:
F a b, means, mutate the pirates from index a to b to Buccaneer Pirates.
E a b, means, mutate the pirates from index a to b to Barbary Pirates.
I a b, means, mutate the pirates from index a to b to inverse pirates.
S a b, means, “God’s query” God is asking a question: “Tell me, how many Buccaneer pirates are there from index a to b?”
(a <= b, 0 <= a < n, 0 <= b < n, index range are inclusive)
Output
For each test print the case number as the sample output suggests. Then for each of “God’s query”, output the query number, colon (:) and a space and the answer to the query as the sample suggest.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N and K find the N’th permutation of the integers from 1 to K when those permutations are lexicographically ordered. N starts from 0. Since N is very large N will be represented by a sequence of K non-negative integers S1, S2 ,…, Sk. From this sequence of integers N can be calculated with the following expression.
Input
First line of the input contains T(≤10) the number of test cases. Each of these test cases consists of 2 lines. First line contains a integer K(1≤K≤50000). Next line contains K integers S1, S2 ,…, Sk.(0≤Si≤K-i).
Output
For each test case output contains N’th permutation of the integers from 1 to K. These K integers should be separated by a single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…
The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by train to Mianyang, Sichuan Province for the winter camp selection of the national team of Olympiad in Informatics.
It was one o’clock a.m. and dark outside. Chill wind from the northwest did not scare off the people in the queue. The cold night gave the Little Cat a shiver. Why not find a problem to think about? That was none the less better than freezing to death!
People kept jumping the queue. Since it was too dark around, such moves would not be discovered even by the people adjacent to the queue-jumpers. “If every person in the queue is assigned an integral value and all the information about those who have jumped the queue and where they stand after queue-jumping is given, can I find out the final order of people in the queue?” Thought the Little Cat.
Input
There will be several test cases in the input. Each test case consists of N + 1 lines where N (1 ≤ N ≤ 200,000) is given in the first line of the test case. The next N lines contain the pairs of values Posi and Vali in the increasing order of i (1 ≤ i ≤ N). For each i, the ranges and meanings of Posi and Vali are as follows:
- Posi ∈ [0, i − 1] — The i-th person came to the queue and stood right behind the Posi-th person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
- Vali ∈ [0, 32767] — The i-th person was assigned the value Vali.
There no blank lines between test cases. Proceed to the end of input.
Output
For each test cases, output a single line of space-separated integers which are the values of people in the order they stand in the queue.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sequence of n elements S with properly increasing integers. It means that the ith number must be less than the i+1th number. (Si < Si+1) Given a range number d, please count the number of the subsequences that the i+1th number is equal to or grater than the ith number. (S’i + d S’i+1, for every subsequence S’)
For example, S={1, 3, 5}, d=4. The answer is 7. The subsequences are {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, and {1,3,5}. If d=2, then the sequences will be {1}, {3}, {5}, {1,3}, {3,5}, and {1,3,5}.
Input
Each test case starts with a line containing two integers n (1≤n≤106) and d (1≤d≤109) indicating the length of the sequence and the range between every two adjacent numbers. Following this is one line, containing n integers.
Output
For each test case, out the number of the sequences according the rules. This number may be very large. Please output the number mod 100000077.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given four integers A, B, X0 and Y0 such that gcd(A, B) = 1 and A × X0 + B × Y0 = 1. Find another pair of integers X’ and Y’, where X’ ≠ X0, Y’ ≠ Y0, |X’|, |Y’| ≤ 109 and A × X’ + B × Y’ = 1.
The pair X0, Y0 is selected by the following algorithm:
pair< int, int > extended_euclidean(int a, int b) {
if (b == 0)
return make_pair(1, 0);
else {
pair< int, int > t = extended_euclidean(b, a % b);
return make_pair(t.second, t.first – a / b * t.second);
}
}
However, that is another pair of shoes and the intended solution does not depend on how the pair is chosen.
Input
Each test case consists of four space-separated integers A, B, X0 and Y0 (A, B, |X0|, |Y0| ≤ 108, gcd(A, B) = 1, A ≠ 0, B ≠ 0) in a line. The input is terminated by A = B = X0 = Y0 = 0.
Output
For each test case, output two integers X’ and Y’ (|X’|, |Y’| ≤ 109) separated by a space character. If there are more than one pairs that meet the requirement, you may output any one of them.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are capturing the awesome meteor shower tonight. We model the vision seen through the camera lens as a rectangle R on the two dimensional grid, with two sides parallel to the x-axis and the other two sides parallel to the y-axis. Meteors are modeled as line segments on the grid. We can capture a meteor if there is point p on the line segment representing that meteor such that p ∊ R, and we say p ∊ R if p falls inside the rectangle R or on its boundary.
Count the number of meteors that can be captured.
Input
Each test case begins with five space-separated integers N (1 ≤ N ≤ 1000), X1, Y1, X2, Y2 (X1 < X2, Y1 < Y2, |X1|, |Y1|, |X2|, |Y2| ≤ 1000) in a line, where N denotes the number of visible meteors on the two dimensional grid, and (X1, Y1) and (X2, Y2) represent the lower-left and upper-right coordinates of the rectangle R.
There are N lines follow, each line consists of four integers x1, y1, x2, y2 (|x1|, |y1|, |x2|, |y2| ≤ 1000), where (x1, y1) and (x2, y2) are two end points of the line segment representing the meteor.
There is a blank line after each test case, and the input is terminated by a line consists of five zeros.
Output
Output an integer in a line for each test case, which is the number of meteors that can be captured.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a lever of length L, with some weights placing on it, find an integer point p in the range [0, L − 1] to place the pivot and make the lever in balance. The torque ti contributed by a weight wi at point i is wi × (i − p), and the lever is said to be in balance if ∑ ti = 0.
The figure above shows an example of L = 4, and the pivot is selected at p = 2. Note that the selected position fails to balance the lever since ∑ ti = −1. In fact, no integer point in the range [0, L – 1] is able to balance the lever in this scenario.
Input
Each test case begins with a line consists of an integer L (2 ≤ L ≤ 10000), denoting the length of the lever. The following line contains L space-separated integers wi (0 ≤ i < L, 0 ≤ wi ≤ 100, ∑ wi > 0), where wi denotes the weight at position i or nothing is placed there if wi = 0.
The input is terminated by L = 0.
Output
For each test case, output an integer in a line representing the position to place the pivot so that the lever can be balanced. In case that no such integer point exists, or there are more than one possible solution, output −1 instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are ordered by the king to analyze the financial report of your country.
There are N days in a year, and the report consists of exactly N integers. Each integer represents the incomes or the outgoings of the day. The king is interested about some consecutive days (possibly empty) no more than a year, such that the value of total incomes minus total outgoings during the interval is maximized. Note that the intervals that starts from the current year and ends at the next year should also be considered, provided the length of the interval is less than or equal to N. It is assumed that the same day of different years have the same amount of incomes or outgoings.
Input
Each test case begins with a line consists of an integer N (N ≤ 105), denoting the number of days in a year. The following line contains N integers ai (|ai| ≤ 100), representing the incomes or the outgoings of the i-th day in a year.
The input is terminated by N = 0.
Output
Output an integer in a line for each test case, representing the maximum possible value.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are initially N buckets of oats on the wall, numbered from 1 to N and arranged in a circular shape. Now, starting from bucket number 1, every M bucket of oats will be eaten until there is only one bucket left. What is the number of that bucket?
Input
Each test case consists of two space-separated integers N and M (2 ≤ N ≤ 100, 1 ≤ M ≤ 10000), representing the variables defined in the problem statement.
The input is terminated by N = M = 0.
Output
2Output the number of the last bucket in a line for each test case
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Yup, your knapsack is running out of space again. That’s why you plan to reduce the space occupied by the currencies of the game you are playing so that you can bring more other items with you. There are 6 different values of coins, $0.01, $0.05, $0.1, $0.5, $1 and $2. What is the minimum number of coins to represent D dollars, assuming that the supplies of each type of coins are unlimited?
Input
Each test case consists of a floating point number D (0 < D ≤ 20.00) in a line, with exactly two digits after the decimal point, representing the amount of your money.
The input is terminated by D = 0.00.
Output
Output the minimum number of coins you need to bring if you have D dollars in a line, assuming that the supplies of each type of coins are unlimited.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the hand gestures of the two rock-paper-scissors players, determine if the first player win the game. Note that rock defeats scissors, scissors defeats paper and paper defeats rock. Two players tie if they show the same symbol.
Input
Each test case consists of two space-separated strings (which can only be “rock”, “paper” or “scissors”) in a line, representing the symbol shown by the first and the second player, respectively.
The input is terminated by end-of-file (EOF).
Output
2For each test case, output a line that consists of the string “win”, “tie” or “lose” to indicate that the first player win, lose, or two players tie.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are distributing N toys into M boxes, which will be sending as gifts to children. It doesn’t matter each of the boxes is received by whom, but different toys packed into the same box is considered different. That is to say, toys are considered different, but boxes are considered indistinguishable. Count the number of ways to distribute N toys into M boxes, and no boxes should be left empty.
Input
Each test case consists of two space-separated integers N and M (1 ≤ M ≤ N ≤ 1000) in a line, representing the number of toys and boxes.
The input is terminated by N = M = 0.
Output
For each test case, output a line that consists of an integer, representing the total number of ways to distribute these toys, mod 10007.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two integer sequences A and B, with their values denoted by ai (1 ≤ i ≤ N) and bj (1 ≤ j ≤ M), we said that the sequence B matches A at index k, if there exists an integer d, such that ak + j = bj + d, 1 ≤ j ≤ M, k + j ≤ N. You have to count how many distinct k are there.
Input
Each test case begins with a line consists of two integers N and M (2 ≤ M ≤ N ≤ 50000), denoting the length of integer sequence A and B. The second line contains N integers ai (|ai| ≤ 108), and the third line contains M integers bj (|bj| ≤ 108).
The input is terminated by N = M = 0.
Output
For each test case, output a line that consists of an integer, denoting the number of matches.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are a girl. You are a young girl. You are a young and beautiful girl. Based on many reasons above, someone always wants to meet you. And you always want to avoid someone. Some day, your friends finally collect enough information about someone to analysis. These data are the probability that someone appears in every road. Now, you want to take the course. But you don’t want to meet someone. You can compute the probability before going out.
At first, the map records every possible path from the dormitory to the classroom. Guarantees the map doesn’t have any cycle. In every location, you have equal probability to go to the next locations. In every road, you have the probability that someone appears. Please output the probability that you will meet someone.
Input
Each test case starts with a line containing two integers n(2<=n<=100) and m indicating the number of locations on the map and the number of the roads. Following this are m lines, each containing 3 integers representing the endpoints of the directed road ui, vi (0<=ui,vi<=n) and the probability that someone appears in this road pi (0<=pi<=100). The summation of pi will be 100. The map of the path doesn’t have any cycle. The number of the dormitory and the classroom are 0 and n-1.
Output
Output the probability that you meet someone.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are the best friend of some girl. You always prevent someone from approaching your friend. On a Friday night, your friend is waiting for the bus to get away the campus. Unfortunately, someone heard about this. He wants to take the same bus to make a chance to chat with your friend. To save the world, you need to stop someone to get to the bus stop before the bus comes. “Dao Dan” is the Chinese pronunciation of the missile and also a name of the salesman who sells the missiles. You can buy ONLY ONE missile. And the power-k missile will destroy ALL roads whose stability is less than or equal to k. To make your friend safe and save the money, what is the minimum power of the missile you need to buy to archive the goal?
Input
Each test case starts with a line containing three integers n(2<=n<=100000) ,m(1<=m<=200000) and t(0<=t<=109) indicating the number of locations on the map, the number of the roads, and the time that the bus “exactly” get away from the bus stop. Following this are m lines, each containing 4 integers representing the endpoints of the bi-directed road ui, vi (0<=ui,vi
Output
Output the minimum power of the missile you need to buy. If you don’t need to buy the missile, output “Safe.”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
“Dao Dan” is you. You are “Dao Dan”. Besides the missile salesman, you have a totally different identity – a teacher. You’re lazy and busy. You decide to put everything boring to an Automatic Laboring Amazing Navigator (which called ALAN) to handle.
Nowadays, you make a final exam for the course. Every question sheet is full of the characters. You are too lazy to write a complex program into ALAN. You decide to check whether the keyword is inside the students’ replications. If the keyword is inside the replication, he will get the full points. Otherwise, he will be failed.
Input
Each test case starts with two lines. The first line contains the student’s replication S (1<=|S|<=106) . The second line contains the keyword, which you want to see T(1<=|T|<=104) .
Output
If the keyword T is inside the replication S, output “100”. Otherwise, output “0”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are a bus driver. Someday, you heard about the act of the terror. The rumor says the terrorist will destroy the bus to the campus. (Actually, the truth is to destroy the roads. But you don’t know the truth.) You don’t want to be involved in this accident. So, you call a lot of colleagues who don’t know about the act of the terror to drive the bus from the same source (the company) to the same destination (the campus). You think more bus can confuse the terrorist. Because of safety, you want the paths these buses passed are all road-disjoint. How many road-disjoint paths can buses run at the same time?
Input
Each test case starts with a line containing three integers n(2<=n<=100), and m(1<=m<=1000) indicating the number of locations on the map, and the number of the roads. Following this are m lines, each containing 2 integers representing the endpoints of the directed road ui, vi (0<=ui,vi
Output
Output the maximum buses that can run from the company to the campus with all road-disjoint paths.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are someone. You don’t see some girl for long days. You are very angry and confused. There must be some things or some ones to prevent you from doing so. You need to be more active. You decide to take a tour in the campus to look for some girl at regular time. At regular time, you will traverse every road inside the campus. So, you want to find a way to traverse all roads and to avoid traversing some road twice. The source and the destination of the path must be the dormitory. Can you find the path?
Input
Each test case starts with a line containing three integers n(1<=n<=105), and m(1<=m<=106) indicating the number of locations on the map, and the number of the directed roads you want to check. Following this are m lines, each containing 2 integers representing the endpoints of the directed road ui, vi(0<=ui,vi
Output
For each test case, output one line containing the best lexical order of the tour. If the tour doesn’t exist, please output “No Way”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are a friend of someone and some girl. To make the world better, when you walk with someone, you will send a text message to notify some girl where someone goes. This is the reason why someone always cannot meet some girl. You’re tired to do this thing again and again. You decide to set up the sensor network to detect someone. You put many of them in the campus. If someone is near the sensor, the sensor will send to the message to some girl automatically. Unfortunately, because of the problem about the wave, the sensors cannot be too close to each other. You realize this remark from the readme of the sensors after the setup. You remember the positions of the sensors. Try to check whether a pair of the sensors is too close.
Input
Each test case starts with a line containing two integers n(1<=n<=105) and d(1<=n<=107) indicating the number of sensors on the campus and the minimum safe distances between every two sensors. Following this are n lines, each containing 2 integers representing the position of the sensor xi, yi (|xi|,|yi|<=107) .
Output
If there exists a pair of too close sensors, output “Reconstruct”.
Otherwise, output “Go Go Go!!”
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are the friend of someone. You realize the truth about the sensor network from the question sheet of CPT final exam, which you’re reading right now. You decide to help your best friend, someone. You go to threaten Dao Dan to hand in the data sheet of the sensor network. (Yes, the gossip king is Dao Dan’s 3rd identities. He knows everything you want to know.) You decide to use the fence with the shortest length to surround the sensors all together in one region. Then, tell someone not to enter the region. As the best friend of someone, you should let him pay for the fence. Please output the length of shortest fence times 5 (unit price of the wood) times 10 (unit price of friendship).
Input
Each test case starts with a line containing one integers n(1<=n<=105) indicating the number of sensors on the campus. Following this are n lines, each containing 2 integers representing the position of the sensor xi, yi (|xi|,|yi|<=107).
Output
Please output the price of the fence, which is equal to the length of the fence times 50.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
CKL is dining with his friends. They sit around a table with a Lazy Susan on it. We number the people around the table from 1 to N consecutively in clock-wise order. Initially, there is exactly one dish in front of each person, and we also number them from 1 to N, which corresponds to the people’s number. However, not all of the diners wish to taste the dish in front of them, so we need to turn the tray and pass the dish to their front. A step to turn the tray is defined by passing the dishes originally in front of everyone to their left or right neighbors. A person is said to be served if the dish he or she wants to taste has been passed to his or her front at least once, or the dish is initially in the front of him or her. Find the minimum number of steps to turn the tray such that all of the diners are served.
Input
Each test case begins with a line consists of an integer N (1 ≤ N ≤ 1000), denoting the number of diners and dishes. The second line contains N integers di (1 ≤ di ≤ N), representing that the i-th diner wish to taste the dish which is initially placed in front of the di-th diner.
The input is terminated by N = 0.
Output
For each test case, output a line that consists of an integer, representing the minimum number of steps.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are a student in Dao Dan’s class. Someday, Dao Dan opens the file of the student’s grades to edit. The grades of the students are either failed or passed. He wants to adjust the grades fast. He calls ALAN to write a program, which provides 4 operations:
(a) p x y: Let the student whose id is between [x, y] passed.
(b) f x y : Let the student whose id is between [x, y] failed.
(c) q x y : Count then number of passed student whose id is between [x, y].
(d) r x y : Let the grades of the students whose id is between [x, y] reverse. (Passed<->Failed)
You want to help ALAN write the program. Maybe ALAN will like you to let you passed without telling Dao Dan.
Input
Each test case starts with a line containing two integers n(1<=n<=105) and q(1<=q<=2*105) indicating the number of the student and the number of events. Then one line contains a P-F string representing the original grade of the student. Following this are q lines, each containing one character c and two integers x, y. The first character c specifies the type of the event. For every event, x and y mean the interval you want to adjust(1<=x<=y<=n).
Output
For every type-(c) event, output the number of the passed student whose ID is between [x, y].
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Finally, someone meets some girl. So, the end of the world is coming. Some girl becomes a sacrificial offering of this year to avoid someone to be close to other one in one year. This is totally your fault, because someone’s friend discovers your sensor network in the campus. It’s too late to save the world. What you can do is to revenge. You are so evil and you want to edit someone’s grade. You randomly select the interval of the grades and give the highest grade a random value. Please output the grades after editing.
Input
Each test case starts with a line containing two integers n(1<=n<=105) and q(1<=q<=2*105)indicating the number of the grades and the number of events. Then, one line contains n integers representing someone’s original grades. Following this are q lines, each containing three integers x, y, c(1<=x<=y<=n). For every event, adjusts the highest value between [x, y] to c. If there is more than one highest value, choose the number has the smaller index.
Output
Please output one line containing someone’s final grades.
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
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).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Palindrome is a string that is identical to its reverse, like "level" or "aba". Check whether a given string is a palindrome or not.
Input
The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000. The number of test case is less than 1000.
Problem size for the four testcases
0 < length of each string < 1000
0 < length of each string < 10000
0 < length of each string < 100000
0 < length of each string < 100000
Output
For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Mode means the most frequent value in a data set. Given a sequence of integers, find out their mode.
Input
There are several numbers of test cases. Each case begins with an integer N. The next line contains N integers separated by a blank space. Each number is less than 1000 and greater than 0. The input is terminated if N = 0.
Problem size for the four testcases
1 <= N <= 1000 (1 second)
1 <= N <= 10000 (1 second)
1 <= N <= 1000000 (1 second)
1 <= N <= 10000000 (3 seconds)
Output
For each test case, print the mode of the sequence. If the mode is not unique, print the smallest one.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maintain a doubly linked list, which supports the following operations:
(1) IH i : Insert a new integer i to the head of the list.
(2) IT i : Insert a new integer i to the tail of the list.
(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.
(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.
(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.
To improve the performance, it is suggested that three pointers be maintained: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.
Input
There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains no more than 500000 operations, and it is terminated by end-of-file (EOF). You may assume that i will fit in a 32-bit signed integer. The list is initially empty.
Output
For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Mid-Square hash function works as follows.
(1) The number of hash values is 65536, which are numbered from 0 to 65535.
(2) To obtain the hash value for an integer, the hash function squares the key and return 16 bits from the middle of the square; key is considered as a 32-bit unsigned integer.
Input will contain these commands:
(1) INSERT i – Insert the integer i into the hash.
(2) DELETE i – Delete the integer i from the hash, i will be in the hash table.
(3) PRINT i – Print the elements that have the same address as integer i in the hash table.
Input
There is only one data set in the input. Each line contains a single command. The range of the given integer is considered as a 32-bit unsigned integer, and the number of commands will be no more than 200000. The input is terminated by end-of-file (EOF), and the hash table is initially empty.
Output
For each “PRINT” command, output a line which contains integers of the same address as the given integer i in ascending order, including i. Each distinct integer should appear exactly once, and a single space character should be printed to separate two successive integers. In case that i is not found in the hash, print “Null” instead, even there are other integers in the same address of the hash table.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a tree, and the distance between two vertices is the minimum number of edges to traverse from one to the other. Then, the diameter of a tree is defined to be the maximum distance between any two vertices. Please find the diameter of the tree.
The diameter can be found by the following steps:
1. Pick any vertex v and perform BFS starting from v.
2. Let u be one of the vertex that is farthest away from v.
3. Perform BFS starting from u.
4. Let w be one of the vertex that is farthest away from u.
5. Output the distance between u and w as the answer.
Input
The first line of input is an integer T (T <= 40) denoting the number of cases following.
For each case, the first line contains an integer N, denoting the number of nodes. Nodes are numbered from 1 to N. Then N-1 lines follows, each line contains two numbers of node which are connected by an edge.
Cases are separated by a blank line.
Problem size for the four testcases
1 < N < 10
1 < N < 100
1 < N < 1000
1 < N < 200000
Output
For each case a line, output the diameter.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000), denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b (1 <= a,b <= 1000), which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Output
For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within this range.
Input
The first line contains an integer t, which indicates the number of test cases. In each test case, the first line contains an integer n (n<=100000), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-50000 <= ai <= 50000). The followed line contains a positive integer q (q <= 10000), denoting the number of queries. Next q lines define q queries, one per line. Each query is specified by two integers a and b(1<=a<=b<=n), meaning a range, in which the partial sum of the given integers are queried.
Output
For each query, output a line with the partial sum of the given integers within the queried range.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are some line segments in 1 dimensional space. If two segments overlap or one segment’s start is another segment’s end, we consider them as one segment. Please output the length of the longest segment.
Input
There are multiple of test cases. Each case begins with an integer N (1 <= N <= 106) which represents the number of line segments. In the next N lines, each line contains two integers a and b (1 <= a <= b <= 109) representing a line segment. The input is terminated by N = 0.
Output
For each test case, output the length of the longest segment.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Please maintain a max-heap, which stores integers and is able to support following operations:
(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.
(2) POP – Delete the maximum element from the heap.
(3) TOP – Print the maximum element in the heap.
Input
There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 10000 at any time.
Output
For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a map, how fast can you get the two keys and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls. You have to get the two keys first and then you can go to the door. Notice that before you get the both keys, you can not pass the door.
Hint: Go to the nearest key first is not always the best choice, see the sample test cases.
Input
The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 <= R, C <= 1000) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:
s : Your start position.
. : A free square that you can move.
k : The position of the key.
w : The wall.
d : The door.
There are exactly two keys and exactly one door.
There is one blank line after each map. The input is terminated by two zeros in place of the map size.
Output
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to reach the door. If no way to reach the door, output the string "No solution." instead. One step is defined as a movement between two adjacent squares. Grabbing a key or unlocking a door does not count as a step.