Department of Computer Science, CTU FEE & Czech ACM Chapter CTU Open Contest 1999
Dear Contestants: As every year, we have prepared a set of real life problems. This time it
is the composing of excelent The GUI was given to another firm, so we are interested in the efficient algorithms only. All the programs you have to create should read the data from the standard input and write the result to the standard output. You must follow the given format exactly in order to allow integration with the GUI. When there are more values on the same line, they are divided using exactly one space, if not specified otherwise. Neither input nor output may contain unneeded spaces and lines. Because some situations require batch processing of more input cases, your programs must be able to solve more instances of the problem at once. Usually there is the total number of problems specified on the first line. Then the particular cases follow. The exact format is specified for each of the problems. If the input contains any integer numbers, they are only so big to fit into standard integer type (if not specified otherwise). Also the result should fit into it (if not specified otherwise). Well, all we need to do now is to wish you Good Luck. Your Organization Team ## Jack( We need to have at least one computer game in our collection, of course. The typical one could be described as "chase in the town". The smiling face called Jack in our case is walking through the town divided into small fields. Some of the fields are covered with the wall and it is not possible to go through them. Jack collects the points and tries to avoid contact with the monsters who chase him. Once the Jack eats the special point (or asterisk), the situation turns upside-down and Jack can eat monsters. And so on, still again and again. I am sure everyone of you have ever seen such game. The town is randomly generated in our case. Jack always starts in the top left corner and the "bonus asterisk" is in the bottom right corner. At the most difficult level, the bonus is set to disappear after exactly as much steps that are sufficient to get from one corner to another, providing Jack only makes steps to the left and to the bottom. Should he made one single step into the wrong direction and he never could be there in time. But it is still important to prevent being catched by monsters. So the player has to choose the best possible way to the bottom right corner. You are to determine how many different ways exist in the town. ## Input SpecificationThe input consists of ## Output SpecificationPrint exactly one line for each of the input cases. The line must contain
the statement " X with the
number of all existing different paths between the top left and the bottom
right corner. Each path must consist of R+S-2 steps, each leading
to the left or to the right. No path can cross any field with the wall.
## Sample Input2 3 3 ... .#. ... 1 6 ...#.. ## Output for the Sample InputExistuje 2 ruznych cest. Existuje 0 ruznych cest. ## Kaleidoskop (Caleidoscope)( We suppose even the very little children will play with KOKODáKH. So beside all the games and riddles, we need to have at least one toy in it. It is very favourite one and no special knowledge or ability is required to play with it. Yes, it is the Caleidoscope. I guess all of you know the magic thing. You can watch into it for long hours and still find new and new images that never repeat. But there is a problem with the little children. They break everything they have, all the things are falling from their hands down to the ground. The mechanics of caleidoscope is very fine and so it is very sensitive to proper handling. So our variant of this toy is not mechanical but fully electronic one. The main advantage is that it is water-resistant, fire-resistant, cold-resistant, it cannot break and does not catch fire. Besides, it contains a special teeth detector that prevents the children to bite it. Every tooth contact is detected and reacts with the electric shock (@@@) immediately. The main problem with our electric caleidoscope is the picture generating. To reach the quality of the mechanical caleidoscope, the picture must consist of many similar pieces that are resized, mirrored and rotated. As many of you probably know, we use matrices in computer graphics to manipulate pictures. The so called transformation matrix specifies the action that should be done with the picture. The picture manipulation is then done by matrix multiplication. We can also preform many transformations sequentially, by multiplying with more matrices. The picture manipulation is very difficult in the caleidoscope, so the matrices can be very large. Your task is to write a computer program that would be able to multiple the given matrix with the sequence of other matrices.
When we multiple the matrix
## Input SpecificationThe input consists of ## Output SpecificationThe program should print out the resulting matrix for each assignment,
with the dimensions ## Sample Input2 2 3 1 1 2 3 1 3 3 2 1 2 2 2 -1 1 -1 1 2 2 1 2 3 4 ## Output for the Sample Input3 2 1 6 4 2 9 6 3 2 2 2 2 ## Logik (Logic)( There is also the logical game "Of Liars and Honest Men" in our KOKODáKH collection. Almost any number of players can participate in the same game and no special items are needed. The rules are simple: every player tosses a coin to decide if he is Liar or Honest. All the other players know what he is. After all of the roles are determined, the play begins. Honest men must tell the truth under any circumstances, liars must always lie. Whoever should violate this simple rule, he (or she) loses that game. You would not believe how interesting this game can be! Good players can assemble (@@) even very complicated statement and it is very difficult to determine its meaning. Excellent players can play this game for several days without making a mistake. Their children and wives search them all over the town without any success. The players consider for the best situation, when some other person enters the room and listens to them. Of course the players won't stop! They want to impress the new person and the statements become even more complicated. The witness (@@@) has the only possibility. He must to listen very carefully and determine who is who. The best for him is to prove someone's mistake because it should ended the game. Unfortunately, this is not easy. You are to write a computer program that will be able to listen the conversation and tries to determine who is liar. ## Input SpecificationThe input consists of Each assignment begins with one empty line that separates it from the
previous text. Then there is the single number Then there is a single number
- 1.
`X`+`Y`=`Z`- 2.
(`H`je poctivec)`H`is Honest- 3.
(`H`je lhar)`H`is Liar- 4.
(`H`rika "`V`".)`H`says`V`- 5.
(`H`rika "`V`" a je to opravdu tak)`H`says`V`and it's really true- 6.
(`H`rika "`V`", ale neni to pravda)`H`says`V`but is lying- 7.
`Poctivcu je mene nez` (`X`*There are less than*)`X`Honests- 8.
`Poctivcu je vice nez` (`X`*There are more than*)`X`Honests- 9.
`Poctivcu je alespon` (`X`*There are ate least*)`X`Honests- 10.
`Lharu je mene nez` (`X`*There are less than*)`X`Liars- 11.
`Lharu je vice nez` (`X`*There are more than*)`X`Liars- 12.
`Lharu je alespon` (`X`*There are ate least*)`X`Liars- 13.
`(` (`V`) a zaroven (`W`)*(*)`V`) and (`W`)- 14.
`(` (`V`) nebo (`W`)*(*)`V`) or (`W`)
The formula of type 4 is true if and only if the
player ## Output SpecificationPrint the line " X with the number
of the assignment, starting with one.
As the first step, assume that no player violated the rules, that means
liars say false formulas and honests say the truth. If there exists such
arrangement of players that all the formulas could be said, the set of
formulas is called " ().
If there are more roles to be reported, they should be printed in the same
order as the player names on the beginning of input file. If it is not
possible to determine any player's role, the program should print the
line "H is honest`Neda se nic zjistit.` " (Nothing could be deducted).
If the set of formulas is not satisfiable, it is obvious that someone has
violated the rules and has lost the game. So we should try to determine who
was that. Assume that only one player did the mistake. If the player
If there is exactly one player after removing whose "main" formulas we
get the satisfiable set, the program should print the line
" ```
Prohral nektery z techto hracu:
``` "
(Some of the following players has lost:
).
F1, F2, F3If there is no such player whose formulas we could remove to get the
satisfiable set, the program is to print the line:
" Print one empty line after each assignment including the last one. Empty
line contains one the special character ## Sample Input2 3 Petr Josef Marie 1 Petr: Petr je lhar. 3 Petr Josef Marie 1 Josef: Marie rika "Marie je lhar" a je to opravdu tak. ## Output for the Sample InputHra cislo 1: Petr prohral. Hra cislo 2: Josef je lhar. Marie je poctivec. ## Mocneni (Raising Modulo Numbers)( People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow: Each player chooses two numbers B and writes them on a slip of paper. Others cannot
see the numbers. In a given moment all players show their numbers to the
others. The goal is to determine the sum of all expressions
_{i}A from all players including
oneself and determine the remainder after division by a given number
_{i}^{Bi}M. The winner is the one who first determines the correct
result. According to the players' experience it is possible to increase the
difficulty by choosing higher numbers.
You should write a program that calculates the result and is able to find out who won the game. ## Input specificationThe input consists of B separated by
space. Both numbers cannot be equal zero at the same time.
_{i}## Output specificationFor each assingnement there is the only one line of output. On this line, there is a number, the result of expression
## Sample Input3 16 4 2 3 3 4 4 5 5 6 36123 1 2374859 3029382 17 1 3 18132 ## Output for the Sample Input2 13195 13 ## Nejvyssi zisky (The Highest Profits)( This program will not be part of the KOKODáKH collection, but it may be more important than the games themselves. It will serve to the marketing staff to find suitable procedures for promoting and selling the collection. So try to do your best. Extensive marketing case study tried to prove that the total income from
selling a product is polynomial function of number of satisfied
customers. Experiments showed that the real results are not exactly the same
which you can obtain using the function. However, this method is widely
used. The reason is probably nonexistence of better solution. Let's denote
the number of satisfied customers
The number of satisfied customers depends on the price of a product.
Again, there is hypothese that this dependence is polynomial. If we
denote the price
Coeficients b strongly
depend on the season of the year, the moon phase, the purchasing power of
customers, inflation rate and hunderds of other parameters. Besides on the
kind of product and its quality, of course. In the past there was lot of
effort put into the reserarch of these parameters. For various combinations
of input parameters, the coeficients are stated in Pyshwejc's marketing
tables. It is not thus difficult to find out their values. But the degree of
polynoms is usualy very high. It is very difficult to substitute one
polynom into the other and to compute the dependency of the profit on the
price. This dependency is usually crucial for us to set the right price.
_{i}Your goal is to write the program which can substitute the polynom
## Input SpecificationThe input consists of a. These numbers
are coeficients of polynom _{m}P. On the third line there are
n+1 integers b
... _{0}b. Always _{n}a and
_{m} <> 0b. Coeficients _{n} <> 0a and
_{i}b are separated by space and they are chosen in order
to each resulting coeficient could fit into the standard type
_{i}integer.
## Output SpecificationThe program prints exactly one line for each assignement. On this line,
there will be c of resulting
polynom. The coeficients are separated by space and the line does not consist
any redundant spaces. The coeficient in the highest degree should not be
zero.
_{p}## Sample Input3 0 0 7 -2 1 1 6 6 9 -6 3 3 -3 6 -5 1 0 3 -3 1 ## Output for the Sample Input7 60 -36 -3 18 -63 123 -156 138 -86 36 -9 1 ## Osmismerka (Word Puzzle)( What a game collection it would be without famous and well known word puzzle. Also KOKODáKH contains this game. Typical word puzzle is a rectangular array filled with letters, and the list of words. The goal is to find the words form the list in the array and to score out all their letters. After scoring out the letter can still be part of any other word (words can cross and overlap). When all words from list are found and scored out there are several remaining letters. These letters, read in rows, create the secret word. The words can be found in all eight directions, including diagonal directions. It is clear that KOKODáKH has to bring some innovation into this game. The
new rule says that the word can "jump over" the array boundary and continue
on the opposite side. Upper row is thus next to the bottom row and the left
collum is next to the right one. If we number the rows with numbers 0 till
## Input SpecificationThe input consists of ## Output SpecificationThe program prints one line for each assignement. On this line there will be all letters from word puzzle which remained in the array after scoring out all the words that appeared on the list. The letters are not separated and they are lined up in order in which they appeared in the array in row major order. At the end of the string, there is the newline character. If there are no remaining letters after scoring out all words, the program prints out empty line. ## Sample Input1 3 7 kroksun pranyra cmakrom 7 syr kra kroksunkrok pranyr rak mak makro ## Output for the Sample Inputacm ## Patnactka (Lloyd Fifteen Puzzle)( Nearly everybody knows the popular game called Also KOKODáKH contains the modification of this game. The game is destinated for the advanced players so the fifteen tiles would be too little. Our game can have arbitrary dimension of the array. Your goal is to write the program which will simulate the working of this game. For a given starting situation it has to replay the succession of valid moves and to display the final state of the puzzle. The valid move is moving the tile to the neighbouring free position up, down, right or left. Any other move is not valid. ## Input SpecificationThe input consists of At the first line of the description of the game initialposition, there are
two integers The list of moves follows. The list can be empty. Each move is on the
separate line and consists of one number ## Output SpecificationFor each assignement the program prints out one line " C is substitued by the number of the assignement. The numbering of
assingement is ascending and begining with 1.
For each move in the list the program finds out if the move is valid. The
move is valid if there is an empty field neighbouring. For each valid move the
program prints out the following sentence at the separate line: " T is the number of the tile and
KAM is one of the strings "doprava", "doleva",
"nahoru" nebo "dolu" (right, left, up, down). If
the move is not valid the sentence "```
Neplatny tah kamenem
``` " (Invalid move with tile is printed
out.
T)When the list of moves ends, the program prints out the final state of
the puzzle in the similar format that was used in the input. The output has
to consist of ## Sample Input2 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 15 11 7 0 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 15 1 0 ## Output for the Sample InputSkladacka cislo 1: Kamen 15 presunut doprava. Kamen 11 presunut dolu. Kamen 7 presunut dolu. 1 2 3 4 5 6 0 8 9 10 7 12 13 14 11 15 Skladacka cislo 2: Neplatny tah kamenem 1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 15 ## Quorf( To keep the word "card" in its name, KOKODáKH also contains one less known
card game called The principle of the game is very easy. Each of two preparing players chooses for one packet arbitrary cards and shuffle them in the order which cannot be changed later. The "main" player can then look at both packets and orders his third pakcet in arbitrary order. Of course he tries to choose the order in the way which enables him to win in the following game. During the game both players (in our case represented by the program) turn the upper card from their packets and put it at the table. Main player then turns the cards from his packet and puts them at the table. If he turns a card that already appears on the table by one of the other players, that player's card is put out of game. If both players has the same card and the main player turns it, both their cards are put out of game. Games continues until the main player has cards in his packet. Then, if any of two players has any card, the main player losts. If neither of the two players has any card, third player won. The program plays the role of the two players. Generating the contents of both packets is not difficult problem. More difficult is to find out whether the third player can win. Your task is to write program that will be able to determine this. ## Input SpecificationThe input consists of M numbers
b. These numbers give the order of the cards in the
packets of both preparing players. No number can appear twice in the same
succession. Thus, for each _{i}i,j if a or
_{i} =
a_{j}b then _{i} = b_{j}i = j.
## Output SpecificationThe goal of the program is to determine for each assignment whether
there is a succession c,
..., _{2}c such that no number appeares twice in this
succession and the order of the cards leads to the victory. If such
succession exists, the program prints out the only line containing the
sentence "_{x}Hrac ma sanci vyhrat." (The player can win). If
there is no such succession, the input is the sentece "Spatne
usporadani." (Wrong order).
## Sample Input2 4 4 1 2 3 4 4 3 2 1 4 4 1 3 5 7 2 4 6 8 ## Output for the Sample InputSpatne usporadani. Hrac ma sanci vyhrat. |