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 2004 Congratulations! 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 end-of-line character is not considered a part of the line.         in out PostScript solution Agents a.in a.out a.ps a.c Boatherds b.in b.out b.ps b.c C Looooops c.in c.out c.ps c.c Death to Binary? d.in d.out d.ps d.c Electricity e.in e.out e.ps e.c Firepersons f.in f.out f.ps f.c God of the Vile Baskers g.in g.out g.ps g.c Herbalists h.in h.out h.ps h.c Inglish-Number Translator i.in i.out i.ps i.C Japan Plotter Driver j.in j.out j.ps j.C all.tgz (10MB) Contributions to the problem set: -   Charles University Prague   University of Valladolid's "English-Number Translator"   CTU Prague Agents a.in, a.out, a.ps, a.c The top-secret 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 Specification The 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 a1, a2 < A separated by a single space, meaning that agents with numbers a1 and a2 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 Specification The output consists of several lines. The i-th line of the output corresponds to the i-th 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 i-th 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 Input 3 3 0 1 0 2 2 1 4 6 0 1 0 2 0 3 1 2 1 3 2 3 0 0 Sample Output 0 1 2 The agents cannot be split Boatherds b.in, b.out, b.ps, b.c Boatherds 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 x1,..., xk. For each xi, 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 xi. Input Specification The input consists of several instances. Each instance is described by (in the following order): A single line containing a single integer: the number of villages N (1 N 10 000). N lines describing the villages. The i-th of these lines (1 i N) describes the village with number i. It contains space separated integers d1, c1, d2, c2, , dki, cki, 0. The dj's are numbers of villages from which the rivers flow directly to the village i (with no other villages in between), each cj is the price of the journey between villages i and dj. Moreover, 2 dj N and 0 cj 1 000. Village 1 always corresponds to the mouth of the largest river, therefore no di can ever be equal to 1. M 100 lines describing the queries. The i-th of these lines corresponds to the i-th query and contains a single integer xi (1 xi 10 000 000). The instance is finished by a single line containing the number 0. The whole input is ended by a single line containing the number 0. Output Specification For each instance you should produce a sequence of M lines (where M is the number of queries in the particular instance). The i-th 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 xi, or the word ``NAY'' otherwise. Output for each instance must be followed by a single line containing just the dot character. Sample Input 6 2 5 3 7 4 1 0 0 5 2 6 3 0 0 0 0 1 8 13 14 0 0 Sample Output AYE AYE NAY AYE . C Looooops c.in, c.out, c.ps, c.c A Compiler Mystery: We are given a C-language 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 k-bit unsigned integer type (with values 0 x < 2k) modulo 2k. Input Specification The 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 < 2k) are the parameters of the loop. The input is finished by a line containing four zeros. Output Specification The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate. Sample Input 3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0 Sample Output 0 2 32766 FOREVER Death to Binary? d.in, d.out, d.ps, d.c 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 F0 = 1, F1 = 2 and the recursive relation Fn = Fn-1 + Fn-2 for n 2). For example 1101001Fib = F0 + F3 + F5 + F6 = 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 10001001Fib. However, for any integer there is a unique representation that does not contain two adjacent digits 1 - we call this representation canonical. For example 10001001Fib 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 Specification The 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 Specification The 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 Input 11101 1101 1 1 Sample Output 100101 + 10001 ------- 1001000 1 + 1 -- 10 Electricity e.in, e.out, e.ps, e.c Blackouts 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 non-connected parts from that the network may consist after removal of one of the joining points (not counting the removed joining point itself). Input Specification The 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 p1, p2 < P separated by a single space, meaning that plants with numbers p1 and p2 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 Specification The output consists of several lines. The i-th line of the output corresponds to the i-th 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 Input 3 3 0 1 0 2 2 1 4 2 0 1 2 3 3 1 1 0 0 0 Sample Output 1 2 2 Firepersons f.in, f.out, f.ps, f.c The 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 ACM-sequence of order k is an integer sequence defined by its first k terms a0, a1,...ak-1 and a recurrence relation mod 10 000 for n k, where the bi's are integer constants. The i-th oldest fireperson then gets rank ai. Your task is to calculate the rank of the i-th fireperson, given parameters of the ACM-sequence and the number i. Input Specification The input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a0, , ak-1, b1, , bk, i. Here 1 k 100 is the order of the sequence, 0 ai < 10 000 are the first k elements of the sequence, 0 bi < 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 Specification The output consists of several lines corresponding to the instances on the input. The l-th line contains a single integer ai which is the i-th element of the sequence described by the l-th input instance. Sample Input 2 0 1 1 1 6 0 Sample Output 8 God of the Vile Baskers g.in, g.out, g.ps, g.c A 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 open-ended 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 S1 and S2 are k-identical up to permutation of letters if: Both S1 and S2 start and end with an alphabetic character Both S1 and S2 contain exactly k alphabetic characters For each alphabetic character c, the string S1 contains the same number of occurrences of c as the string S2. In other words, if the strings S1 and S2 are k-identical 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 k-identical up to permutation of letters from several of the ACM's books. Input Specification The 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 non-alphabetic 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 Specification The output consists of several lines. The i-th line of the output corresponds to the i-th input instance. The line a single integer number - length of the longest prefix P (including all non-alphabetic characters) of the string T of the corresponding instance such that P does not contain two distinct, but not necessarily non-overlapping, substrings S1 and S2 that are k-identical up to permutation of letters. Sample Input 4 a'B'C'd'x'a'b'c'd 4 abcdabcd 0 Sample Output 16 4 Herbalists h.in, h.out, h.ps, h.c A 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 Specification The 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 h1, h2 < H separated by a single space, meaning that herbalists with numbers h1 and h2 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 Specification The output consists of several lines. The i-th line of the output corresponds to the i-th 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 Input 3 3 0 1 0 2 1 2 4 6 0 1 0 2 0 3 1 2 1 3 2 3 0 0 Sample Output Yes, village can be built No, village cannot be built Inglish-Number Translator i.in, i.out, i.ps,, i.C In 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 Specification The input consists of several instances. Notes on input: Negative numbers will be preceded by the word negative. The word ``hundred'' is not used when ``thousand'' could be. For example, 1500 is written ``one thousand five hundred'', not ``fifteen hundred''. The input is terminated by an empty line. Output Specification The answers are expected to be on separate lines with a newline after each. Sample Input six negative seven hundred twenty nine one million one hundred one eight hundred fourteen thousand twenty two Sample Output 6 -729 1000101 814022 Japan Plotter Driver j.in, j.out, j.ps, j.C The 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: POINT x y -- makes a little circle at the given coordinates. TEXT x y txt -- displays a line of text at the given coordinates. LINE x1 y1 x2 y2 -- draws a line between the specified points. CLEAR x1 y1 x2 y2 -- erases the given rectangle. PRINT -- prints an output page and terminates the current job. The emulation driver uses few ASCII characters to represent the picture, one character being a basic unit of the coordinate system. The top-left character has coordinates (1,1). The X-axis aims to the right, the Y-axis goes down. The particular commands are emulated as follows: POINT: The driver puts a lowercase letter "o" at the given coordinates. TEXT: Shows a single line of text, the first character is positioned at the given coordinates and the text always goes right. LINE: Simulates a straight line between two points. The line is formed by one of the following characters: dash ("-"), pipe ("|"), slash ("/"), or backslash ("\"), according to its direction. CLEAR: The driver fills the appropriate rectangular area with spaces, including the bounding rows and columns. PRINT: This command causes the driver to print the picture surrounded with a nice frame made of plus ("+"), minus ("-"), and pipe ("|") characters. If more objects should be drawn across a single character, the following rules apply: If the same character is drawn several times, it is used without a change. If only pipe and minus characters are involved, they result in the plus sign ("+"). If only slashes and backslashes are involved, the result is the lowercase letter "x". Otherwise, the asterisk ("*") is displayed. 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 45o 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 Specification The 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 Specification For each script, output the emulated picture, created as specified above. After the picture, print one blank line. Sample Input 20 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| +--------------------+ +-+ | | +-+ +---+ | | | |-+-| | | | +---+