| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 4000 | Airplane Parking |
|
| 4040 | Alien |
|
| 6031 | Paper Presentation |
|
| 6037 | Stopped Watches |
|
| 6047 | The Islands |
|
Description
During this economic crisis time, Jack has started an incredible new business related to air travel, a parking-lot for airplane. He bought a very large land to park airplanes. However the land is very narrow, so that the only way airplanes can go in or go out of the parking lot must be in the Last-In First-Out fashion (see picture below). He only has spaces in the parking lot so he cannot take some airplane at the end out so that other airplanes can move.
In this case, it is possible to accommodate airplane 1, 2, and 4. But it is not possible to accommodate both airplanes 2 and 3.
It is possible that different planes plan to arrive or depart the parking lot at the same time. Jack has the best crews working with him, so that they will manage to arrange the plane to the parking lot in the best way that if it is possible to park and take out the planes they will be able to do it. Consider another example.
Although airplane 5 and 6 arrive at the same time, Jack's crews know that airplane 5 will have to be out before airplane 6, so when both airplanes arrive they put airplane 6 in first, following by airplane 5.
Given a list of parking requests, you want to find the maximum number of airplanes that can be parked in this parking lot, provided that they can only depart in the Last-In First-Out fashion.
Input
The first line contains an integer T, the number of test cases (1 < T < 5). Each test case is in the following format.
The first line starts with an integer N (1 < N < 300) denoting the number of airplanes. The next N lines describe the request table. Each line 1 + i, for 1 < i < N, contains two integer Si and Ti , (0 < Si < Ti < 1,000,000,000) which are the planned arrival time and planned departing time for airplane i.
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It is 2050 and human live with alien. There are two kind of alien: good alien and evil alien. Good alien were our friend because they help us to develop good technology for our earth. Evil alien were very very bad, they develop heavy and dangerous weapons that can destroy earth. Alien were very hard to kill because of their ultra regeneration skill. Luckily, we have developed a kind of bomb that can kill alien in an instant. This weapon is very expensive so we must use it wisely.
Given a map of 10 × 10, each element in the map will be:
- '.' represents empty region.
- 'g' represents good alien.
- 'e' represents evil alien.
Calculate how many evil alien that can be killed without killing any good alien, and how many bombs we need to do that. A bomb has a 3 × 3 area of effect, so all of the 8 adjacent neighbors will also be destroyed. You can put bomb anywhere in the map, even if there is an alien in that cell. For example,
e..
.Xe
..e
Bombing at X will kill three evil aliens.
Our spy has reported that the number of alien groups from each side is less than 16.
Input
First line in the input will be T (1 ≤ T ≤ 100) number of cases. Each case will have a map of 10 × 10 represent the city. Between each city will be separated by a blank line.
Output
For each case, output two numbers: a and b, where a is the maximum number of evil aliens that you can kill and b is the minimum number of bombs you need to do that.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
2M scientists are supposed to present papers in a conference in a day. The day is divided into 2 slots, the morning slot and the evening slot. M scientists present their paper in the morning slot and the remaining in the evening slot. Both slots are separated by a lunch break.
Some scientists depend on a paper from some other scientists to be presented before theirs. So if Scientist A is presenting a paper on "Graph Theory" and Scientist B on "Max flow-Min cut", then A has to present before B. Lunch break is a time of merry making and partying, so attendees tend to forget the papers in the previous half. Due to this, the dependent scientist (B in this case) has to present the paper in the same slot as the scientist on whom he is dependent (A in this case). Given the dependencies, find the number of possible orderings of presenting the papers.
Input
The first line of input will contain an integer T ≤ 20 denoting the number of test cases. Each test case will be formatted as follows: The first line will contain an integer denoting 1 ≤ M ≤ 8. The next 2M lines will contain 2M characters each. Each character will either be ‘Y’ or ‘N’. If the i th line's j th character is ‘Y’ it means that scientist i is dependent on scientist j. ‘N’ signifies no dependence. A scientist will never be dependent on himself.
Output
Output one line per case that contains an integer denoting the number of possible ordering of scientists.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the middle of Tyrrhenian Sea, there is a small volcanic island called Chronus. The island is now uninhabited but it used to be a civilized island. Some historical records imply that the island was annihilated by an eruption of a volcano about 800 years ago and that most of the people in the island were killed by pyroclastic flows caused by the volcanic activity. In 2003, a European team of archaeologists launched an excavation project in Chronus Island. Since then, the project has provided many significant historic insights. In particular the discovery made in the summer of 2008 astonished the world: the project team excavated several mechanical watches worn by the victims of the disaster. This indicates that people in Chronus Island had such a highly advanced manufacturing technology.
Shortly after the excavation of the watches, archaeologists in the team tried to identify what time of the day the disaster happened, but it was not successful due to several diffculties. First, the extraordinary heat of pyroclastic flows severely damaged the watches and took away the letters and numbers printed on them. Second, every watch has a perfect round form and one cannot tell where the top of the watch is. Lastly, though every watch has three hands, they have a completely identical look and therefore one cannot tell which is the hour, the minute, or the second (It is a mystery how the people in Chronus Island were distinguishing the three hands. Some archaeologists guess that the hands might be painted with different colors, but this is only a hypothesis, as the paint was lost by the heat). This means that we cannot decide the time indicated by a watch uniquely; there can be a number of candidates. We have to consider different rotations of the watch. Furthermore, since there are several possible interpretations of hands, we have also to consider all the permutations of hands.
You are an information archaeologist invited to the project team and are asked to induce the most plausible time interval within which the disaster happened, from the set of excavated watches.
In what follows, we express a time modulo 12 hours. We write a time by the notation hh : mm : ss , where hh , mm , and ss stand for the hour (hh = 00, 01, 02,..., 11) , the minute (mm = 00, 01, 02,..., 59) , and the second (ss = 00, 01, 02,..., 59) , respectively. The time starts from 00:00:00 and counts up every second 00:00:00, 00:00:01, 00:00:02, ... , but it reverts to 00:00:00 every 12 hours.
The watches in Chronus Island obey the following conventions of modern analog watches.
A watch has three hands, i.e. the hour hand, the minute hand, and the second hand, though they look identical as mentioned above.
Every hand ticks 6 degrees clockwise in a discrete manner. That is, no hand stays between ticks, and each hand returns to the same position every 60 ticks.
The second hand ticks every second.
The minute hand ticks every 60 seconds.
The hour hand ticks every 12 minutes.
At the time 00:00:00, all the three hands are located at the same position.
Because people in Chronus Island were reasonably keen to keep their watches correct and pyroclastic flows spread over the island quite rapidly, it can be assumed that all the watches were stopped in a short interval of time. Therefore it is highly expected that the time the disaster happened is in the shortest time interval within which all the excavated watches have at least one candidate time.
You must calculate the shortest time interval and report it to the project team.
Input
The input consists of multiple datasets, each of which is formatted as follows.
n
s1 t1 u1
s2 t2 u2
...
sn tn un
The first line contains a single integer n (2<=n<=10) , representing the number of the watches. The three numbers si , ti , ui in each line are integers such that 0 <= si, ti, ui <= 59 and they specify the positions of the three hands by the number of ticks relative to an arbitrarily chosen position.
Note that the positions of the hands of a watch can be expressed in many different ways. For example, if a watch was stopped at the time 11:55:03, the positions of hands can be expressed differently by rotating the watch arbitrarily (e.g. 59 55 3, 0 56 4, 1 57 5, etc.) and as well by permuting the hour, minute, and second hands arbitrarily (e.g. 55 59 3, 55 3 59, 3 55 59, etc.).
The end of the input is indicated by a line containing a single zero.
Output
For each dataset, output the shortest time interval within which all the watches given in the dataset have at least one candidate time. The output must be written in a single line in the following format for each dataset.
hh:mm:ss h'h':m'm':s's'
Each line contains a pair of times hh:mm:ss and h'h':m'm':s's' , indicating that the shortest interval begins at hh:mm:ss and ends at h'h':m'm':s's' inclusive. The beginning time and the ending time are separated by a single space and each of them should consist of hour, minute, and second in two digits separated by colons. No extra characters should appear in the output.
In calculating the shortest interval, you can exploit the facts that every watch has at least one candidate time and that the shortest time interval contains 00:00:00 only if the interval starts from 00:00:00 (i.e. the shortest interval terminates before the time reverts to 00:00:00).
If there is more than one time interval that gives the shortest, output the one that first comes after 00:00:00 inclusive.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Wen Chen is the captain of a rescue boat. One of his important tasks is to visit a group of islands once a day to check if everything is all right. Captain Wen starts from the west-most island, makes a pass to the east-most island visiting some of the islands, then makes a second pass from the east-most island back to the first one visiting the remaining islands. In each pass Captain Wen moves steadily east (in the first pass) or west (in the second pass), but moves as far north or south as he needs to reach the islands. The only complication is that there are two special islands where Wen gets fuel for his boat, so he must visit them in separate passes. Figure 7 shows the two special islands in pink (1 and 3) and one possible path Captain Wen could take.
Calculate the length of the shortest path to visit all the islands in two passes when each island's location and the identification of the two special islands are given.
Input
The input consists of multiple test cases. The data for each case begins with a line containing 3 integers n (4 ≤ n ≤ 100), b1, and b2 (0 < b1, b2 < n - 1 and b1 ≠ b2), where n is the number of islands (numbered 0 to n - 1) and b1 and b2 are the two special islands. Following this, there are n lines containing the integer x - and y -coordinates of each island (0 ≤ x, y ≤ 2000), starting with island 0. No two islands have the same x -coordinate and they are in order from west-most to east-most (that is, minimum x -coordinate to maximum x -coordinate).
Input for the last case is followed by a line containing 3 zeroes.
Output
For each case, display two lines. The first line contains the case number and the length of the shortest tour Captain Wen can take to visit all the islands, rounded and displayed to the nearest hundredth. The second line contains a space-separated list of the islands in the order that they should be visited, starting with island 0 and 1, and ending with island 0. Each test case will have a unique solution. Follow the format in the sample output.