e-mail e-mail how to use these pages? how to use these pages? Czech Version Czech Version

ACM Programming Contest
mail, help

Department of Computer Science, CTU FEE & Czech ACM Chapter

CTU Open Programming Contest 1997

Travel agency ACMCZ

When our economy was changed to the free market, the number of various companies were founded in various fields of activities. One of the most successful areas became travel agencies especially those who organize traveling abroad. One from these new agencies is ACMCZ, Amaterske Cestovani Mezi Cizokrajnymi Zviratky (this is difficult to translate, approximately it means Amateur Traveling Among Strange Animals), which is successful because of its very original services.

To run such as agency is not easy and it means a lot of time and energy for the owner. Because of this he bought a new computer, where he would like to run all the agenda. But there is yet no software ready, so you have to help him with writing some basic programs for running the agency.

Because the owner is very familiar with computers, the graphical output is not so important for him - but he is looking for very efficient calculations. All the programs, which you have to write, will receive the standard input and all the results have to be sent to the standard output. In all cases the values on input will be only so high to fit into the standard integer or int type (unless stated otherwise).

All best for you programming...

Airport

While transporting the costumers' luggage, the travel agency ACMCZ uses the Super-efficient Ultra-lifting Natural-gas-free Rotatable Hydraulical Ecological Movable Electrical Truck SUN-RHEM-ET-31789/48WQ, also called the lorry. The luggage is loaded onto the truck and then it is put to the unloading sector.

There is Guiliam Wates Airport in the Republic of Muctonsofia. Between the runway and the luggage unloading ramp there is a very long and narrow path, bounded with the high walls on the both sides. Unfortunately, the path is covered with various boxes, machines, crashed cars, planes, computers, and other rubbish. Although all the travel agencies often complain about it, the airport owner Guiliam Wates refuses all that criticism stating that in every moment there was at least one possibility to go through.

There was only a single improvement at the airport since 1981 -- the surface of the path was divided into square tiles. Each tile (except the tiles at the border) neighbours with exactly four other tiles, one on each side. The size of the tile is large enough to allow the truck to go through and to turn 90 degrees to the left or right. The path has the same width along its whole length -- that means the tiles make a rectangle with the sides S (width) and L (length). With the help of the stationary satellite (which was bought by the director especially for that purposes) the picture of the path is taken each hour and one computer makes an evidence which tiles are free.

The owner of the ACMCZ agency does not like the situation because the drivers lose lots of time by turning, back-tracing and finding the right way. Moreover, the lorry finds sometimes no way at all, and it has to come back and wait for some tiles to become free again. The lawyers of ACMCZ used some more or less legal way to got some pictures taken by the satellite. Their goal is to prove that there existed some moments when it was definitely impossible to pass through. Now they need the computer program to help them with this question.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. The first line of each assignment contains a positive integer S, S <= 10000. It is the number of tiles in one row, that means the width of the rectangle. Then L lines follow, each containing a single row of tiles. Each of that lines contains exactly S characters (the end-of-line character is not counted), each of that characters is either 1 (free tile, it is possible to go through) or 0 (occupied tile, impossible to go through). There is no restriction on the number of rows (the length of the rectangle). Each assignment ends with an empty line. Empty line contains only the end-of-line character.

Output Specification

The program should output exactly one line for each assignment. The line should contain the sentence "Cesta je prujezdna." (the path allows transit) if it is possible to pass through the whole length of the path. Otherwise, output the line containing the sentence "Cesta neni prujezdna." (the path does not allow transit). The lorry can only use the free tiles and can only move between the neighbouring tiles. Neighbouring tiles are connected to each other by their whole side, not only touching at the corner.

Sample Input

3
7
0000110
0111010
0101010
0101010
1101110
1000000
1100000
0100000

10
0010010000
0100001111
0100001101
0111001000
0000000111
0000001010

10
0010010000
0110000000
0100001111
0000001101
0000011001
0000001010
0000000000

