ACM International Collegiate Programming Contest 1998/99

Central European Regional Contest

Dept. of Computer Science
Czech Technical University in Prague

November 14, 1998

## The Antique Theater

Dear contestants,

You have heard an interesting talk about the Antique Theater yesterday. Now, we will try to imagine how would the theater have looked like if computers had already been invented in ancient time. There is a theater ensemble in Malidinesia, a country far away from Europe. This ensemble is called Antique Comedians of Malidinesia (ACM) and they specialize in playing Antique Comedies. The director of the ACM is a very progressive person so he wants to use computers in almost every particular area of his work.

Your task is to write a set of programs that will help ACM become the best theater ensemble all over the world. The user interface of programs is not important, all we need is an effective algorithm. Thus all the programs will read input data from the standard input and write results to the standard output. It is important to follow the exact format of both input and output data.

If not specified otherwise, all the numbers are only so high to fit into the standard integer (Pascal) or int (C) type.

We wish you good luck in the competition.

Organizers

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.

ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

### Output Specification

For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

```3
24 1
4358 754
305 794
```

```34
1998
1
```

## Copying Books

(file name: books.c, books.p, books.C)

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000.

### Output Specification

For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.

If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

### Sample Input

```2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
```

### Output for the Sample Input

```100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
```

## Substitution Cipher

(file name: cipher.c, cipher.p, cipher.C)

Antique Comedians of Malidinesia would like to play a new discovered comedy of Aristofanes. Putting it on a stage should be a big surprise for the audience so all the preparations must be kept absolutely secret. The ACM director suspects one of his competitors of reading his correspondece. To prevent other companies from revealing his secret, he decided to use a substitution cipher in all the letters mentioning the new play.

Substitution cipher is defined by a substitution table assigning each character of the substitution alphabet another character of the same alphabet. The assignment is a bijection (to each character exactly one character is assigned -- not neccessary different). The director is afraid of disclosing the substitution table and therefore he changes it frequently. After each change he chooses a few words from a dictionary by random, encrypts them and sends them together with an encrypted message. The plain (i.e. non-encrypted) words are sent by a secure channel, not by mail. The recipient of the message can then compare plain and encrypted words and create a new substitution table.

Unfortunately, one of the ACM cipher specialists have found that this system is sometimes insecure. Some messages can be decrypted by the rival company even without knowing the plain words. The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ap is lexicografically smaller than b1b2 ... bq if there exists an integer i, i <= p, i <= q, such that aj=bj for each j, 1 <= j < i and ai < bi.

