Dear problem solvers,
Again we have prepared new problems for you. The deadline is October 23, 2000.
In a village called Nalomena Trieska they organize a tournament in their traditional ball game annually. This year more teams than ever registered for the tournament. Each team played one match against every other team. The organizers kept record of winning team for each match, but they forgot to keep also the score of matches. In each match one team wins and the other team loses (no tie) and there is a score indicating how much better was the winning team. Kleofas, the chair of the organizing team, tried to figure out how to resolve possible ties between teams with the same number of winning matches without having scores of the matches. His friend Zacharias found a solution: "We have never announced the rules for producing the final ranking of the teams. Maybe we can just order all the teams so that each team lost the match with the team that is one rank better in the ranking. In this way nobody can claim a better ranking and everything will be O.K." The organizers were very happy with this solution until they found out it is not easy to find such a ranking of the teams.
Array Res[1..N,1..N] contains results of the tournament where Res[i,j]=1 if team i won over the team j and otherwise Res[i,j]=0. Write a program which outputs one possible order of all teams d1,...,dN such that for all i, 1 <= i < N team di won over the team di+1. If there is no such order of the teams your program should output string "Bad luck".
Input
0 0 1 1 0 1 0 0 0
Output
2,1,3
Top Secret Scientific Laboratory (TSSL) is one of the greatest centers of scientific research. However, even TSSL has not invented a money-tree yet. Therefore the management had to agree with a secret operation DSE (Dismissals of Superfluous Employees). This time, scientists fell victims to DSE.
Until now each scientist worked on exactly one project. That, of course, is not very wise because some of the scientists could work on several projects simultaneously and other scientists could be fired. However there is a catch. Even the best scientists are only human and cannot be overloaded with many projects (each project takes a LOT of time). According to TSSL internal rule No. 355/113 the length of the working time of each scientist is limited. Furthermore because of safety and secrecy no scientist can work on more than two projects (in case that he/she reveals the secret to an enemy).
You are given N – the number of employed scientists before operation DSE, and M – the maximal length of their working time. Furthermore each of N projects has its given time-length. The lengths of projects are given in decreasing order. Write a program to compute the maximum number of scientists who can be fired according to the TSSL internal rules. The program should output any distribution of projects to the remaining (not fired) scientists.
Input
N=6 M=50 Projects: 44 29 26 25 10 8
Output
Scientist #1: 6,2 Scientist #2: 5,3 Scientist #3: 4 Scientist #4: 1 Other (2) scientists can be fired.
There may be more correct outputs.
A dangerous internationally active criminal, Gill Bates, has been arrested, at last, and sent where he belongs - in a strictly guarded prison on the island of Alcatraz. Everybody was relieved. So were even his companions, hoping for some rest after years of hard work. Nevertheless, their joy did not last long, as they found out that they had forgotten the combination of the lock of Gill's safe where all their common wealth was stored. Therefore, they decided to help Gill escape.
Gill's companions sailed to the island closest to the Alcatraz. In order to rescue their boss, they decided to dig a tunnel to connect their island to the Alcatraz. Since they are not too industrious, they want the tunnel to be the shortest possible. Now, they sit over the map of the two islands and try to figure out how to dig the tunnel. However, this task is beyond their abilities, so they will need some help from you.
Two integers N and M are given as well as N-gon representing the Alcatraz and M-gon representing the island where Gill's companions are. Both polygons are specified by coordinates of their vertices clockwise. They needn't be convex nor disjoint. Write a program which computes the minimum length of a tunnel connecting the two islands (i.e. the length of a shortest line segment with one endpoint in the first polygon and the other endpoint in the second polygon).
Input 1
N=5 M=3 (1,1), (3,1), (2,2), (3,3), (1,3) (3,2), (4,3), (4,1)
Output 1
The length of the shortest tunnel is 0.707.
Input 2
N=4 M=4 (1,0), (2,1), (1,2), (0,1) (2,0), (3,1), (2,2), (1,1)
Output 2
The length of the shortest tunnel is 0.
The citizens of Stuchanice pri Koryte decided to build a hen farm. They bought a few hens, and after only a few days, they were able to collect the first eggs. People from the whole village gathered: "Look! How nice eggs!" "These eggs are certainly the most beautiful eggs in the country!" "Not only most beautiful, but also the best!" "And certainly the most solid ones.." noted Mr. Zavis, who was in a bad mood today.
"Yes, the most solid eggs!" shouted the villagers, but then hesitated. It is easy to see that they are beautiful by simply looking at them. But how do we find out whether are they solid? "It's easy," Mr. Zavis informed them. "The solidity of an egg is the largest height in centimeters, from which the egg can survive a fall without breaking". The villagers took all the eggs they had and started to measure. Gejza took an egg, lifted it to height N centimetres, released it, and the egg after a short fall crashed to the ground and broke into small pieces.
Write a program that reads a height N from which the egg certainly breaks if released and the number of available eggs M. Then it will repeatedly print a message "Drop an egg from height h" and request a response from the user whether the egg broke or not. The villagers are very impatient and eager to know the solidity of their eggs. Thus your program should determine it (assume that the solidity is an integer number) by using the minimal (in the worst case) possible number of egg releases. It doesn't matter how many eggs break during the experiment (if an egg doesn't break, it is possible to reuse it), but your program must know the answer after the last egg breaks.
N=10 M=2 Drop an egg from height 1 cm > The egg didn't break Drop an egg from height 3 cm > The egg didn't break Drop an egg from height 5 cm > The egg broke Drop an egg from height 4 cm > The egg didn't break The solidity of the eggs is 4 cm. (We needed to drop an egg 4 times to determine the solidity.)
Give reasons why your program always determines the solidity correctly. Try to estimate how many times it needs to drop an egg to determine the solidity in the worst case for given M and N.
Gold miner Santo decided one day that he is too old for his current occupation and he established an amusement park for gold miners called Santoland.
The greatest attraction of Santoland is a labyrinth called Cave of Rum. The cave consists of N chambers numbered 1 to N. The chambers are connected by numerous narrow tunnels. Each tunnel is one-way only (the direction is indicated by an arrow at the beginning of the tunnel). Each tunnel is also labeled by one letter of the alphabet inscribed at its beginning (Santo wanted to show his friends that he is not illiterate any more). Finally there is a bottle of rum hidden in some of the chambers.
As soon as the Cave of Rum was finished the first visitors arrived. Santo gave each visitor a small piece of paper with a sequence of letters and he announced the following rules for using the cave:
You can enter the cave and walk in it as you wish. But if you want to win a bottle of rum you need to perform a trip obeying the following rules:
Gold miners have taken their sequences and entered the cave to search for hidden rum. After several hours of wandering they discovered it is not easy to find the rum. The problem is that in some chambers there are several tunnels labeled with the same letter and it is not clear which of them should be used. The gold miners suspect that Santo gave them sequences that cannot be used to find any rum. First of all they want to make sure this is true and they need your help.
Input consists of the number of chambers N, the list of the tunnels (each tunnel is given by the numbers of the start and end chambers and by the letter inscribed at its beginning), the list of chambers containing rum, and the sequence of letter given by Santo. Your program should decide whether it is possible to get to some chamber containing rum obeying Santo's rules (i.e. a trip starts in chamber 1 and uses the tunnels labeled with letters in the sequence in the order as they appear in the sequence). The trip can contain some chambers more than once. It is not important whether the trip passes through some chambers with rum; the question is whether it ends in a chamber with rum.
Input
N = 4 Tunnels: 1 3 a 1 4 b 2 1 a 2 3 a 3 4 b 4 2 b 4 3 a Chambers with rum: 2, 4 Sequence: abbababb
Output
Rum can be found.
(One possible trip: 1, 3, 4, 2, 3, 4, 3, 4, 2. Other possibility: 1, 3, 4, 2, 1, 4, 3, 4, 2).