Output for Sample Input

Cesta je prujezdna.
Cesta neni prujezdna.
Cesta neni prujezdna.

Term

Travel agency ACMCZ is offering vacation on a shore of the Bulfik lake each year. This trip is special, because there is no arrange program for participants and everybody can do what he likes. Other advantage is the lower price for such as trip. The agency only prepare cabins and tends for accommodation of various number of persons, ensure one or two administrators of the camp, one bus and those are all expenses. The camp is rented from BSA (Bulfik Shore Agency), which has of course more travel agencies interesting for an accommodation so they can provide camp only for the limited number of days.

To choose the best term for the reservation of the camp, ACMCZ does search among the clients. ACMCZ is giving them a questionnaire to know how many are interesting in each day of the season. Your program has to look for the best term from the results of the questionnaires. The program has to find such as term which is not longer than the number of days offered by BSA and which gives the maximum sum of clients for all the days during the term. The term must be coherent, because BSA does not want to change client agencies so often.

Input Specification

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 is a positive integer K, K<=1000. Each K states the maximum number of days which BSA is willing to sublet. The second line of each assignment contains the sequence of non-negative integers separated by spaces. These numbers are never greater than million and they represent how many clients are interesting for each day during the whole season. The total number of these days is not limited. There is exactly one space character between any two consecutive numbers. After the last number on the line there is no trailing space, only the new line character follows.

Output Specification

For each assignment there must be exactly one output line with the sentence "Nejvhodnejsi termin zacina XX. dnem." (The best term starts on the day number XX), where XX is the day number of the first day of the term in which sum of all clients from all the days is maximal and which is not longer then K days. Days are numbered from the beginning of sequence started with one. If there is more than one solution, give the first one.

Sample Input

3
3
6 2 3 2 9 2 1 1
3
1 1
2
1 1 2 1 3 2 8 1

Output for Sample Input

Nejvhodnejsi termin zacina 3. dnem.
Nejvhodnejsi termin zacina 1. dnem.
Nejvhodnejsi termin zacina 6. dnem.

Compiler

Travel Agency ACMCZ has a lot of rivals, but the most important of them is Nonpolitical Association for Tourist Observation (NATO) that has a large computing center. Since the owner of ACMCZ found out the plans of his rival, he corrupted one of the rival's employees to get the source programs. He found out that most of the computings in rival's computer center is done on research about the future of women on the Earth. Because the results are very important for any travel agency, ACMCZ would like to use them for its own purposes. To avoid the risk the stolen software could be found on the hard disk of ACMCZ computer, all the calculations will be run using the programmable calculator. Unfortunately all the source programs are written in miniBASIC but the calculator is using the stack language miniFORTH. ACMCZ needs a compiler to make translations between those two languages.

Statements of miniBASIC are:

  • LET var=expr, where var is an identifier of a variable and vyraz is an arithmetical expression. This statement assigns the value of the expression to the variable var.
  • PRINT var, where var is an identifier of a variable. The statement prints out the value of the variable var and then terminates the program.

Identifier of a variable is exactly one capital letter (A to Z).

Arithmetical expression is one of the following possibilities:

  • decadic number
  • identifier of a variable
  • expression created from the above possibilities using one of the operators + (plus), - (minus), * (times), / (divide) and the followin scheme:
    • <expression> ::= <operand1> <operator> <operand2>
    • <operand> ::= <number> or <identifier>

The program in miniBASIC is a sequence of LET statements followed by exactly one PRINT statement. PRINT is the last statement in the program. Each statement is placed on a single line, no unneeded spaces are present. Note that each expression may contain only one operator.

miniFORTH language is the stack computer language with the following statements:

  • : - beginning of the program
  • ; - end of the program
  • var - store the address of a variable var onto the top of the stack
  • @ - dereference, i.e. the address of a variable on the stack top is replaced by the value of that variable
  • const - store the constant onto the top of the stack, const is a decadic number
  • + - addition
  • - - subtraction
  • * - multiplication
  • / - division
  • . - print out the value on the stack top and then clean the whole stack

