Department of Computer Science, CTU FEE & Czech ACM Chapter
CTU FEE Local Programming Contest 1998
PSOS Political Party
Several new political parties have appered in our country due to the next election to come. PSOS (Programmers for Stable Operating Systems) are one of that parties. They are going to attract people not only with their promises. The main point of Election Programme can be easily found from the name of the Party. But it would be very incorrect, if someone should say it is the only point.
PSOS want to get as many votes as possible, of course. Because of that they decided to use computers during the campaign. They have bought the very fast computer which has been optimized for computations during the election campaign. The main problem is with the software. Because of strict security requirements, none of the large (and known) companies could be contacted. That is the main reason that you are to write all the required software. Your goal is to create a set of programs that help PSOS to win the election.
We wish you good luck with your mission.
Metric Time (Metricky cas)
(file name: cas.c, cas.p, cas.C)
The Metric Time is one of the most important points of PSOS Election Programme. The Time can be much easier calculated in operating systems. These systems are then more stable, which meets the main goal of the Party.
The length of one day is the same as with the "classic" time. The day is divided into 10 metric hours, each of them into 100 metric minutes, and each minute into 100 metric seconds. 10 metric days form one metric week, 10 metric weeks give one metric month, 10 metric months are called metric year. It is obvious this Metric Time is much better than the classic one.
Some opponent parties often complain that the Metric Time has also some drawbacks. First of all, it would be very difficult to change to the new time. PSOS Chairman decided to solve these problems all at once. He plans to publish a freeware utility which will be able to convert between the time formats. Your goal is to write one half of this utility, the program which converts classic time to Metric Time. Metric hours, metric minutes, and metric seconds are counted starting with zero, as usual. Metric days and metric months start with one. There exist metric year zero. The metric seconds should be rounded to the nearest smaller integer value. Assume that 0:0:0 1.1.2000 classic time is equal to 0:0:0 1.1.0 Metric Time.
Note that the classic year is leap, if it is an integer multiple of 4. The only exception are years divisible by 100 - they are leap only if they are an integer multiple of 400. For example, leap years are 1996, 2400, and 2000; leap years are not 1900, 2300, 2002.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of exactly one line in the form "hour:minute:second day.month.year" which is the date in the classic form (usual in most of European countries). The date is always valid, 2000 <= year <= 50000.
The program must print exactly one line for each assignment. The line should have the form "mhour:mmin:msec mday.mmonth.myear" which is the Metric Time equal to the specified classic time.
7 0:0:0 1.1.2000 10:10:10 1.3.2001 0:12:13 1.3.2400 23:59:59 31.12.2001 0:0:1 20.7.7478 0:20:20 21.7.7478 15:54:44 2.10.20749
Output for Sample Input
0:0:0 1.1.0 4:23:72 26.5.0 0:8:48 58.2.146 9:99:98 31.8.0 0:0:1 100.10.2000 0:14:12 1.1.2001 6:63:0 7.3.6848
(file name: foto.c, foto.p, foto.C)
The election campaign just started, so PSOS decided to make some propagation. One of the representatives came with a great idea - he proposes to make an photography of their Parliament Club. Unfortunatelly, even after many briefings, the representatives are still not able to agree upon an ordering of people in the photography. Moreover, there are a lot of representatives and it is not possible to have all of them in a single picture. The situation became critical. In the end, the representatives decided they will make one photo of every possible combination of people and their ordering. Different photographs will be used for a large number of billboards PSOS plan to use. To make things more clear, every person gets a Unique Identification Number (UIN). Every picture can be then described as the succession of several UINs x1, x2, ... xk, in whichxi is UIN of the i-th person in the picture x. Now we can sort all the possible photographs (combinations) to a single succession. The ordering of combinations of the same length (photographs with the same number of people in it) is defined as follows: the combination p is greater than the combination q if there exists any i such as that pj = qj for every j < i, and pi > qi. Your goal is to find the right place for a given picture among all possible photographs.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of exactly two lines. At the first line of each assignment, there are two integers n and k, 1 <= k <= n <= 12 stating the total number of representatives (n) and the number of them which can fit into a single picture (k). At the second line of the assignment, there is exactly k positive numbers x1, x2, ... xk, each of them 1 <= xi <= n. No number can appear more than once on this line.
For each assignment, output the text "Variace cislo I ma poradove cislo J." (Combination #I is J-th in sequence). Fill the number of assignment instead of I (starting with one), and the number of the given photograph among all possible combinations after ordering, instead of J (also starting with one).
4 1 1 1 5 1 4 3 3 1 2 3 5 3 5 3 1
Output for Sample Input
Variace cislo 1 ma poradove cislo 1. Variace cislo 2 ma poradove cislo 4. Variace cislo 3 ma poradove cislo 1. Variace cislo 4 ma poradove cislo 55.
(file name: jeskyne.c, jeskyne.p, jeskyne.C)
A large system of caverns was discovered some time ago. PSOS know about it and they promised to make these caverns accessible for tourists. PSOS think it could add some more votes for the Party.
Unfortunatelly, there is a big problem. The members did not notice that the caverns are completely flooded by water. Because PSOS want to be modest and they do not want to break their promises, they started to think about the solution in case they really would win the election. One of the most interesting proposals involved even little submarines. But it seems as the best solution, to exhaust the water out of the cavern. The caverns are very well examined, that means it is exactly known where the water is. PSOS would like to know how much water they have to pump out, so they need a computer program that will be able to determine this.
All the cavern space consists of equal cubes, their size is 1 meter. Obviously, it is possible to exhaust water from a continous space only, e.g. the space consisting of neighbouring cubes. Moreover, only the space running to the top layer of cubes may be exhausted. Two cubes are considered neighbouring if they have one common side, not only the edge.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment begins with three integer numbers X, Y, Z on a single line, separated by spaces. 1 <= X,Y,Z <= 100. All the flooded cubes are inside a box with the size X, Y, and Z meters. All cubes outside this box are filled with rock. After the first line, the description of Z layers follows, starting from the top one. Each layer begins with a line with a single integer number P that denotes the number of flooded cubes in that layer. Then P lines follow, each of them consisting of two integer numbers R and S, 1 <= R <= X, 1 <= S <= Y. These number are coordinates of one flooded cube, given in meters.
Output a single line for each assignment. The line must contain the sentence "Je nutne vycerpat X litru vody." (X litres of water must be exhausted). Fill the right ammount of litres of water, instead of X. It should include all the water that is accessible from the top layer of the cavern.
2 4 4 5 1 3 3 2 1 2 3 3 4 1 2 2 2 2 3 3 3 2 3 3 1 1 0 3 7 2 1 2 4 5 1 4 2 3 2 4 2 5 3 4
Output for Sample Input
Je nutne vycerpat 8000 litru vody. Je nutne vycerpat 6000 litru vody.
(file name: kod.c, kod.p, kod.C)
The important thing is also the fact, where the representatives sit in the Parliament. Some of them prefer front rows because of more light, some prefer back rows because of less light and more silence. The others want to sit by the window. Moreover, the sitting order must be kept absolutely secret, because the neighbouring representatives may influence each other. Since we do not want to have corruption in the Parliament, it was decided to use Hyper-secret Code to encrypt the numbers of seats. The Hyper-secret Code of length n is designated SK(n) and consists of all possible binary strings of length n. That means it always has 2n elements. The Code is generated using the following recursive algorithm:
Every seat in the Parliament has its own number. The numbers make a continuos succession beginning with one. The Hyper-secret Code SK(n) is generated (using the above algorithm) for greater and greater n, until the length of the Code (the number of binary strings that form the succession) is greater or equal to the highest number of seat. Every seat s is then given the binary string that appears at the s-th possition in the succession SK(n). Every representative then gets the Code of his seat and nobody can determine who is going to be his neighbour.
But the problem appears when the representative enters the Parliament, takes the paper with his Code and finds his seat. To solve this, the Chairman of the Parliament wants the computer program that will be able to convert any Hyper-secret Code to the appropriate number of a seat. You propably guess that you are to write this program.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of two lines. The first line contains an integer number k, 1 <= k <= 30. At the second line, there is the Hyper-secret Code consisting of exactly k characters. Each of the characters is either 0 or 1.
The program should print the line for each assignment. The line must contain the sentence "Poslanec P se posadi na sedadlo cislo S." (The representative #P sits down at the seat S). Fill the number of the assignment (starting with one) instead of P, and the right number of a seat instead of S - it means the possition of the given string in the Code SK(k).
5 1 0 4 0000 4 1000 4 1111 8 10101010
Output for Sample Input
Poslanec 1 se posadi na sedadlo cislo 1. Poslanec 2 se posadi na sedadlo cislo 1. Poslanec 3 se posadi na sedadlo cislo 16. Poslanec 4 se posadi na sedadlo cislo 11. Poslanec 5 se posadi na sedadlo cislo 205.
(file name: okrsky.c, okrsky.p, okrsky.C)
The new election system was introduced in our republic. The system is based on a majority of votes in regions. The republic is divided into M regions, each of them means exactly one seat in the Parliament.
The Chairman of PSOS would like to know how many voters makes the certainty that PSOS win the election. To win the election means to get more than one half of Parliament seats. We do not know the exact number of political Parties participating in election but we can determine the number of voters in every region. We can assume that all voters will participate in election and each of them will give his/her vote to one of the candidates. PSOS have their candidates in all regions. At least one another party has its candidate in each of the regions. You are to determine the minimum number of votes which ensures the landslide of PSOS, even in the worst possible case.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of two lines. The first line contains an integer number M stating the number of regions. At the second line, there are exactly M numbers separated by spaces. These numbers state the number of voters in each of the regions. All the number are possitive and less or equal to 100000.
Print a single line for each assignment. The line must contain the sentence "H hlasu zajisti strane vitezstvi." (H votes ensures the win of Party). Instead of H, fill the minimum number of votes which ensures the win.
3 10 340 260 180 15 1 20 40 90 78 34 2 12 1 6 1 2 3 4 5 6
Output for Sample Input
1003 hlasu zajisti strane vitezstvi. 13 hlasu zajisti strane vitezstvi. 18 hlasu zajisti strane vitezstvi.
(file name: parlament.c, parlament.p, parlament.C)
The representatives have to spend a lot of time in the Parliament. That is why PSOS want to choose their seats to have the best ones. The special committee was formed to check all the seats and give a score to each of them. The more attractive the seat is, the higher is its score. The score involves the upholstering of chairs, the position of cameras that could take picture of sleeping representative, e.t.c. It was not easy, but finally, after many months, the committee put a score to each seat. Unfortunatelly, it is not possible to take all the best seats. There is also a Security Committee that decided the representatives must sit all together, in a rectangular shape. Moreover, the election is still not over and PSOS do not know how many seats they are going to get. The Party needs a program that will read the score of each seat and then it will be able to determine the total score of any rectangular area.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment begins with a line consisting of two integers R and S, separated by space. R is the number of rows in the Parliament, S is the number of seats in every row (all rows are of the same size). It is known that no Parliament can have more than 1000 rows, nor more than 1000 seats in a row. Then R lines follow. Each of them describes one row of the Parliament, in sequence starting with the first one. Each line contains exactly S numbers separated by spaces. These numbers are score values of each seat in the given row, in sequence starting with the first one. The total score of all seats in the Parliament will always fit into the standard int or integer type.
Then the line containing the single integer number D follows. It is the number of queries. Then D lines follow, each specifying a single query. The query consists of four coordinates separated by spaces, R1, S1, R2, S2 (in that order), 1 <= R1 <= R2 <= R <= 1000, 1 <= S1 <= S2 <= S <= 1000. The coordinates designate that representatives are sitting at the seats forming a rectangle. The seats are in rows from R1 to R2 (including them) and in each of these row the seats from S1 to S2 (including them) are occupied.
Output a single line for each query. The line must contain the sentence "Absolutni hodnota pohodlnosti je X bodu." (The total score is X points). Fill the total score instead of X. The total score is a sum of score values of each seat occupied by PSOS Party. Print one empty line after each assignment (including the last one).
2 10 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 5 1 1 1 1 2 2 2 2 1 1 10 10 9 9 10 10 2 2 9 9 1 1 1 1 1 1 1 1
Output for Sample Input
Absolutni hodnota pohodlnosti je 1 bodu. Absolutni hodnota pohodlnosti je 2 bodu. Absolutni hodnota pohodlnosti je 550 bodu. Absolutni hodnota pohodlnosti je 38 bodu. Absolutni hodnota pohodlnosti je 352 bodu. Absolutni hodnota pohodlnosti je 1 bodu.
(file name: ruleta.c, ruleta.p, ruleta.C)
The political Party needs some money to lead its campaign. PSOS have insufficient funds in this time, so they want to earn some money. One of the new members have designed a completely Electronic Roulette in Monte Carlo some time ago. During the obligatory Learn-How-to-Say-the-Truth Course, the member said that the random number generator follows the equation:
xk+1 = (A . xk) mod 47
in which xk+1 is the random number following the previous number xk, and A is the Constant of the Day that is determined by the director Karl Monte each morning. PSOS sent several members to Monte Carlo immediately, to get some money. The problem is that the author of the algorithm suddenly died during the Course. PSOS now need somebody who is able to break the algorithm and predict pseudo-random numbers. Given the succession
xt-n, xt-n+1, ..., xt-1, xt
the program should be able to decide, what the next number xt+1 will be. The Constant A is always integer, non-negative, and less then 1000000. All the numbers xi are integer and non-negative.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of exactly two lines. There is an integer non-negative number M at the first line of each assignment. The next line contains the succession of exactly M numbers (x1, x2, ... xM) separated by spaces.
Output a single line for each assignment. If it is possible to determine the next number in the succession, the line must contain the sentence "Vsad na X." (Bet on X). Replace X with the number which will follow in the succession. If it is not possible to determine the following number, output the sentence "Dalsi cislo nelze urcit." (It is not possible to determine the next number). If the given succession does not follow the above equation, output the sentence "Algoritmus byl zmenen." (The algorithm was changed).
3 1 5 3 7 33 28 3 25 26 25
Output for Sample Input
Dalsi cislo nelze urcit. Vsad na 38. Algoritmus byl zmenen.
(file name: sekretarka.c, sekretarka.p, sekretarka.C)
The basic condition of success of a political party, it is the good Election Programme. PSOS know about it, so they entrust the top secretary Juliet with this task. Because she wanted to make her work easier, she used her charm to talk round her friend Romeo to help her. Romeo is assistent of another political party and he was writing the programme some time ago. While writing the Programme for Juliet, he used some parts of his previous programme. When he gave the finished Programme to Juliet, they recognized that both programmes are too similar and that someone could notice it. They need to determine the longest part of text which is common to both programmes.
At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of exactly two lines of text, each of them contains at most 10000 characters. The end-of-line character is not considered to be a part of the text.
Print a single line of text for each assignment. The line should contain the sentence "Nejdelsi spolecny retezec ma delku X." (The longest common part of text has X characters). Replace X with the length of the longest common substring of both texts.
2 Tady nejsou zadni mimozemstani. Lide tady take nejsou. Ja do lesa nepojedu. V sobotu pojedeme na vylet.
Output for Sample Input
Nejdelsi spolecny retezec ma delku 7. Nejdelsi spolecny retezec ma delku 5.