| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 6031 | Paper Presentation |
|
| 6032 | The Sky is the Limit |
|
| 6033 | Key Task |
|
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
The city of Banff hired an advertising agency to promote the city's attractions to potential visitors. One of the planned slogans stated that the mountain ranges around the city form the most beautiful skyline in Canada. But the Institute for Consumer Protection in Canada (ICPC) decided that ``the most beautiful skyline" was a subjective and unverifiable claim, and could therefore be considered misleading.
The advertising agency then came up with the slogan ``Banff - the longest skyline in Canada." Although not as catchy, it is hopefully verifiable, and therefore admissible under Canada's tricky advertising laws.
This is where you come in. What the advertising agency needs is a program that determines the length of a skyline. Consider each mountain as a two-dimensional triangle having two upper sides the same length. A skyline is the outline of one or more mountains. The skyline's length is the total length of the outline. The left illustration below shows three mountains. The right illustration shows (with bold lines) the skyline and (with dashed lines) the portion of the mountains' upper edges that are not part of the skyline. Note that parts of the horizon line that lie between mountains are not considered part of the skyline.
Input
Each input file contains one or more test cases, which are descriptions of mountain ranges. Each description starts with a line containing a positive integer N , which specifies the number of mountains in the range. Each of the next N lines describes a mountain with three integers X , H , and B , which specify the horizontal position of the mountain's peak relative to some fixed point, the height of the peak, and the width of the base of the mountain, respectively. The base of each mountain coincides with a horizontal line. The values satisfy the conditions N ≤ 100 , H > 0 , and B > 0 .
The last test case is followed by a line containing a zero.
Output
For each test case, print the case number (beginning with 1) and the length of the skyline. Print the length rounded to the nearest integer, with 0.5 rounded up. Print a blank line after the output of each test case. Use the format shown in the sample output below.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Czech Technical University is rather old -- you already know that it celebrates 300 years of its existence in 2007. Some of the university buildings are old as well. And the navigation in old buildings can sometimes be a little bit tricky, because of strange long corridors that fork and join at absolutely unexpected places.
The result is that some first-graders have often diffculties finding the right way to their classes. Therefore, the Student Union has developed a computer game to help the students to practice their orientation skills. The goal of the game is to find the way out of a labyrinth. Your task is to write a verification software that solves this game.
The labyrinth is a 2-dimensional grid of squares, each square is either free or filled with a wall. Some of the free squares may contain doors or keys. There are four different types of keys and doors: blue, yellow, red, and green. Each key can open only doors of the same color.
You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls and you cannot leave the labyrinth area. If a square contains a door, you may go there only if you have stepped on a square with an appropriate key before.
Input
The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 100) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:
| Character | Meaning | |
| Hash mark | # | Wall |
| Dot | . | Free square |
| Asterisk | * | Your position |
| Uppercase letter | B Y R G | Blue, yellow, red, or green door |
| Lowercase letter | b y r g | Blue, yellow, red, or green key |
| Uppercase X | X | Exit |
- more than one exit,
- no exit at all,
- more doors and/or keys of the same color, and
- keys without corresponding doors and vice versa.
Note that it is allowed to have
You may assume that the marker of your position (``*") will appear exactly once in every map. 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 possible in S steps.", where S is the smallest possible number of step to reach any of the exits. If no exit can be reached, output the string ``The poor student is trapped!" instead. One step is defined as a movement between two adjacent cells. Grabbing a key or unlocking a door does not count as a step.