Arithmetical operations are always performed with the values on the stack top (the left operand is on the top, the right operand next from the top), the both operands are removed from the stack and the result is stored back onto the stack top. Statements are separated by an arbitrary number of spaces.

Input Specification

At the first line there is a positive integer N stating the number of miniBASIC programs to follow. The length of miniBASIC program is not limited. After the last statement of each program there is an empty line with only a single "new line" character.

Output Specification

For each miniBASIC program there must be exactly one line of output containing the program in miniFORTH, which is equivalent to the given miniBASIC program. Two programs are considered to be equivalent if they give the same result for an arbitrary initial variable values (there is the same value on the output). More complicated expressions may be optimized in any way but this is not required.

Sample Input

2
LET A=12*A
LET B=A-5
LET C=67+B
PRINT C

LET D=A-B
LET E=C+D
LET F=D*E
LET G=D/E
PRINT G

Output for Sample Input

: 67 12 A @ * 5 - + . ;
: A @ B @ - C @ A @ B @ - + / . ;

Secretary

The secretary of ACMCZ has to write lots of letters: advertisements of trips, invitations, announcements, calling for participants, and also the letters to apology for bad meals, hotel swimming pool under reconstruction, or closed Internet Cafe in the venue of the trip. The computer and the text processor MS Byte is used for writing such letters. The director of the company would like to make work of the young secretary as simple as possible, because he would like to use her services also for some other activities. His proposal is based on an idea that the tesaurus of words used in the letters written by the secretary is limited. There is no problem to make a list of all the used words and the secretary can write only the beginning of each word, so she can eliminate writing a lot of characters. You have to write the program which will change this shortened text into the full version.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of two parts. First part are the words which are known by the secretary, second are the beginnings of words to be completed. At the first line of the first part there is a positive integer X, stating the number of words known by the secretary. Then X lines follow, each of them containing exactly one word. No word appears more than once in every list. The first line of the second part contains the positive integer Y. Then Y lines follow, each containing one string -- the beginning of some word to be complete.

Each word may be from 1 to 100 characters long and it can contain upper- and lower-case letters and digits. The total number of known words (X) is among the interval <1,1000>. The Number of uncomplete words (Y) is among the interval <1,10000>. The upper- and lower-case letters are consider to be different.

Output Specification

For each beginning of the word there must be exactly one line of output. If it is possible to complete the given string to a unique existing word from the first part of the assignment, output the sentence "Doplneno slovo XX." (Completed to word XX), where XX is the full word. If there are more than one word which could be completed, output the sentence "Detekovana kolize." (Collision detected). Finally, if there is no word beginning with the given string, output the sentence "Slovo nelze doplnit." (Word cannot be completed). It is also possible to complete the word by an empty string.

Sample Input

1
5
skola
skolnik
skoda
volkswagen
voltamper
10
sko
skod
skop
skoln
skolni
skolnikovo
v
volper
volk
volt

Output for Sample Input

Detekovana kolize.
Doplneno slovo skoda.
Slovo nelze doplnit.
Doplneno slovo skolnik.
Doplneno slovo skolnik.
Slovo nelze doplnit.
Detekovana kolize
Slovo nelze doplnit.
Doplneno slovo volkswagen.
Doplneno slovo voltamper.

Medical doctor

On the Fujutimoru Island in the Caribbean sea there appeared the new epidemy of unknown illness Philuktirus Pendoxis (Filctura). The illness is not very dangerous, but it is troublesome for ill people and for other people around them. There are such symptoms as sickness, depressions, ill people bite, cry, are furious and they use MS-Windows.

