Czech ACM Student Chapter
CTU in Prague, Dept. of Computer Science and Engineering Charles University in Prague, MFF VİB TU Ostrava, FEI, Dept. of Computer Science SUT Bratislava, FEI, Dept. of Computer Science and Engineering
CTU Open 2004Congratulations! Your application for the position of A Chief Ment in our company was accepted and you have passed through the first round of evaluation. Of course you are not alone who is interested in getting this position, and unfortunately we may accept only one team for it. Therefore we have prepared a set of tasks of the similar nature as those you will meet on everyday basis in case you are the ones to be chosen, in order to test your skills. In few following hours, you are required to propose solutions for these problems. The team whose solutions will be the best ones, and who will be able to come up with them in the shortest time, will win this lucrative position. All of the programs will run in UNIX environment. Every program should read data from the standard input and send results to the standard output. The data format is given and must be exactly followed. There will be no extra spaces in the input and there should be no extra spaces and newlines in the output, if not stated otherwise. The endofline character is not considered a part of the line.
Contributions to the problem set:
AgentsThe topsecret organization Agency of C.M. (The agency is so secretive that nobody is allowed to know what C.M. was supposed to mean. The most common interpretation  ``Crazy Madmen''  is vehemently, but of course futilely, denied by leadership of the ACM.) was given a difficult mission. In order to complete the mission, all agents of ACM must be used. To make the situation worse, it is known that certain pairs of agents hate each other or simply do not work well together for some other reasons. Therefore to increase the efficiency, the leader of ACM has decided to split his subordinates to several teams, so that no such pair of agents belongs to the same team. The nature of the mission however makes it impossible to have more than three teams. At first this seemed to be an easy task, but he quickly noticed that there are some quite unpleasant persons in his organization. Such ``bad guys'' are of course necessary in this type of organizations, since there are tasks that simply cannot be solved in the ``gentle'' way. There used to be a lot more of them, but after recent reforms, the regulations only permit at most three (but at least one) such characters in the organization. Still, he found out that each normal (i.e. not bad guy) member of the organization hates at least one of these bad guys, which made him doubt that such a split is possible. Your task is to decide whether he is right with his doubts, or whether splitting the agents to at most three teams according to the criterion described above is possible.
Input SpecificationThe input consists of several instances. The first line of each instance contains two integers 1 A 500 and R 0 separated by a single space. A is the number of agents in the organization. Agents are assigned integers between 0 and A  1. R is the number of pairs of agents that hate each other. The following R lines of the instance describe these pairs. Each of the lines contains two integers 0 a_{1}, a_{2} < A separated by a single space, meaning that agents with numbers a_{1} and a_{2} hate each other. Every pair of agents that hate each other is described exactly once. An empty line follows each instance. The input is terminated by a line containing two zeros.
Output SpecificationThe output consists of several lines. The ith line of the output corresponds to the ith input instance. If it is possible to split the agents in the instance to at most three teams, the corresponding output line describes such a split. If there are several possible splits, then only one (arbitrary) of them is described. The line contains A integers {0, 1, 2} separated by single spaces, where the ith number is the number of the team to that the agent with number (i  1) is assigned. If it is not possible to split the agents in the instance so that no two persons in the same team hate each other, the corresponding output line consists of the string ``The agents cannot be split''.
Sample Input3 3 0 1 0 2 2 1 4 6 0 1 0 2 0 3 1 2 1 3 2 3 0 0
Sample Output0 1 2 The agents cannot be split
BoatherdsBoatherds Inc. is a sailing company operating in the country of Trabantustan and offering boat trips on Trabantian rivers. All the rivers originate somewhere in the mountains and on their way down to the lowlands they gradually join and finally the single resulting river flows to the sea. Moreover, the Trabantian villages are exactly at the rivers' springs, junctions and at the mouth of the largest river. Please note that more than 2 rivers can join at a junction. However, the rivers always form a tree (with villages as vertices). The pricing policy of the Boatherds is very simple: each segment of each river between two villages is assigned a price (the price is same in both directions), so if a tourist requests a journey between any two villages, the ticket office clerks just add the prices of the segments along the only path between the villages. One day, a very strange tourist appeared. She told the clerks that she returns to her country on the next day and she wants to spend all the remaining money on a boat trip, so they should find a route with exactly this cost. Being just poor (ahem) businessmen, they have asked the Abacus Calculator Makers for help. You are given a description of the river network with costs of river segments and a sequence of integers x_{1},..., x_{k}. For each x_{i}, you should determine if there is a pair of cities (a, b) in the river network such that the cost of the trip between a and b is exactly x_{i}.
Input SpecificationThe input consists of several instances. Each instance is described by (in the following order):
The whole input is ended by a single line containing the number 0.
Output SpecificationFor each instance you should produce a sequence of M lines (where M is the number of queries in the particular instance). The ith of these lines contains the word ``AYE'' if there exists a pair of cities in the river network which is connected by a path of cost x_{i}, or the word ``NAY'' otherwise. Output for each instance must be followed by a single line containing just the dot character.
Sample Input6 2 5 3 7 4 1 0 0 5 2 6 3 0 0 0 0 1 8 13 14 0 0
Sample OutputAYE AYE NAY AYE .
C LooooopsA Compiler Mystery: We are given a Clanguage style for loop of type
for (variable = A; variable != B; variable += C) statement; I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a kbit unsigned integer type (with values 0 x < 2^{k}) modulo 2^{k}.
Input SpecificationThe input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 k 32) is the number of bits of the control variable of the loop and A, B, C (0 A, B, C < 2^{k}) are the parameters of the loop. The input is finished by a line containing four zeros.
Output SpecificationThe output consists of several lines corresponding to the instances on the input. The ith line contains either the number of executions of the statement in the ith instance (a single integer number) or the word FOREVER if the loop does not terminate.
Sample Input3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0
Sample Output0 2 32766 FOREVER
Death to Binary?The group of Absurd Calculation Maniacs has discovered a great new way how to count. Instead of using the ordinary decadic numbers, they use Fibonacci base numbers. Numbers in this base are expressed as sequences of zeros and ones similarly to the binary numbers, but the weights of bits (fits?) in the representation are not powers of two, but the elements of the Fibonacci progression (1, 2, 3, 5, 8,...  the progression is defined by F_{0} = 1, F_{1} = 2 and the recursive relation F_{n} = F_{n1} + F_{n2} for n 2). For example 1101001_{Fib} = F_{0} + F_{3} + F_{5} + F_{6} = 1 + 5 + 13 + 21 = 40. You may observe that every integer can be expressed in this base, but not necessarily in a unique way  for example 40 can be also expressed as 10001001_{Fib}. However, for any integer there is a unique representation that does not contain two adjacent digits 1  we call this representation canonical. For example 10001001_{Fib} is a canonical Fibonacci representation of 40. To prove that this representation of numbers is superior to the others, ACM have decided to create a computer that will compute in Fibonacci base. Your task is to create a program that takes two numbers in Fibonacci base (not necessarily in the canonical representation) and adds them together.
Input SpecificationThe input consists of several instances, each of them consisting of a single line. Each line of the input contains two numbers X and Y in Fibonacci base separated by a single space. Each of the numbers has at most 40 digits. The end of input is not marked in any special way.
Output SpecificationThe output for each instance should be formated as follows: The first line contains the number X in the canonical representation, possibly padded from left by spaces. The second line starts with a plus sign followed by the number Y in the canonical representation, possibly padded from left by spaces. The third line starts by two spaces followed by a string of minus signs of the same length as the result of the addition. The fourth line starts by two spaces immediately followed by the canonical representation of X + Y. Both X and Y are padded from left by spaces so that the least significant digits of X, Y and X + Y are in the same column of the output. The output for each instance is followed by an empty line.
Sample Input11101 1101 1 1
Sample Output100101 + 10001  1001000 1 + 1  10
ElectricityBlackouts and Dark Nights (also known as ACM++) is a company that provides electricity. The company owns several power plants, each of them supplying a small area that surrounds it. This organization brings a lot of problems  it often happens that there is not enough power in one area, while there is a large surplus in the rest of the country. ACM++ has therefore decided to connect the networks of some of the plants together. At least in the first stage, there is no need to connect all plants to a single network, but on the other hand it may pay up to create redundant connections on critical places  i.e. the network may contain cycles. Various plans for the connections were proposed, and the complicated phase of evaluation of them has begun. One of the criteria that has to be taken into account is the reliability of the created network. To evaluate it, we assume that the worst event that can happen is a malfunction in one of the joining points at the power plants, which might cause the network to split into several parts. While each of these parts could still work, each of them would have to cope with the problems, so it is essential to minimize the number of parts into which the network will split due to removal of one of the joining points. Your task is to write a software that would help evaluating this risk. Your program is given a description of the network, and it should determine the maximum number of nonconnected parts from that the network may consist after removal of one of the joining points (not counting the removed joining point itself).
Input SpecificationThe input consists of several instances. The first line of each instance contains two integers 1 P 10 000 and C 0 separated by a single space. P is the number of power plants. The power plants have assigned integers between 0 and P  1. C is the number of connections. The following C lines of the instance describe the connections. Each of the lines contains two integers 0 p_{1}, p_{2} < P separated by a single space, meaning that plants with numbers p_{1} and p_{2} are connected. Each connection is described exactly once and there is at most one connection between every two plants. The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.
Output SpecificationThe output consists of several lines. The ith line of the output corresponds to the ith input instance. Each line of the output consists of a single integer C. C is the maximum number of the connected parts of the network that can be obtained by removing one of the joining points at power plants in the instance.
Sample Input3 3 0 1 0 2 2 1 4 2 0 1 2 3 3 1 1 0 0 0
Sample Output1 2 2
FirepersonsThe Association for Courtly Manners, an international organization for standardization of social interactions (Better known under the name Absurdly Clumsy Moralists, but let's not take prejudice.) has decided to create a new international standard defining ranks of firepersons (Formerly firemen, but the international standards of course must be politically correct.)  each fireperson receives an integer number describing his rank and when they arrive to a fire, they must enter the fire ground in order of increasing ranks and the low ranked firepersons must keep the fire burning long enough for the high ranked firepersons to enjoy extinguishing sufficiently. The ranks are assigned according to an Arbitrary Constant Multiplier Sequence. An ACMsequence of order k is an integer sequence defined by its first k terms a_{0}, a_{1},...a_{k1} and a recurrence relation mod 10 000 for n k, where the b_{i}'s are integer constants. The ith oldest fireperson then gets rank a_{i}. Your task is to calculate the rank of the ith fireperson, given parameters of the ACMsequence and the number i.
Input SpecificationThe input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a_{0}, , a_{k1}, b_{1}, , b_{k}, i. Here 1 k 100 is the order of the sequence, 0 a_{i} < 10 000 are the first k elements of the sequence, 0 b_{i} < 10 000 are the multipliers and 0 i < 1 000 000 000 is the number of the element we ask for. The input ends with a line containing a number 0.
Output SpecificationThe output consists of several lines corresponding to the instances on the input. The lth line contains a single integer a_{i} which is the ith element of the sequence described by the lth input instance.
Sample Input2 0 1 1 1 6 0
Sample Output8
God of the Vile BaskersA not very famous writer Arthur Conan Moyle has finally found out why his books are not as popular as he believes they would deserve. He noticed that his works are getting a bit boring due to frequent repetitions of same or similar pieces of text. He decided that the best way how to improve the quality of his books is to simply throw away everything after the first repetition  the books then get an interesting openended feeling. First he attempted to look for exactly same pieces of text, but this failed, since the repeated texts often do not match precisely  some of letters that are lowercase in the first place may be uppercase in the second and vice versa, punctuation may be a bit different, and even the words in sentences may be in slightly different order. To overcome these problems, he devised the following more involved criterion for recognizing duplicates (a positive integer k is a parameter of his criterion; by changing it he affects how long repeated pieces are still acceptable): Alphabetic characters are the letters 'a''z' and 'A''Z'. We do not distinguish case of the letters, i.e. 'a' is supposed to be the same letter as 'A'. Two strings S_{1} and S_{2} are kidentical up to permutation of letters if:
In other words, if the strings S_{1} and S_{2} are kidentical up to permutation of letters, then the alphabetic characters in them are the same, but their ordering may be different. Your task is to write a program that separates a longest initial part that does not contain two substrings kidentical up to permutation of letters from several of the ACM's books.
Input SpecificationThe input consists of several instances. Each instance is described by two lines. The first line of the instance consists of an integer number 1 k 50. The second line of the instance consists of the string T. Length of T is at most 100 000 characters. The string T may contain nonalphabetic characters including spaces, but it does not contain any characters with special meaning (i.e. with ASCII code smaller than 32). The input is terminated by a line containing a zero.
Output SpecificationThe output consists of several lines. The ith line of the output corresponds to the ith input instance. The line a single integer number  length of the longest prefix P (including all nonalphabetic characters) of the string T of the corresponding instance such that P does not contain two distinct, but not necessarily nonoverlapping, substrings S_{1} and S_{2} that are kidentical up to permutation of letters.
Sample Input4 a'B'C'd'x'a'b'c'd 4 abcdabcd 0
Sample Output16 4
HerbalistsA group of herbalists has decided to move to a new village on the boundary of a huge forest. The arrangement of houses and paths in the village turned out to be a major problem: Many of the herbalists are friends and want to visit each other often, so they want to have a path between their houses. However the herbalists are also known for quarreling with everyone else. To avoid the chance of meeting with someone they do not like, it is required that no two paths intersect  there should be no crossroads in the village (And of course also no other means of crossing; overpasses spoil the scenery and underpasses destroy the root systems of precious herbs.) . Each herbalist also wants to be able to visit the forest, of course without having to cross any path  i.e., it is also necessary to make it possible to get from each house to ``infinity'' without crossing a path. You are given a description of the relationships between herbalists. Your task is to decide whether such an ideal village can be built.
Input SpecificationThe input consists of several instances. The first line of each instance contains two integers 1 H 10 000 and F 0 separated by a single space. H is the number of herbalists. The herbalists have assigned integers between 0 and H  1. F is the number pairs of friends. The following F lines of the instance describe the pairs of friends. Each of the lines contains two integers 0 h_{1}, h_{2} < H separated by a single space, meaning that herbalists with numbers h_{1} and h_{2} are friends. Each pair of friends is described exactly once. The instances follow each other immediately, without any separator. The input is terminated by a line containing two zeros.
Output SpecificationThe output consists of several lines. The ith line of the output corresponds to the ith instance. If it is possible to build a village for the corresponding input instance, the output line consists of ``Yes, village can be built'' string. If it is not possible to build such a village, the output line consists of ``No, village cannot be built'' string.
Sample Input3 3 0 1 0 2 1 2 4 6 0 1 0 2 0 3 1 2 1 3 2 3 0 0
Sample OutputYes, village can be built No, village cannot be built
InglishNumber TranslatorIn this problem, you will be given one or more integers in English. Your task is to translate these numbers into their integer representation. The numbers can range from negative 999,999,999 to positive 999,999,999. The following is an exhaustive list of English words that your program must account for: negative, zero, one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand, million
Input SpecificationThe input consists of several instances. Notes on input:
The input is terminated by an empty line.
Output SpecificationThe answers are expected to be on separate lines with a newline after each.
Sample Inputsix negative seven hundred twenty nine one million one hundred one eight hundred fourteen thousand twenty two
Sample Output6 729 1000101 814022
Japan Plotter DriverThe Japan company you are working for produce plotter devices that can draw nice pictures. To support customers who do not posses the special hardware, you were asked to write an emulation driver that simulates the work of the plotter and prints the picture on a computer screen. The plotter is driven with a simple language consisting of several drawing commands:
The emulation driver uses few ASCII characters to represent the picture, one character being a basic unit of the coordinate system. The topleft character has coordinates (1,1). The Xaxis aims to the right, the Yaxis goes down. The particular commands are emulated as follows:
If more objects should be drawn across a single character, the following rules apply:
Before a script is given to the driver, it is checked by a special preprocessor, which rejects all invalid commands. Therefore, you may assume that all coordinates are within the range of the page. Also, with the LINE command, the two points are always different and the line is strictly either vertical, horizontal, or at the angle of 45^{o} to the axes. There is no assumption on the relative position of the points used with the LINE and CLEAR commands. The text in the TEXT command is always composed only of uppercase letter and digits.
Input SpecificationThe input consists of several scripts. Each script begins with a line containing two integers X and Y, separated with space, 1 X, Y 75. These numbers specify the dimensions of the page. Every other line contains exactly one of the above commands. The commands are always uppercase, command arguments are separated with one space. The PRINT command is always the last command of the script. After the PRINT command, a new script begins. The input is terminated with two zeros, which are not considered to be a script.
Output SpecificationFor each script, output the emulated picture, created as specified above. After the picture, print one blank line.
Sample Input20 10 LINE 3 2 11 10 LINE 3 10 11 2 LINE 20 3 8 3 TEXT 6 8 TEST LINE 19 1 19 10 LINE 17 10 17 1 LINE 16 1 16 10 LINE 13 6 20 6 CLEAR 20 5 15 7 LINE 18 1 18 10 TEXT 12 10 NICEPICTURE POINT 1 1 POINT 3 2 PRINT 1 1 POINT 1 1 CLEAR 1 1 1 1 PRINT 3 3 LINE 2 1 2 3 LINE 1 2 3 2 LINE 2 3 2 1 LINE 3 2 1 2 LINE 2 1 2 3 LINE 1 2 3 2 PRINT 0 0
Sample Output++ o    * /    \ *++++  \ /    \ /    x     / \    /TES*    / \    / \NICE****U ++ ++   ++ ++    +    ++