The director is interested in which of his messages could be read by the rival company. You are to write a program to determine that.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. The first line of each case contains only two positive integers A, 1 <= A <= 26, and K, separated by space. A determines the size of the substitution alphabet (the substitution alphabet consists of the first A lowercase letters of the english alphabet (a--z) and K is the number of encrypted words. The plain words contain only the letters of the substitution alphabet. The plain message can contain any symbol, but only the letters of the substitution alphabet are encrypted. Then follow K lines, each containing exactly one encrypted word. At the next line is encrypted message.

### Output Specification

For each case, print exactly one line. If it is possible to decrypt the message uniquely, print the decrypted message. Otherwise, print the sentence 'Message cannot be decrypted.'.

```2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
aac
bca
bdac
```

### Output for the Sample Input

```abcde
Message cannot be decrypted.
```

## Commedia dell' arte

(file name: dellarte.c, dellarte.p, dellarte.C)

So called commedia dell' arte is a theater genre first played at Italy in the beginning of the sixteenth century. It was inspired with the Roman Theater. The play had no fixed script and the actors (also called performers) had to improvise a lot. There were only a simple directions by the author like "enter the stage and make something funny" or "everyone comes on stage and everything is resolved happily". You can see it might be very interesting to play the commedia dell' arte. Therefore the ACM want to put a new play on a stage, which was completely unknown before. The main hero has a puzzle that takes a very important role in the play and gives an opportunity of many improvisations. The puzzle is the worldwide known Lloyd's Fifteen Puzzle. ACM wants to make the play more interesting so they want to replace the "standard" puzzle with a three-dimensional one. The puzzle consists of a cube containing M3 slots. Each slot except one contains a cubic tile (one position is free). The tiles are numbered from 1 to M3-1. The goal of the puzzle is to get the original ordering of the tiles after they have been randomly reshuffled. The only allowed moves are sliding a neighbouring tile into the free position along one of the three principal directions. Original configuration is when slot with coordinates (x,y,z) from {0,...,M-1}3 contains tile number z.M2+y.M+x+1 and slot (M-1,M-1,M-1) is free.

Your are to write a program to determine whether it is possible to solve the puzzle or not.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. The first line of each case contains only one integer M, 1 <= M <= 100. It is the size of 3D puzzle cube. Then follow M lines, each contains exactly M2 numbers on the tiles for one layer. First is the layer on the top of the cube and the last one on the bottom. In each layer numbers are arranged from the left top corner linewise to the right bottom corner of the layer. In other words, slot with coordinates (x,y,z) is described by the (x+M.y+1)-th number on the (z+1)-th line. Numbers are separated by space. Number 0 means free position.

### Output Specification

For each case, print exactly one line. If the original configuration can be reached by sliding the tiles, print the sentence 'Puzzle can be solved.'. Otherwise, print the sentence 'Puzzle is unsolvable.'.

```2
2
1 2 3 4
5 7 6 0
2
2 1 3 5
4 6 0 7
```

### Output for the Sample Input

```Puzzle is unsolvable.
Puzzle can be solved.
```

## Calculating Expressions on Turing Machine

(file name: expr.c, expr.p, expr.C)

### Turing Machine

Turing Machine (TM) was defined by mathematician Alan Turing in 1936. You probably expect all the Contest problems to be related to the same topic, so you may now wonder what the Turing Machine has in common with the Antique Theatre. The fact is that Alan Turing had a friend called Fred. And Fred's Grandmother was keen on Antique Tragedies. So we think it is a good idea to give you this problem as a remembrance of Alan Turing.

Let us describe one particular TM: TM consists of two-way potentially infinite tape, read/write head and a finite automaton control unit. The tape is an infinite one-dimensional sequence of fields. Each field contains one symbol of an alphabet Sigma = {~,0,1,...,M}, where '~' is a special blank symbol. At each moment, there is just a finite number of fields not containing the blank symbol.

The head is a device capable at each step of reading one symbol from the tape field above which it is positioned, writing another symbol on its place and moving one field to the left or right. As the tape is two-way potentially infinite, the movement is always possible.

The control unit drives the head. At each time, it is in one state taken from Gamma = {0,1,...,N}. It starts in state 0. At each step the control unit considers its actual state gamma and the symbol under the head sigma. This information determines the symbol to be written on the tape sigma' in place of sigma, the next state to go gamma' and the direction delta (R or L for right or left) for the movement of the head.

TM description (TMD) is a triple (M,N,P) where P is a set of rules. Each rule is a quintuple (gamma, sigma, sigma', gamma', delta) describing the behaviour of the machine in a particular situation as described in the preceding paragraph. If no rule exists for the current situation, the machine stops, i.e. the calculation is finished. Conflicting (with the same gamma and sigma) rules may not exist.

In the text form, TMD starts with a line containing positive integers M and N. Then there is an arbitrary number of lines containing each one rule. The rule is described as gamma sigma sigma' gamma' delta, where gamma, sigma, sigma' and gamma' are integers ('~' should be coded as -1 and delta from {R, L}, the symbols are separated by spaces. After the last rule, a line immediately follows which contains only the symbol '-'.

When the machine starts there will be a finite string of symbols from Sigma starting under the head position and continuing to the right. All the remaining fields on the tape are blank.

Theoretically, TM is equivalent to any general purpose computer. We ask you to at least partly demonstrate it --- you are to write a program generating TMD evaluating arbitrary Turing arithmetic expression (TAE) for any input values. TAE is defined in the following section.

### Turing Arithmetic Expression

TAE is defined by the following grammar:

• TAE -> expr
• expr -> factor | expr + expr
• factor -> ( expr ) | factor * factor | variable
• variable -> 1 | 2 | ... | 9

The operators + resp. * operators stand for integer addition resp. multiplication modulo 10 (e.g. 238*17=6); multiplication takes precedence over addition. The syntactic element variable denotes the value of the first, second, etc. up to ninth integer written on the tape of the TM at start time.

Write a program that for each TAE outputs a TMD evaluating the TAE for any valid contents of the tape. A valid contents of the tape is a sequence of at most nine non-negative integers written left to write (most significant digit first) in a decimal notation using symbols 0, ..., 9 and separated by one blank symbol. All the rest of the tape is blank, the head starts at the most significant digit of the first number. The magnitude of the integers is not specified. Example of a valid tape (underline indicates head position):

`... ~ ~ ~ ~ 1 2 3 ~ 4 7 ~ 1 1 ~ ~ ~ ~ ...`

When the TM finished processing the tape should contain the result of the computation starting with the most significant digit under the head and continuing to the right until the first blank. No leading zeros are allowed. The contents of the rest of the tape is insignificant. For example, if the TAE was (1+3)*2 and the tape contents as above, the correct answer would be (123+11).47 mod 10 = 8. The correct tape contents would be

`x x x 8 ~ x x x`

where x stands for any symbol.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case is described by one line, containing one valid TAE. The line is at most 1000 characters long, does not contain any characters other than 0, 1, ..., 9, (, ), * and +, and is terminated by the newline character.

### Output Specification

For each case, print valid TMD that evaluates the TAE for any valid tape contents. You can assume there will be always at least as many integers on the tape, as mentioned in the TAE.

Remark: For this problem, 'Presentation error' is returned if your program did not generate a valid TMD, while 'Wrong answer' means that the generated TMD was valid but the corresponding TM did not produce the correct output.

```2
1
2
```

```9 2
0 1 1 1 R
0 2 2 1 R
0 3 3 1 R
0 4 4 1 R
0 5 5 1 R
0 6 6 1 R
0 7 7 1 R
0 8 8 1 R
0 9 9 1 R
1 1 1 2 L
1 2 2 2 L
1 3 3 2 L
1 4 4 2 L
1 5 5 2 L
1 6 6 2 L
1 7 7 2 L
1 8 8 2 L
1 9 9 2 L
1 -1 -1 2 L
-
9 1
0 1 1 0 R
0 2 2 0 R
0 3 3 0 R
0 4 4 0 R
0 5 5 0 R
0 6 6 0 R
0 7 7 0 R
0 8 8 0 R
0 9 9 0 R
0 -1 -1 1 R
-
```

## Skyscraper Floors

(file name: floors.c, floors.p, floors.C)

What a great idea it is to build skyscrapers! Using not too large area of land, which is very expensive in many cities today, the skyscrapers offer an extremely large utility area for flats or offices. The only disadvantage is that it takes too long to get to the upper floors. Of course these skyscrapers have to be equiped not only with a stairway but also with several elevators. But even using ordinary elevators is very slow. Just imagine you want to get from the very top floor to the base floor and many other people on other floors want the same. As a result the elevator stops on almost every floor and since its capacity is limited and the elevator is already full from the upper floors, most stops are useless and just cause a delay. If there are more elevators in the skyscrapers, this problem is a little bit eliminated but still not completely. Most people just press all the buttons of all the elevators and then take the first one so that all elevators will stop on the floor anyway.

However, the solution exists as we shall see. The Antique Comedians of Midilesia headquarters reside in a skyscraper with a very special elevator system. The elevators do not stop on every floor but only on every X-th floor. Moreover each elevator can go just to a certain floor Y (called starting floor) and cannot go any lower. There is one high-capacity elevator which can stop on every elevator's starting floor.

The ACM has a big problem. The headquarters should be moved to another office this week, possibly on a different floor. Unfortunately, the high-capacity elevator is out of order right now so it is not always possible to go to the base floor. One piece of furniture cannot be moved using the stairway because it is too large to pass through the stairway door. You are to write a program that decides whether it is possible to move a piece of furniture from the original office to the other.

### Input Specification

The input consists of N cases. The first line contains only one positive integer N. Then follow the cases. Each case starts with a line containing four integers F, E, A, B, where F, 1 <= F < 50000000 determines the number of floors in the skyscraper (this means that there are floors 0 to F-1), E, 0 < E < 100 is the number of elevators and A, B, 0 <= A,B < F are numbers of the two floors between which the piece of furniture should be moved. Then follow E lines. Each of them contains description of one elevator. There are exactly two integers X and Y, X > 0, Y >= 0 at each line. Y determines, that the elevator starts on the Y-th floor and X determines, that it stops on every X-th floor, eg. for X = 3, Y = 7 the elevator stops on floors 7, 10, 13, 16, etc.).

### Output Specification

For each case, print exactly one line. If floor B is reachable from floor A not using the stairway, print the sentence 'It is possible to move the furniture.', otherwise print 'The furniture cannot be moved.'.

```2
22 4 0 6
3 2
4 7
13 6
10 0
1000 2 500 777
2 0
2 1
```

### Output for the Sample Input

```It is possible to move the furniture.
The furniture cannot be moved.
```

(file name: glass.c, glass.p, glass.C)

Once upon a time there was a famous actress. As you may expect, she played mostly Antique Comedies most of all. All the people loved her. But she was not interested in the crowds. Her big hobby were beads of any kind. Many bead makers were working for her and they manufactured new necklaces and bracelets every day. One day she called her main Inspector of Bead Makers (IBM) and told him she wanted a very long and special necklace.

The necklace should be made of glass beads of different sizes connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not very robust so it is possible that the necklace will get torn by its own weight. The situation becomes even worse when the necklace is disjoined. Moreover, the point of disconnection is very important. If there are small beads at the beginning, the possibility of tearing is much higher than if there were large beads. IBM wants to test the robustness of a necklace so he needs a program that will be able to determine the worst possible point of disjoining the beads.

The description of the necklace is a string A = a1a2 ... am specifying sizes of the particular beads, where the last character am is considered to precede character a1 in circular fashion.

The disjoint point i is said to be worse than the disjoint point j if and only if the string aiai+1 ... ana1 ... ai-1 is lexicografically smaller than the string ajaj+1 ... ana1 ... aj-1. String a1a2 ... an is lexicografically smaller than the string b1b2 ... bn if and only if there exists an integer i, i <= n, so that aj=bj, for each j, 1 <= j < i and ai < bi.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line containing necklace description. Maximal length of each description is 10000 characters. Each bead is represented by a lower-case character of the english alphabet (a--z), where a < b   ...   z.

### Output Specification

For each case, print exactly one line containing only one integer -- number of the bead which is the first at the worst possible disjoining, i.e.\ such i, that the string A[i] is lexicographically smallest among all the n possible disjoinings of a necklace. If there are more than one solution, print the one with the lowest i.

```4
helloworld
amandamanda
dontcallmebfu
aaabaaa
```

```10
11
6
5
```

## Hares and Foxes

(file name: hares.c, hares.p, hares.C)

The Antique Comedians of Malidinesia play an interesting comedy where many animals occur. Because they want their plays to be as true as possible, a specialist studies the behaviour of various animals. Recently, he is interested in a binary dynamic ecological system hares-foxes (SHF). As a part of this project, you are asked to design and implement intelligent automatic target evaluation simulator (IATES) for this system. The behaviour of the SHF follows so called standard model, described by the following set of difference equations.

hy+1 = a.hy - b.fy
fy+1 = c.fy + d.hy

where hy resp. fy represent the difference of the number of hares resp. foxes in year y and the reference count determined at the beginning of the experiment. The units of hy and fy are unknown. Therefore, hy and fy are to be treated as real numbers. Your task is to write a program to determine the long term evolution of SHF.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of six real numbers a, b, c, d, h1998 and f1998, written in this order on three lines, two numbers per line, separated by one or more spaces. The numbers are given in the classical format, i.e. optional sign, sequence of digits, optional dot and optional sequence of digits. The text form of a number does not exceed 10 characters. Each case is followed by one empty line.

### Output Specification

For each case, print one of the following sentences:
• 'Ecological balance will develop.' - if after sufficiently long time the population of both hares and foxes approaches the reference count with an arbitrary a priori given precision, i.e. lim hy=0 and lim fy=0.
• 'Hares will die out while foxes will overgrow.' - if after sufficiently long time the population of hares resp. foxes falls under resp. exceeds any a priori given threshold, i.e. lim hy=-infinity and lim fy=+infinity.
• 'Hares will overgrow while foxes will die out.' - if after sufficiently long time the population of foxes resp. hares falls under resp. exceeds any a priori given threshold, i.e. lim hy=+infinity and lim fy=-infinity.
• 'Both hares and foxes will die out.}' - if after sufficiently long time the population of both hares and foxes falls under any a priori given threshold, i.e. lim hy=-infinity and lim fy=-infinity.
• 'Both hares and foxes will overgrow.' - if after sufficiently long time the population of both hares and foxes exceeds any a priori given threshold, i.e. lim hy=+infinity and lim fy=+infinity.
• 'Chaos will develop.' - if none of the above mentioned description fits.

```2
2 0.5
0.5 0.6
2 3

0.1 1
2 0.1
1 1
```

### Output for the Sample Input

```Both hares and foxes will overgrow.
Hares will die out while foxes will overgrow.
```

## Invitation Cards

(file name: invite.c, invite.p, invite.C)

In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery.

The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where 'X' denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.

All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.

### Input Specification

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.

### Output Specification

For each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.

```2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
```

```46
210
```