Researchers found out that Filctura may appear only by some persons, because the most people are immune. The test, if somebody may be or may not be infected by the disease, is a very reliable microbiology test, named by its founder, Greece researcher Postolomlatos. Because ACMCZ does not want to put its clients into the danger of Filctura, the agency is testing all clients before they leave to Fujutimoru.

Postolomlatos' method tests the blood using a very complicated way. This is out of interest of this problem, so we will mention no details about the method at all. But there are some important facts. At first, into the blood sample is added some number of Pendoxia Vulgaris bacteria, which causes the disease. Some of the bacteria are killed by the defense mechanisms of the blood corpuscles. It is the rate of killed and alive bacteria, by which the immunity is determined.

The special trained technician prepares the blood sample, adds the exact amount of bacteria to it, puts it on a testing glass, takes the picture by CCD camera and digitalizes the picture by camera software. The result is a black and white bitmap, where white pixels means background and black pixels are parts of the cells. The cell of a living bacteria looks always as coherent black area with exactly one white "hole". Dead cell is a coherent black area without any white hole. We can assume that no two cells are attached to each other, and that there are no other objects in a bitmap. All the pixels outside the bitmap are considered to be white i.e. all the cells are inside the bitmap and they are not crossing the bitmap border.

Write a program which determines in compliance with this bitmap how many cells are of the type A (living bacteria i.e. the area with one white hole) and how many cells are of the type B (dead bacteria i.e. area without any hole). For the purpose we will make an informal definition of notions:

Two pixels are attached to each other iff the sum of the absolute values of the difference between their X and Y coordinates is equal to one.

Path is a sequence of attached pixels.

Coherent area is the maximal set of the same color pixels, for which there exists at least one path between any two pixels considered to be the part of that area.

Coherent black area C contains a hole iff there exists some coherent white area D (a hole) for which any path connecting D with any other white area always cross some pixels of area C.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. Each assignment starts with the line containing two positive integers R and S, R<=1000000, S<=200, which represent the number of lines and columns of the bitmap. Then there are R lines representing the bitmap. Each of these line contain S characters representing the pixels, each of them is either 'X' (the black pixel) or '.' (the white pixel). The last pixel is immediately followed by the newline character.

Output Specification

For each assignment output a single containing the sentence "Nalezeno XX bunek typu A a YY bunek typu B." (XX cells of type A and YY cells of type B found). Replace XX and YY with the appropriate numbers.

Sample Input

1
3 7
XXX..XX
X.X.XX.
XXX....

Output for Sample Input

Nalezeno 1 bunek typu A and 1 bunek typu B

Farm

The most expensive and also the most attractive trip of ACMCZ travel agency is an airplane trip to Komolu in the Pacific ocean. This state is known by the farm Naopsi where natives rear a very special animal called Vertecholustosaurus, which replicates by "splitting". By each day the number of animals grow up K-times. The last day of the trip there is served the specialty - Vertecholustosaurus steak. The meat is very tasty, healthy and nutrition but also very expensive.

Naopsi Farm is very often visited by thieves which steal Vertecholustosauruses. From the thieves the animals are bought by shopkeepers but always only in boxes with X animals. Because the thieves are very rapacious they only steal the maximum number of animals which is divisible by X and they leave the rest of animals on the farm. The ACMCZ would like be sure that for the last day of the trip there will be enough Vertecholustosaurususes for the dinner (and there will be enough left for the next rear), so it needs a program which will calculate how many animals will remain on Naopsi, if we know that the farm was "visited" by thieves C-times in the times T1, T2, .... TC. You have to write the program which will find out how many animals will be on the farm after the last "visit" of thieves if we know that in "zero" time there were Z animals in the farm.

Input Specification

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 numbers separated by space. The first line contains the numbers Z, K, X, C, at the second line there are C numbers representing the times T1, T2, .... TC. The times make the non-decreasing sequence of exactly C non-negative integer numbers.

The limitations on the numbers are:

  • 1 <= X <= 40000
  • 1 <= K <= 40000
  • 1 <= Z <= 40000
  • 1 <= C <= 100

