|
ACM International Collegiate Programming Contest 1998/99
Sponsored by IBM
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
Adding Reversed Numbers
(file name: adding.c, adding.p, adding.C)
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.
Sample Input
3
24 1
4358 754
305 794
Output for the Sample Input
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.'.
Sample Input
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
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.'.
Sample Input
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.
Task
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.
Sample Input
2
1
2
Output for the Sample Input
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.'.
Sample Input
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.
Glass Beads
(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.
Sample Input
4
helloworld
amandamanda
dontcallmebfu
aaabaaa
Output for the Sample Input
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.
Sample Input
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.
Sample Input
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
Output for the Sample Input
46
210
| 
