| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1132 | The Party, Part I |
|
| 1136 | Audiophobia |
|
| 1140 | The Sultan's Successors |
|
| 1144 | Colour Hash |
|
Description
[[Category: BFS]]
Don Giovanni likes to dance--especially with girls! And everyone else in the party enjoyed the dance, too. Getting a chance to dance with the host (that is Don Giovanni) is the greatest honour; failing that, dancing with someone who has danced with the host or will dance with the host is the second greatest honour. This can go further. Define the Giovanni number of a person as follows, at the time after the party is over and therefore who has danced with whom is completely known and fixed:
- No one has a negative Giovanni number.
- The Giovanni number of Don Giovanni is 0.
- If a person p is not Don Giovanni himself, and has danced with someone with Giovanni number n, and has not danced with anyone with a Giovanni number smaller than n, then p has Giovanni number n + 1.
- If a person's Giovanni number cannot be determined from the above rules (he/she has not danced with anyone with a finite Giovanni number), his/her Giovanni number is ∞.
Your job is to write a program to compute Giovanni numbers.
Input
The input begins with a single positive integer k ≤ 100 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.
The first line has two numbers P and D; this means there are P persons in the party (including Don Giovanni) and D dancing couples (2 ≤ P ≤ 105 and 0 ≤ D ≤ 106) Then D lines follow, each containing two distinct persons, meaning the two persons has danced. Persons are represented by numbers between 0 and P-1; Don Giovanni is represented by 0.
Output
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 P-1 lines. Line i is the Giovanni number of person i, for 1 ≤ i ≤ P-1. If the Giovanni number is ∞, print ``INF". Note that it is P-1 because we skip Don Giovanni in the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[[Category: All-Pairs Shortest Path]]
(Hint: Transitive Closure)
Consider yourself lucky! Consider yourself lucky to be still breathing and having fun participating in this contest. But we apprehend that many of your descendants may not have this luxury. For, as you know, we are the dwellers of one of the most polluted cities on earth. Pollution is everywhere, both in the environment and in society and our lack of consciousness is simply aggravating the situation.
However, for the time being, we will consider only one type of pollution - the sound pollution. The loudness or intensity level of sound is usually measured in decibels and sound having intensity level 130 decibels or higher is considered painful. The intensity level of normal conversation is 60-65 decibels and that of heavy traffic is 70-80 decibels.
Consider the following city map where the edges refer to streets and the nodes refer to crossings. The integer on each edge is the average intensity level of sound (in decibels) in the corresponding street.
To get from crossing A to crossing G you may follow the following path: A-C-F-G. In that case you must be capable of tolerating sound intensity as high as 140 decibels. For the paths A-B-E-G, A-B-D-G and A-C-F-D-G you must tolerate respectively 90, 120 and 80 decibels of sound intensity. There are other paths, too. However, it is clear that A-C-F-D-G is the most comfortable path since it does not demand you to tolerate more than 80 decibels.
In this problem, given a city map you are required to determine the minimum sound intensity level you must be able to tolerate in order to get from a given crossing to another.
Input
The input may contains at most 100 test cases.
The first line of each test case contains three integers C(2 ≤ C ≤ 100), S(0 ≤ S ≤ 104) and Q(1 ≤ Q ≤ 104) where C indicates the number of crossings (crossings are numbered using distinct integers ranging from 1 to C), S represents the number of streets and Q is the number of queries.
Each of the next S lines contains three integers: c1, c2 and d(0 ≤ d ≤ 108) indicating that the average sound intensity level on the street connecting the crossings c1 and c2 (c1 ≠ c2) is d decibels. The streets are bidirectional and you can assume that there is no two lines describing the same street in these S lines.
Each of the next Q lines contains two integers c1 and c2 (c1 ≠ c2) asking for the minimum sound intensity level you must be able to tolerate in order to get from crossing c1 to crossing c2.
The input will terminate with three zeros form C, S and Q.
Output
For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then for each query in the input print a line giving the minimum sound intensity level (in decibels) you must be able to tolerate in order to get from the first to the second crossing in the query. If there exists no path between them just print the line ``no path".
Print a blank line between two consecutive test cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[[Category: Branch and Bound]]
The Sultan of Nubia has no children, so she has decided that the country will be split into up to k separate parts on her death and each part will be inherited by whoever performs best at some test. It is possible for any individual to inherit more than one or indeed all of the portions. To ensure that only highly intelligent people eventually become her successors, the Sultan has devised an ingenious test. In a large hall filled with the splash of fountains and the delicate scent of incense have been placed k chessboards. (A chessboard has eight rows and eight columns.) Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens on the chessboard in such a way that no queen threatens another one, and so that the numbers on the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one. It is known that the number of valid placements of the 8 queens on the chessboard is less than 100.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player and a good mathematician and you suspect that her score is the best attainable.)
Input
Input will consist of k (the number of boards), on a line by itself, followed by k sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a positive integer less than 100. There will never be more than 105 boards .
Output
Output will consist of k numbers consisting of your k scores, each score on a line by itself and right justified in a field 5 characters wide.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[[Category: 2-Way BFS]]
This puzzle consists of two wheels. Both wheels can rotate both clock and counter-clockwise. They contain 21 coloured pieces, 10 of which are rounded triangles and 11 of which are separators. Figure 1 shows the final position of each one of the pieces. Note that to perform a one step rotation you must turn the wheel until you have advanced a triangle and a separator.
Figure 1. Final puzzle configuration
Your job is to write a program that reads the puzzle configuration and prints the minimum sequence of movements required to reach the final position. We will use the following integer values to encode each type of piece:
- 0 grey separator
- 1 yellow triangle
- 2 yellow separator
- 3 cyan triangle
- 4 cyan separator
- 5 violet triangle
- 6 violet separator
- 7 green triangle
- 8 green separator
- 9 red triangle
- 10 red separator
A puzzle configuration will be described using 24 integers, the first 12 to describe the left wheel configuration and the last 12 for the right wheel. The first integer represents the bottom right separator of the left wheel and the next eleven integers describe the left wheel clockwise. The thirteenth integer represents the bottom left separator of right wheel and the next eleven integers describe the right wheel counter-clockwise.
The final position is therefore encoded like:
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
If for instance we rotate the left wheel clockwise one position from the final configuration (as shown in Figure 2) the puzzle configuration would be encoded like:
2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1
Figure 2. The puzzle after rotating the left wheel on step clockwise from the final configuration.
Input
Input for your program consists of at most 50 puzzles. The first line of the input will contain an integer n specifying the number of puzzles. There will then be n lines each containing 24 integers separated with one white space, describing the initial puzzle configuration as explained above.
Output
For each configuration your program should output one line with just one number representing the solution. Each movement is encoded using one digit from 1 to 4 in the following way:
- 1 Left Wheel Clockwise rotation
- 2 Right Wheel Clockwise rotation
- 3 Left Wheel Counter-Clockwise rotation
- 4 Right Wheel Counter-Clockwise rotation
No space should be printed between each digit. Since multiple solutions could be found, you should print the solution that is encoded as the smallest number. The solution will never require more than 16 movements.
If no solution is found you should print ``NO SOLUTION WAS FOUND IN 16 STEPS". If you are given the final position you should print ``PUZZLE ALREADY SOLVED".