Output Specification

For each assignment there must be exactly one line of output containing the sentence "Na farme zbylo XX zivocichu." (There are XX animals left on the farm), where XX is the number of Vertecholustosaurususes which remain on the farm after last visit of thieves.

Sample Input

2
6 2 10 1
2
1 2 20000 2
4 15

Output for Sample Input

Na farme zbylo 4 zivocichu.
Na farme zbylo 12768 zivocichu.

Luggage

Travel agency ACMCZ cares about the luggage of clients during airplane trips. To simplify this task they put all luggage into containers. The containers have the shape of a cylinder with very small height (so called "pan cake"). The agency owns 30 containers with different sizes. Those containers are always filled by luggage, marked by labels with the names of the destination station, and they are loaded onto the plane. The airport crane is used for loading the luggage and an expansive rent must be paid for this. To save expenses the angency always arranges departure of 3 trips at the same time.

The crane has 3 platforms but they are very small so only one container can be placed on any platform. But containers are constructed in that way they can be laid one onto the another, so one platform can hold more than one container. We have to care about the containers during placing them onto the platforms, because the smaller container must always be put on the top of the greater one. In other way the containers and luggage could be damaged. And if some old lady with a lot of VIP friends has wrinkled her evening dress during the transport to the ski trip in the mountains, it may be very bad reputation for the travel agency.

At the beginning of loading, all the containers are put on a single platform, biggest one is on the bottom and smallest one on the top. First task of a "craneman" is to separate the containers by the destination station. During this manipulation (and also at the end of it) there may never be the bigger container put onto the smaller one.

You have to determine the smallest possible number of moves which must be obeyed to separate containers to all 3 platforms in that way, that there will be only the containers for one destination on each platform.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of exactly one line containing the numbers separated by spaces. Each assignment starts with the number of containers X and then X numbers follow on the same line, each is from the set {0,1,2} and represents the destination for one container. Destinations are assigned one by one to the containers starting with the bottom one (biggest) container. The number X will never be greater then 30.

Output Specification

For each assignment should the program generate exactly one line with sentence "Je treba XX presunu." (There is the need of XX movements), where XX is the minimum number of movements needed to separate all the containers in that way that all the containers with the same destination will be on the same platform and there will be no other containers with them.

Sample Input

3
5 1 1 1 1 1
2 1 2
3 0 1 1

Output for Sample Input

Je treba 0 presunu.
Je treba 1 presunu.
Je treba 3 presunu.

Competition

One of the best trips of travel agency ACMCZ is the trip to Programming Contest, which is held each year in Prague. Contest rules are very well known to you so we will not mention them here.

Adam and Karl decided they will participate in the contest with ACMCZ and they would like to win. They find out a new strategy: Adam will only analyze all the problems, Karl will do coding of them (it means to write them into the computer using the programming language miniFORTH). If any of these two friends starts to work on a problem, he always finishes it before starting anything else. That means he never works on two problems simultaneously and he never interrupts his work. Karl cannot start coding before Adam finishes analyzing of the problem.

Input Specification

At the first line there is a positive integer N stating the number of assignments to follow. The first line of each assignment contains the positive integer M, M <= 100000 representing the number of the problems in competition which should be solved. Then exactly M lines follow, each of them represents one problem and contains two positive integers A and B, A, B <= 1000000, stating the times in minutes needed for analyzing and coding the problem.

Output Specification

For each assignment there will be exactly one line of output with the sentence "Adam s Karlem budou hotovi nejdrive za XX minut." (Adam and Karl will be finished not sooner than in XX minutes), where XX is time in minutes. This time is the minimum time in which Adam and Karl could solve all the problems under all of the above conditions.

Sample Input

1
3
4 5
2 1
1 4

Output for Sample Input

Adam s Karlem budou hotovi nejdrive za 11 minut.

You are visitor number since June 2nd, 1998.