|  |
|
Department of Computer Science, CTU FEE & Czech ACM Chapter CTU Open Programming Contest 1997 Travel agency ACMCZWhen 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...
AirportWhile 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 SpecificationAt 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 Output SpecificationThe program should output exactly one line for each assignment. The line
should contain the sentence " Sample Input3 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 InputCesta je prujezdna. Cesta neni prujezdna. Cesta neni prujezdna. 
TermTravel 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 SpecificationAt 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 SpecificationFor each assignment there must be exactly one output line with the
sentence " Sample Input3 3 6 2 3 2 9 2 1 1 3 1 1 2 1 1 2 1 3 2 8 1 Output for Sample InputNejvhodnejsi termin zacina 3. dnem. Nejvhodnejsi termin zacina 1. dnem. Nejvhodnejsi termin zacina 6. dnem.
CompilerTravel 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:
Identifier of a variable is exactly one capital letter
( Arithmetical expression is one of the following possibilities:
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:
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 SpecificationAt 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 SpecificationFor 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 Input2 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 @ - + / . ;
SecretaryThe 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 SpecificationAt 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 SpecificationFor 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 " Sample Input1 5 skola skolnik skoda volkswagen voltamper 10 sko skod skop skoln skolni skolnikovo v volper volk volt Output for Sample InputDetekovana 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 doctorOn 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 SpecificationAt 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 ' Output SpecificationFor each assignment output a single containing the sentence
" Sample Input1 3 7 XXX..XX X.X.XX. XXX.... Output for Sample InputNalezeno 1 bunek typu A and 1 bunek typu B
FarmThe 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 SpecificationAt 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:
Output SpecificationFor each assignment there must be exactly one line of output containing
the sentence " Sample Input2 6 2 10 1 2 1 2 20000 2 4 15 Output for Sample InputNa farme zbylo 4 zivocichu. Na farme zbylo 12768 zivocichu.
LuggageTravel 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 SpecificationAt 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 SpecificationFor each assignment should the program generate exactly one line with
sentence " Sample Input3 5 1 1 1 1 1 2 1 2 3 0 1 1 Output for Sample InputJe treba 0 presunu. Je treba 1 presunu. Je treba 3 presunu.
CompetitionOne 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 SpecificationAt 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 SpecificationFor each assignment there will be exactly one line of output with the
sentence " Sample Input1 3 4 5 2 1 1 4 Output for Sample InputAdam s Karlem budou hotovi nejdrive za 11 minut. |
| You are visitor number | since June 2nd, 1998. |