Central European Olympiad in Informatics 2004 University of Information Technology and Management, July 2004, Rzeszów, Poland 

(Original version of this document can be found at http://cs.science.upjs.sk/ceoi/)
(Cluj, Romania) Day 2: Black or white  Odd and even  Expressions For the purposes of computer graphics a part of the screen is always coded by a positive integer consisting only of digits 1, 2, 3, 4. See the pictures: Normalised square * is coded by 133, normalised square + is coded by 343. There is no limit on the scale of the normalised squares. If you want to shift square * to the place +, you may shift it for example 4 times down and then 2 times to the right. Write a program into the file SQUARE.PAS which does repeatedly the following: a) Reads a code of a normalised square from one line of the input file SQUARE.DAT as a positive integer, consisting only of digits 1,2,3,4 and a sequence of shifts L (left), R (right), U (up), D (down) as a sequence of letters L, R, U, D from the next line of the input file SQUARE.DAT. b) Writes the final position of the normalised square into the output file SQUARE.RES or writes message OUT OF THE BORDER c) Writes an empty line into the output file SQUARE.RES, until an empty line is read. In each data set, the number of digits in the code is less or equal to 35. The time limit is at most 1 minute for each data set.
Example If the file SQUARE.DAT contains 133 DDDDRR 1 DD the output file SQUARE.RES should contain 343 Let n be a positive integer. We consider an ordering <, called lexicographic ordering, defined on the subsets of {1,2,...,n}. Let S_{1} = {x_{1},...,x_{i}} and S_{2} = {y_{1},...,y_{j}} be two distinct subsets of {1,2,...,n} with x_{1}<x_{2}<...<x_{i} and y_{1}<y_{2}<...<y_{j}. Then we say that S_{1}<S_{2} if there exists k with 0<=k<=min{i,j} such that x_{1}=y_{1},...,x_{k}=y_{k} and either k=i or x_{k+1}<y_{k+1}. For example, the subsets of {1,2,3} listed in lexicographic order are: {} 1 {1} 2 {1,2} 3 {1,2,3} 4 {1,3} 5 {2} 6 {2,3} 7 {3} 8 The lexicographic ordering associates to each subset a natural number, as shown in the above example. Your program should read lines from an ASCII file called P6.TXT. Each line has one of the following forms: 1 n k 2 n k1 k2 . . . ki If the line has the first form, you have to print on the display the subset of {1,2,...,n} whose associated number is k (supposing that k<=2^{n}). If the line is of the second form, you have to print the number associated with the subset {k1,...,ki} of {1,...,n} (supposing that 1<=k1<k2< ...<ki<=n). Your program should be able to produce the answer for each input line in at
most 3 minutes, assuming that n<=30. We construct objects according to the following rules: 1. The initial object is a square with the side equal to 1; 2. A new object is obtained concatenating two objects on the side which has the same length. 3. Each time a new object is constructed, it is supposed that an infinite instances of this object are available. Requirements: 1) A positive integer n is introduced from the keyboard. Display the number of objects having the area at most n, which can be constructed if only two objects of the same dimensions will be concatenated. Two objects with the same dimensions are conside"#008DDC" identical. For example, a valid output for n=20 is: (1,1) (2,1) (4,2) (8,2) (16,3) where in each pair the first number represents the area of an object and the second one represents the number of distinct objects having this area. 2) The same requirements must be satisfied when we are allowed to concatenate objects of different dimensions, according to the rules 1  3. For example, a valid output for n=10 is: (1,1) (2,1) (3,1) (4,2) (5,1) (6,2) (7,1) (8,2) (9,2) (10,2) the pairs having the same meaning as in requirement 1). The input is a single line introduced from the keyboard, containing a pair: i n where i is a member of {1,2}, meaning the number of the requirement and n is the above specified integer number. The output is a text file containing pairs of elements, as shown above. The maximum value for n is 10000. Your program should be able to produce the
answer for each data test in at most 1 minute. Write a program which reads three positive integers n, p, q. Decide whether or not there exists a sequence of n integers such that the sum of any p consecutive elements is positive and the sum of any q consecutive ones is negative. If the answer is YES, your program has to produce such a sequence. The values of n, p, q are read from the keyboard; the output consists of NO or YES followed by a sequence of n integers written on display.
Example 1 If the input is n=4 p=2 q=3 the output is NO Example 2 If the input is n=6 p=5 q=3the output is YES 3 5 3 3 5 3 Let us consider a country with N towns. A system of roads formed from direct connections between towns is given; all these direct connections are conside"#008DDC" to have the length equal to 1. This system is called evenodd if there are two towns linked by a road of even length, as well as by a road of odd length. a) Find out if the system of roads is evenodd or not. b) If the answer for a) is negative, find one of the subsets X of towns which has a maximal number of elements and satisfies the following condition: for any two towns in X, if there is a path linking them, then its length is even. The name of the input file is introduced from the keyboard. Its first line contains the value of N; the following lines contain pairs I, J with the meaning that the towns I and J are directly linked. The value of N is at most 300. Display the output on the screen in an intelligible form. Examples If the input file contains 1 2 2 3 3 4 4 5 5 1a valid output is YESIf the input file contains: 1 2then a valid output is: NO X has 2 elements X: 2 3 An expression contains additions and multiplications. The time needed to evaluate an addition (+) is p and the time needed for a multiplication (*) is q. The time needed to evaluate the expression AoB is equal to the time needed to evaluate the operation o plus the maximum of the times needed to evaluate the subexpressions A, and B respectively. The operands are variables consisting of a single character, whose evaluation time is conside"#008DDC" as being equal to 0. Write a program which reads data from an input file that contains the values of p and q and expressions, each expression on a separate line. The parentheses are used compulsory to indicate the order of operations. For each expression one asks: a) To find and print the time needed to evaluate that expression; b) To find and print an equivalent arithmetic expression with a minimum evaluation time, as well as this minimum evaluation time on next line. The equivalent transformations permitted are: The results must be printed in the output file that contains an empty line between two expressions. For example, if the input file contains: 1 1 ((a+(b+(c+d)))*e)*f ((((a*b)*c)*d)+e)+(f*g)then the output file must be: 5 ((a+b)+(c+d))*(e*f) 3 5 (((a*b)*(c*d))+e)+(f*g) 4 (Szeged, Hungary) Day 2: Garden  Party  Measuring glasses A computer records the starting and finishing time of each application
program in the measure of 1/100 seconds. A daily statistic is a set of pairs (a,
b) of non negative integers such that 0<a<=b<8640000. The pair (a, b)
means that a program started at time a and finished at time b. The time points a
and b belong to busy time. Arbitrary number of programs can run in parallel.
Write a program that computes Input data The first line of text file DAY1A.DAT contains N, the number of the intervals (1<=N<=1000). Each of the rest N lines of the file contains two non negative integers, the starting and finishing time of a program. Output Data The text file DAY1A.SOL has to contain the following two integers in this order: a) The length (ba+1) of the largest interval of time when the machine was idle. b) The length (dc+1) of the largest closed time interval when the machine executed at least one program. Example input 9 30000 35000 10000 20000 15000 16000 40000 44000 77000 220000 13000 41000 60000 67000 50000 55000 65000 70000 Example output In our example input the DAY1A.SOL file contains the following two lines: 8419999 143001 The students of a class have decided to form an alarm chain. Every student chooses a unique successor, to whom he directly delivers received messages. Whenever a student receives a message forwards it to his or her successor. Such an assignment is called an alarm chain if the following holds. Suppose somebody sends a message to his or her successor, who in turns transmits the message to his or her successor, etc. The message eventually arrives to every student, including the starting student. Clearly, not every assignment is alarm chain. Write a program which for an arbitrary input assignment, computes the minimal number of necessary modifications that transforms the input assignment to an alarm chain. Input data The first line of the text file DAY1B.DAT contains N, the number of the students (1<=N<256). Each of the following N lines contains two names (strings) separated by the character '>'. The second name terminated by endofline character. The names are at most 20 characters long. A line of the form A>B means that the successor of student A is B, i.e. A directly delivers messages to B. Output Data Write the minimal number of necessary modifications to the text file DAY1B.SOL as an integer. Example input 10 Anita>Peter Andrew>Julia David>Andrew Natalie>Gabriella Edith>David Peter>Anita Gabriella>Julius Adam>David Julia>Gabriella Julius>Julia Example output 4 Two brothers, Alan and Bob want to share a set of gifts. Each of the gifts should be given to either Alan or Bob, and none of the gifts can be split. Each gift has a positive integer value. Let A and B denote the total value of gifts received by Alan and Bob, respectively. The aim is to minimise the absolute value of the difference AB. Write a program which computes the values A and B. Input data The first line of the text file DAY1C.DAT contains N, the number of the gifts (1<=N<= 100). The rest of the input contains N positive integers, the values of the gifts. Each value is <=200. Output Data Write the two integers A and B to the text file DAY1C.SOL. Example input 7 28 7 11 8 9 7 27 Example output 48 49 There are N trees in a garden. The shape of the garden is square with 1000 m long sides. We are looking for a rectangle with largest area that does not contain trees inside. The sides of the rectangle must be parallel to the corresponding sides of the garden. Each side of the rectangle may contain trees and may lie on a side of the garden. Trees are given by (x,y) coordinates of their positions measu"#008DDC" in meter. A tree is conside"#008DDC" to be a point without extension. The origin of the coordinate system is the lower left corner of the garden and the axes are parallel to the sides. Input data The first line of text file DAY2A.DAT contains N, the number of the trees (1<=N<=600). In each of the next N lines you will find integer coordinates (x, y) (0<x<1000, 0<y<1000), the positions of the trees. Output Data Write the area of the largest rectangle as an integer value in the text file DAY2A.SOL. Example input 7 280 100 200 600 400 200 135 800 800 400 600 800 900 210 Example output 360000 The president of a company is organising a party for his employees. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. In order to make the party fun for all attendees, the president does not want both an employee and his or her supervisors to sit at the same table. The problem is to compute the minimal number of tables necessary to make a seating arrangement that satisfies the above requirement. The input of the program is the immediate supervisor relation of the company. The supervisor relation is defined in terms of the immediate supervisor relation as follows. A person P is supervisor of a person Q if P is the immediate supervisor of Q, or there are persons P_{1}, ..., P_{k} (1<k) such that P=P_{1}, Q=P_{k} and P_{i} is the immediate supervisor of P_{i+1} (i=1, ..., k1). The number of attendees is N (1<=N<=200), and there are T (2<=T<=10) seats at each table. Input data The employees of the company are identified by the first N (1<=N<=200) natural numbers. The president of the company is identified by number 1, and has no supervisor. The first line of the text file DAY2B.DAT contains T, the number of seats per table (2<=T<=10). The second line contains the number N (1<=N<=200) of the attendees, each employee identified by numbers from 1 to N will attend the party. In the third line you find N numbers. The ith number in the line is the immediate supervisor of the ith person. The first number in the line is 0, indicating that the president has no supervisor. Output Data Write the minimal number of tables needed to seat all attendees in the specified way in the text file DAY2B.SOL. Example input 4 13 0 1 9 9 9 2 2 1 1 7 8 8 10 Example output 5 We are given three glasses. The volume of each glass is 100 unit (cm^{3}). The first two glasses have marks, same on both glasses, each mark indicating the volume measu"#008DDC" from the bottom up to the mark. That volume is written beside the mark.
Initially the first glass contains 100 unit volume of fluid, and the others are empty. Write a program that decides whether one unit volume of fluid can be separated in the third glass, and if so, computes the minimal number of steps needed to do it. In each step, after the operation at least one of the used glass must contain fluid up to a mark or empty. During the procedure we can keep track of the actual contents of each three glasses. Input data The first line of the text file DAY2C.DAT contains N, the number of the marks on the first two glasses (1<=N<=20). The rest of the file contains N integers in increasing order; that is the volumes corresponding to the marks on the glasses. For each volume mark V the inequalities (1<=V<=100) hold and the largest value is 100. Output Data Write the string YES into the first line of the text file DAY2C.SOL if one unit can be separated in the third glass and write NO otherwise. If the answer is yes for the first question then write the minimal number of steps in the second line. Example input 4 13 37 71 100 Example output YES 8 (Bratislava, Slovakia) Day 2: Bin Packing  Cutting Rectangles  Electrician A kind of grid is sometimes used for encoding messages. Our naval fleet officials decide to use this kind of encoding messages for communication with their ship captains. The encoding grid is a square sheet of paper divided into 2N x 2N little squares. N^{2} of little squares are cut out (see figure 1). Let us briefly describe the encoding process. Take text of message of length 4N^{2}. Then put an encoding grid onto a blank sheet of paper and begin to write first N^{2} letters of message into the cut little squares (one letter per square, write letters in all cut squares in the first line from left to right, then in the second line etc.). See example on figure 2 for message "HELLOYELLOWWORLD". After finishing the first step rotate the encoding grid 90 degrees clockwise and continue similarly writing letters. After two more steps all letters should be written (see example on figure 3). O### H### HOOY ##O# ##E# LREO O##O L##L LWEL #### #### LLDW (fig. 1) (fig. 2) (fig. 3) It is necessary to have a correctly constructed grid. It means that when it is used in the way described above after each rotation new N^{2} blank squares will appear under cut squares of the grid. The naval fleet officials encoded thousands of messages with their grid and then they wanted to send them to ships. Unfortunately they lost the grid. Fortunately the naval admiral remembe"#008DDC" the original text of one of the messages. Your task is to get this original message text and encoded text and find one possible correctly constructed encoding grid with which the message text could have been encoded. Input Data The first line of input file contains an integer N (1<=N<=10). The second line contains 4N^{2} capital letters representing the original message. The next 2N lines contain the encoded text (each line 2N capital letters). Output Data The output file contains a correctly constructed grid with which given message could have been encoded. In each of 2N lines one line of grid (2N characters) will be displayed where "O" (capital letter 'O' represents cut square and "#" uncut square). Example GRID.IN 2 HELLOYELLOWWORLD HOOY LREO LWEL LLDWGRID.OUT O### ##O# O##O #### The Palmia country is divided by a river into the north and south bank. There are N towns on both the north and south bank. Each town on the north bank has its unique friend town on the south bank. No two towns have the same friend. Each pair of friend towns would like to have a ship line connecting them. They applied for permission to the government. Because it is often foggy on the river the government decided to prohibit intersection of ship lines (if two lines intersect there is a high probability of ship crash). Your task is to write a program to help government officials decide to which ship lines they should grant permission to get maximum number of non intersecting ship lines. Input Data The input file consists of several blocks. In the first line of each there are 2 integers X,Y separated with exactly one space, X represents the length of the Palmia river bank (10 <= X <= 6000), Y represents the width of the river (10 <= Y <= 100). The second line contains the integer N, the number of towns situated on both south and north riverbanks (1 <= N <= 5000). On each of the next N lines there are two nonnegative integers C,D separated with space (C,D <= X), representing distances of the pair of friend towns from the western border of Palmia measu"#008DDC" along the riverbanks (C for the town on the north bank, D for the town on the south bank). There are no two towns on the same position on the same riverbank. After the last block there is a single line with two numbers 0 separated by a space. Output Data For each block of the input file the output file has to contain in consecutive lines the maximum possible number of ship lines satisfying the conditions above. Example SHIPS.IN 30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0SHIPS.OUT 4 In Palmia country they have N cities connected by highways (each highway connects exactly two cities in both directions). It is possible to reach every city from any other city using one or several highways. Till this year the highway tolls were collected on highways. In the middle of each highway there was a toll collector who collected 1 Palmia Coin (1 PC) from each car passing by. Government officials decided to "#008DDC"uce the number of toll collectors and introduce highway stamps. If a car will want to enter a highway it must have this higway stamp placed on the window. Officials decided that the highway stamp for one year will cost the same as 100 travels between two farthest cities. The distance between two cities is the minimum number of highways you need to use to get from the first city to the second one. Your task is to write a program which computes the cost of the highway stamp. Input Data The input file consists of several blocks of data. Each block at the first line contains the integers N and M separated by a space where N is the number of cities and M the number of highways in Palmia country (1<= N <= 1000, 1 <= M <= 2000). Cities are numbe"#008DDC" by integers from 1 to N. The next M lines contain each one pair of integers A,B (1<= A,B <= N) separated by a space representing that there is a highway between the cities A and B. After the last block there is a single line with two numbers 0 separated by a space. Output Data For each block of input file the output file contains a single line with the cost of the highway stamp. Example TOLLS.IN 4 4 1 2 2 3 4 2 3 4 0 0TOLLS.OUT 200 A factory has a bin packing robot at the end of an assembly line. There are exactly two bins open, and the robot packs items into any one of the open bins, one by one sequentially. The bins are identical, and one bin can accommodate a set of items up to a given weight limit. More precisely, the robot can perform the following four instructions:
A pack instruction can only be executed if the weight of the current item plus the sum of the weights of the items already in the bin does not exceed the limit. You are given the sequence of weights of items and a weight limit that is constant for all the bins. Write a program that computes the minimal number of bins needed by the robot to pack all items into them. Input Data The input file contains integer numbers. The first line of input file contains the weight limit L (1 <= L <= 100). This limit applies to all bins. The second line contains the number of items N (1 <= N <=5000). Each of the following N lines contains the weight of an item. Each weight is at least 1 and at most L. Output Data Write on the first line of output file the minimum number of bins needed to pack all items. Example BINPACK.IN 8 6 4 2 5 3 5 4BINPACK.OUT 3 You are given a rectangle whose side lengths are integer numbers. You want to cut the rectangle into the smallest number of squares, whose side lengths are also integer numbers. Cutting can be performed with a cutting machine that can cut only from side to side across, parallel with one side of the rectangle. Obtained rectangles are cut separately. Input Data The input file contains two positive integers in the first line: the lengths of the sides of the rectangle. Each side of the rectangle is at least 1 and at most 100. Output Data The output file consist of one line on which your program should write the number of squares resulting from an optimal cutting. Example CUTS.IN 5 6CUTS.OUT 5 The electrician Fero has just finished the installation of the new cable in the building of the CEOI secretariat. The cable consists of N wires and connects the computer room and CEOI secretary office. In the computer room Fero labeled the wires with numbers from 1 to N from left to right. Because the cable was long, sometimes some of wires crossed between the computer room and the office (each pair of wires crosses at most once; at each moment only neighbouring wires may cross). So in the office the wires were not orde"#008DDC" the same way (see figure 1). To know how these wires are crossed Fero drew the graph on the wall near the cable end in the computer room. The vertices represented wires and edges represented wire crosses. There is an edge between vertices a and b if and only if the wires a and b are crossed somewhere on the way (see figure 2 for graph representing situation in figure 1). The cable does not function properly now. Unfortunately Fero broke his leg yesterday. We have another electrician but he is not so experienced in graph theory. He needs to know the order of wires at the end of the cable in the CEOI secretary office to correct this fault.
Input Data In the input file there are several blocks of data. The first line of each block contains two numbers N and M separated by a space, where N (1<= N <= 100) is the number of wires in the cable and M is the number of wire crosses. This is followed by M lines each containing pair of integers A, B separated by a space (1 <= A,B <= N) representing the cross of cable wires A and B somewhere on the way. After the last block there is a line with two numbers 0. Output Data For each block of the input file the output file contains a single line with the list of wire numbers in order as they appear at the second end of the cable (N numbers separated by space) or the message "IMPOSSIBLE" if no order is represented by given graph. Example ELECTRIC.IN 5 4 1 2 1 3 2 3 1 4 0 0ELECTRIC.OUT 3 2 4 1 5 (Nowy Sacz, Poland) Day 2: Integer Intervals  River Crossing  Shooting Contest There is a lot of caves in Byteland. This is the map of one of them: All caves in Byteland have the following properties:
It has been decided to open all the caves to the public. To assure a "smooth" and safe flow through a cave, visitors should follow a route marked in advance and visit every chamber of this cave exactly once. An exception from this rule is the entrance chamber where every tour begins and ends, you are allowed to visit this chamber exactly twice. The tour route should be fit for an average visitor and contain as few hard passages to walk through as possible. Example Consider the cave showed in the figure. The entrance chamber is 1. The dashed passages are hard to walk through. Route 1, 5, 4, 6, 8, 7, 2, 3 contains no hard passages at all. The final chamber, number 1, is implied and not listed. Task Write a program that:
Input There are two integers n, k (separated by a single space) in the first line of the text file CAV.IN. The integer n, 3 < n <= 500, is the number of all chambers in a cave and k is the number of all its outer chambers, k >= 3. The chambers are numbe"#008DDC" from 1 to n. Chamber 1 is the entrance chamber. Chambers 1, 2, ..., k are outer chambers. They do not have to appear on the outer circle in this order. The next 3n / 2 lines contain descriptions of the passages. Each description consists of three integers a, b, c separated by single spaces. The integers a and b are numbers of chambers at the ends of a passage. The integer c equals 0 or 1, where 0 means that the passage is easy to walk through and 1 that it is hard. Output Your program should write a sequence of n integers separated by single spaces to the first line of the text file CAV.OUT; the sequence has to begin with 1 (the entrance chamber). The following n  1 integers should be consecutive chambers on the computed route. Example For the text file CAV.IN: 8 5 1 3 0 3 2 0 7 3 1 7 2 0 8 7 0 1 8 0 6 8 0 6 4 0 6 5 1 5 4 0 2 4 0 5 1 0one of the correct solutions is the text file CAV.OUT: 1 5 4 6 8 7 2 3 A domino is a flat, thumbsized tile, the face of which is divided into two squares, each left blank or bearing from one to six dots. There is a row of dominoes laid out on a table:
The number of dots in the top line is 6+1+1+1=9 and the number of dots in the bottom line is 1+5+3+2=11. The gap between the top line and the bottom line is 2. The gap is the absolute value of difference between two sums. Each domino can be turned by 180 degrees keeping its face always upwards. What is the smallest number of turns needed to minimise the gap between the top line and the bottom line? For the figure above it is sufficient to turn the last domino in the row in order to decrease the gap to 0. In this case the answer is 1. Task Write a program that:
Input The first line of the text file DOM.IN contains an integer n, 1 <= n <= 1000. This is the number of dominoes laid out on the table. Each of the next n lines contains two integers a, b separated by a single space, 0 <= a, b <= 6. The integers a and b written in the line i + 1 of the input file, 1 <= i <= 1000, are the numbers of dots on the ith domino in the row, respectively, in the top line and in the bottom one. Output Your program should write exactly one integer to the first line of the text file DOM.OUT; this integer should be the smallest number of turns needed to minimise the gap between the top line and the bottom line. Example For the text file DOM.IN: 4 6 1 1 5 1 3 1 2the correct solution is the text file DOM.OUT: 1 The base of the hexadecimal system is 16. In order to write down numbers in this system one uses 16 digits 0,1,...,9,A,B,C,D,E,F. The capital letters A,..,F stands for 10,..,15, respectively. For instance the value of the hexadecimal number CF2 is 12 * 16^{2} + 15 * 16 + 2 = 3314 in the decimal system. Let X be the set of all positive integers whose hexadecimal representations have at most 8 digits and do not contain repetitions of any digit. The most significant digit in such a representation is not zero. The largest element in X is the number with the hexadecimal representation FEDCBA98, the second largest is the number FEDCBA97, the third is FEDCBA96 and so forth. Task Write a program that:
Input The first line of the file HEX.IN contains integer n in the decimal representation. Output Your program should write the nth largest element in X in the hexadecimal representation to the first line of the text file HEX.OUT Example For the text file HEX.IN: 11the correct solution is the text file HEX.OUT: FEDCBA87 An integer interval , a < b, is a set of all consecutive integers beginning with a and ending with b. Task Write a program that:
Input The first line of the text file INT.IN contains the number of intervals n, 1<=n<=10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval. Output Your program should write one integer to the first line of the text file INT.OUT; this should be the minimal number of elements in a set containing at least two different integers from each interval. Example For the text file INT.IN: 4 3 6 2 4 0 2 4 7the correct solution is the text file INT.OUT: 4 Citizens of Byteland adore all sports in which logical thinking is as important as physical skills. One of these sports is crossing the Hex River  the widest river in Byteland. There are n poles numbe"#008DDC" 1, ..., n (from left to right) stretching across the river. The citizens have to cross the river by going from the left bank to one pole perhaps to another and so on and then to the right bank. The left bank is located one pole to the left of pole 1; the right bank is located one pole to the right of pole n. At time 0, the citizen is on the left bank of the Hex River with the goal of reaching the right bank of the river as quickly as possible. At any given time, each pole is either up or down and the citizen is standing on a pole or standing on a bank of the river. A citizen can stand on a pole only if it is up; such a pole is available. Each pole is down at time 0 and then spends a time units up, b time units down, a time units up, b time units down, etc. The constants a and b are defined separately for each pole. For example the pole with a=2 and b=3 will be down at time 0, up at time 1 and 2, down at time 3, 4, 5 and so on. At time t+1, a citizen can choose to be on any available pole or river bank within 5 poles of his location at time t or even to stay on his current pole (if available) or bank. For example from pole 5 you can reach any of the poles 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 or the left bank. Task Write a program that:
Input The first line of the input file RIV.IN contains the number of data blocks x, 1 <= x <= 5. The following lines comprise the x blocks. The first block starts on the second line of the input file; each subsequent block starts directly after the previous one. The first line of each block contains an integer n, 5 < n <= 1000, the number of poles. Each of the following n lines in the block contains two integers a, b separated by a single space, 1 <= a, b <= 5. The integers in line i + 1 (in the block), 1 <= i <= n, describe the behaviour of the pole i. Output For the kth block, 1 <= k <= x, write to the kth line of the text file RIV.OUT the first time the citizen can reach the right bank or the word NO, when such a crossing is impossible. Example For the text file RIV.IN: 2 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1the correct solution is the text file RIV.OUT: NO 4 Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a target which is a rectangular grid. The target consists of r*c squares located in r rows and c columns. The squares are colou"#008DDC" white or black. There are exactly two white squares and r2 black squares in each column. Rows are consecutively labelled 1,..,r from top to bottom and columns are labelled 1, ..., c from left to right. The shooter has c shots. A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists. Example Consider the following target:
Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct. Task Write a program that:
Input The first line of the input file SHO.IN contains the number of data blocks x, 1 <= x <= 5. The following lines constitute x blocks. The first block starts in the second line of the input file; each next block starts directly after the previous one. The first line of each block contains two integers r and c separated by a single space, 2 <= r <= c <= 1000. These are the numbers of rows and columns, respectively. Each of the next c lines in the block contains two integers separated by a single space. The integers in the input line i + 1 in the block, 1 <= i <= c, are labels of rows with white squares in the ith column. Output For the ith block, 1 <= i <= x, your program should write to the ith line of the file SHO.OUT either a sequence of c row labels (separated by single spaces) forming a correct volley of hits at white squares in consecutive columns 1, 2, ..., c, or one word NO if such a volley does not exists. Example For the text file SHO.IN: 2 4 4 2 4 3 4 1 3 1 4 5 5 1 5 2 4 3 4 2 4 2 3one of the correct solutions is the text file SHO.OUT: 2 3 1 4 NO (Zadar, Croatia) Day 2: Soldiers  Roads  Ball Cake Contest Problem We are given N squares in the coordinate plane whose sides are parallel to the coordinate axes. All the corners have integer coordinates and the squares do not touch or overlap. You are requi"#008DDC" to count the number of squares visible from the origin point O, O = (0,0). A square is visible from the origin point O if there are two distinct points A and B on one of its sides such that the interior of the triangle OAB has no common points with any of the remaining squares. Input data The first line of the input file SQUARES.IN contains the integer N, 1<=N<=1000, the number of squares. Each of the following N lines describes a square by specifying integers X, Y and L separated by single blank characters, 1<=X,Y,L<=10000. X and Y are coordinates of the lower left corner (the corner with the least X and Y coordinates) and L is the side length. Output data The first and the only line of the output file SQUARES.OUT should contain the number of squares that are visible from the origin. Examples SQUARES.IN 3 2 6 3 1 4 1 3 4 1SQUARES.OUT 3SQUARES.IN 4 1 2 1 3 1 1 2 4 2 3 7 1SQUARES.OUT 2 Alice and Bob have a set of N cards labelled with numbers 1 ... N (so that no two cards have the same label) and a shuffle machine. We assume that N is an odd integer. The shuffle machine accepts the set of cards arranged in an arbitrary order and performs the following operation of double shuffle: for all positions i, 1<=i<=N, if the card at the position i is j and the card at the position j is k, then after the completion of the operation of double shuffle, position i will hold the card k. Alice and Bob play a game. Alice first writes down all the numbers from 1 to N in some random order: a_{1}, a_{2}, ..., a_{N}. Then she arranges the cards so that the position a_{i} holds the card numbe"#008DDC" a_{i+1}, for every 1<=i<=N1, while the position a_{N} holds the card numbe"#008DDC" a_{1}. This way, cards are put in some order x_{1}, x_{2}, ..., x_{N}, where x_{i} is the card at the i^{th} position. Now she sequentially performs S double shuffles using the shuffle machine described above. After that, the cards are arranged in some final order p_{1}, p_{2}, ..., p_{N} which Alice reveals to Bob, together with the number S. Bob's task is to guess the order x_{1}, x_{2}, ..., x_{N} in which Alice originally put the cards just before giving them to the shuffle machine. Input data The first line of the input file CARDS.IN contains two integers separated by a single blank character: the odd integer N, 1<=N<=1000, the number of cards, and the integer S, 1<=S<=1000, the number of double shuffle operations. The following N lines describe the final order of cards after all the double shuffles have been performed such that for each i, 1<=i<=N, the (i+1)^{st} line of the input file contains p_{i} (the card at the position i after all double shuffles). Output data The output file CARDS.OUT should contain N lines which describe the order of cards just before they were given to the shuffle machine. For each i, 1<=i<=N, the i^{th} line of the output file should contain x_{i} (the card at the position i before the double shuffles). Examples CARDS.IN 5 2 4 1 5 3 2CARDS.OUT 2 5 4 1 3CARDS.IN 7 4 6 3 1 2 4 7 5CARDS.OUT 4 7 5 6 1 2 3 We are given a sequence of N positive integers a = [a_{1}, a_{2}, ..., a_{N}] on which we can perform contraction operations. One contraction operation consists of replacing adjacent elements a_{i} and a_{i+1} by their difference a_{i}a_{i+1}. For a sequence of N integers, we can perform exactly N1 different contraction operations, each of which results in a new (N1) element sequence. Precisely, let con(a,i) denote the (N1) element sequence obtained from by replacing the elements a_{i} and a_{i+1} by a single integer a_{i}a_{i+1}: con(a,i) =Applying N1 contractions to any given sequence of N integers obviously yields a single integer. For example, applying contractions 2, 3, 2 and 1 in that order to the sequence con( con( con( Given a sequence a_{1}, a_{2}, ..., a_{N} and a target number T, the problem is to find a sequence of N1 contractions that applied to the original sequence yields T. Input data The first line of the input file SUBTRACT.IN contains two integers separated by blank character: the integer N, 1<=N<=100, the number of integers in the original sequence, and the target integer T, 10000<=T<=10000. The following N lines contain the starting sequence: for each i, 1<=i<=N, the (i+1)^{st} line of the input file contains integer a_{i}, 1<=a_{i}<=100. Output data Output file SUBTRACT.OUT should contain N1 lines, describing a sequence of contractions that transforms the original sequence into a single element sequence containing only number T. The i^{th} line of the output file should contain a single integer denoting the i^{th} contraction to be applied. You can assume that at least one such sequence of contractions will exist for a given input. Examples SUBTRACT.IN 4 5 10 2 5 2SUBTRACT.OUT 1 2 1SUBTRACT.IN 5 4 12 10 4 3 5SUBTRACT.OUT 2 3 2 1 N soldiers of the land Gridland are randomly scatte"#008DDC" around the country. A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move  in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or 1). The soldiers want to get into a horizontal line next to each other (so that their final positions are (x,y), (x+1,y), ..., (x+N1,y), for some x and y). Integers x and y, as well as the final order of soldiers along the horizontal line is arbitrary. The goal is to minimise the total number of moves of all the soldiers that takes them into such configuration. Two or more soldiers must never occupy the same position at the same time. Input data The first line of the input file SOLDIERS.IN contains the integer N, 1<=N<=10000, the number of soldiers. The following N lines of the input file contain initial positions of the soldiers: for each i, 1<=i<=N, the (i+1)^{st} line of the input file contains a pair of integers x separated by a single blank character, representing the coordinates of the i^{th} soldier, 10000<=x<=10000. Output data The first and the only line of the output file SOLDIERS.OUT should contain the minimum total number of moves that takes the soldiers into a horizontal line next to each other. Examples SOLDIERS.IN 3 1 0 2 4 3 2SOLDIERS.OUT 4SOLDIERS.IN 5 1 2 2 2 1 3 3 2 3 3SOLDIERS.OUT 8 N cities named with numbers 1 ... N are connected with oneway roads. Each road has two parameters associated with it: the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away  to the city N. He wants to get there as quickly as possible, but he is short on cash. We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has. Input data The first line of the input file ROADS.IN contains the integer K, 0<=K<=10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2<=N<=100, the total number of cities. The third line contains the integer R, 1<=R<=10000, the total number of roads. Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters:
Output data The first and the only line of the output file ROADS.OUT should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, only number 1 should be written to the output file. Examples ROADS.IN 5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2ROADS.OUT 11ROADS.IN 0 4 4 1 4 5 2 1 2 1 0 2 3 1 1 3 4 1 0ROADS.OUT 1 Professor Balltazar is a big football fan. His birthday was just a couple of days before he was going to leave for the World Cup Football '98 in France, so his friends gave him as a present a dodecahedronshaped puzzle as an entertainment while watching the boring games. The puzzle has 12 equal pentagon sides, labelled with numbers 1, ..., 12. The figure below shows the two hemispheres of the dodecahedron, together with the side labelling we will use in this problem. Hemispheres are "glued" together in such a way that the side 7 is adjacent to the sides 8, 12, 11, 2 and 6 (sides are adjacent if they share an edge). In particular, edges a and b on the left hemisphere will be glued to the edges a and b on the right hemisphere shown below. In addition to that, there are 12 pentagonshaped tiles, also labelled from 1 to 12. Every edge on each of the tiles is marked with a number from the set {0, 1, 2}. Each tile can be placed on each of the twelve sides in any of the 5 positions obtained by rotating the tile around its centre. To solve the puzzle, we need to put each tile on some of the twelve dodecahedron sides in some position, so that every two adjacent tiles have their common edge marked with the same number. Help Professor Balltazar to solve the puzzle! Input data The input file BALL.IN contains 12 lines. For each i, 1<=i<=12, the i^{th} line describes the i^{th} tile by specifying 5 numbers from the set {0, 1, 2} separated by single blank characters. This sequence shows the edge marking of the i^{th} tile starting from an arbitrary edge (called the i^{th} reference edge) going in the clockwise direction. Output data Output file BALL.OUT should contain the description of a solved puzzle in 12 lines with 2 integers in each line. For each i, 1<=i<= 12, the i^{th} line should contain integers t separated by a single blank character describing the tile and its position on the i^{th} side: The i^{th} side will hold the tile labelled t. The tile can be placed on the i^{th} side in five different positions. The exact position is specified by n, which denotes the label of the adjacent side which is in the direction of the t^{th} reference edge (looking from the centre of the i^{th} side). Precisely, the t^{th} reference edge is placed on the dodecahedron edge sha"#008DDC" by the sides labelled i and n. If the puzzle can not be solved, only number 1 should be written to the output file. Examples BALL.IN 0 0 1 1 2 0 2 1 0 1 2 0 1 0 1 0 0 1 2 1 0 2 1 1 2 2 0 1 2 1 0 2 1 2 1 2 2 1 0 1 1 2 2 0 0 0 2 1 0 2 0 2 1 2 0 2 0 1 2 0BALL.OUT 1 2 3 7 12 4 7 9 9 1 11 8 8 2 4 6 5 4 2 12 6 3 10 7BALL.IN 1 0 2 0 2 2 2 2 1 2 1 1 0 0 0 1 1 0 2 1 2 1 1 1 1 1 2 2 1 1 2 1 2 2 1 2 2 0 1 0 0 1 2 1 2 2 2 1 0 0 1 2 0 2 0 2 2 2 0 1BALL.OUT 1 2 2 7 8 2 7 1 11 4 12 2 5 2 3 12 10 5 9 3 6 10 4 7 (The Cake Contest was a special competition for teams, were they should think of the best problem for CEOI competition. Here’s the winning problem:) N participants of the CEOI should be transported to a national park. They travel in B busses with L seating rows of S seats each, with N<=(B*L*S). The distance between two people sitting next to each other is 1. The distance between people sitting in the same row but not next to each other is 2 and the distance between people sitting M rows apart from each other, but in the same bus, is (M+1). People in different busses always have a distance of 20. Your goal is to maximise the happiness of the CEOI participants. Each participant has a certain favourite distance to those participants he or she already knows. Participants do not care about distances to people they do not yet know. Global happiness is the sum over all individual happinesses. Individual happiness of a participant is calculated as follows: An actual distance matching the favourite distance increases the happiness of the participant by 30. The happiness decreases by the difference between actual and favourite distance. If, for example, Alice prefers sitting in a distance of 5 to Bob, while Bob is sitting 3 rows in front of Alice, i.e. at a distance of 4, happiness of Alice will be increased by 29. Note that the favourite distance from Alice to Bob can differ from the favourite distance from Bob to Alice. Since we are at a CEOI, no individual happiness will become less than 0. Input data The first line of the input file VOTE4ME.IN contains the positive integers N<=10000, B<=100, L<30 and S <= 10. The following N lines of the input file contain N numbers each. The number I, 0<= I <= 30, in column U and row V is the distance that participant V would like participant U to sit. The favourite distance from a participant to him/herself is always 0; instead of real distances to people he or she does not know, the input file will contain the special value 1. Output data The output file VOTE4ME.OUT must consist of N lines, line j, 1<=j<=N containing the happiness of person j in an optimal sitting plan. An optimal sitting plan is one that maximises the global happiness. Example VOTE4ME.IN 4 1 3 2 0 5 1 2 1 0 1 1 2 1 0 6 3 1 1 0VOTE4ME.OUT 25 29 26 30 (Brno, Czech Republic) Day 2: Phone numbers  Sightseeing trip  Orders On the chessboard of size 4x4 there are 8 white and 8 black stones, i.e. one stone on each field. Such a configuration of stones is called a game position. Two stones are adjacent if they are on fields with a common side (i.e. they are adjacent in either horizontal or vertical direction but not diagonal). It means that each stone has at most 4 neighbours. The only legal move in our game is exchanging any two adjacent stones. Your task is to find the shortest sequence of moves transforming a given starting game position into a given final game position. Input The starting game position is described in the first 4 lines of input file GAME.IN. There are 4 symbols in each line, which define the colour of each stone in the row from the left to the right. The lines describe the rows of the chessboard from the top to the bottom. Symbol '0' means a white stone and symbol '1' a black one. There is no space symbol separating the symbols in the line. The fifth line is empty. The next 4 following lines describe the final game position in the same way. Output The first line of output file GAME.OUT contains the number of the moves. The following lines describe the sequence of moves during the game. One line describes one move and it contains 4 positive integers R_{1}C_{1}R_{2}C_{2} separated by single spaces. These are the coordinates of the adjacent fields for the move, i.e. fields , where R_{1} (or R_{2}) is the number of the row and C_{1} (or C_{2}) is the number of the column. The rows on the chessboard are numbe"#008DDC" from 1 (top row) to 4 (bottom row) and the columns are numbe"#008DDC" from 1 (the leftmost column) to 4 (the rightmost one) as well (i.e. the coordinates of the left upper field are ). If there are multiple shortest sequences of moves transforming the starting position to the final position, you can output any one of them. Example: GAME.IN 1111 0000 1110 0010GAME.OUT 1010 0101 1010 0101 Children like playing with blocks (cube wooden bricks). They usually build high towers, but small Johny dreams of different plans. He is going to build a big town. His daddy has bought him a rectangular table; its width is K blocks and its length is L blocks exactly. Johny decided to project a plan of such a town before he starts building the town itself. He has drawn a squareshaped network on the table consisting of KxL squares. He wants to place the towers consisting of one or more blocks on some of the squares of the network drawn; the remaining squares will be empty. Because of the table being so large, Johny is not going to plan exactly for every square how many blocks he will put on it. He only wants to decide about front and right sight shapes of his town. He drew these two views (twodimensional projections of the planned town) on a paper. You can see an example of these drawings and the adequate town made of wooden bricks in the pictures:
Johny's daddy is afraid they don't have enough blocks to finish building Johny's planned town. You are asked for writing a program to compute the minimal and maximal amount of blocks with which a town corresponding to Johny's plans can be built. Moreover the program can decide about the possibility of building a town satisfying the views. Input The first line of input file TOWN.IN contains two positive integers K, L  the width and the length of the table (expressed as numbers of bricks). Neither the width nor the length of the table is greater than 100000 bricks. The following lines of the input file contain the description of the front view of the town. The description consists of a series of heights of visible buildings on each square from the left to the right (the height is measu"#008DDC" by the number of the blocks, too). There is only one number on each line, i.e. the number of the lines with the front view description of the town equals K  the width of the table. Similarly the next L lines of the input file contain the right sight view of the town. The heights of the wooden block towers are now specified from the front line to the back line. You may suppose there is no building in the town with height exceeding 5000 blocks. The maximal number of blocks needed for building the entire town does not exceed 2000000000. Output Output file TOWN.OUT contains only one line. If it is not possible to build a town with the front and right sight views given, only a text `No solution.' is written there. In the other case two numbers will be written on the line and separated by a single space. The first one is the minimal and the second one is the maximal amount of blocks small Johny can use to build his town in accordance with his project. Example 1 TOWN.IN 4 3 1 3 4 2 1 4 2TOWN.OUT 10 21 Example 2 TOWN.IN 2 2 4 1 1 3TOWN.OUT No solution. Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers. You suspect some of your friend's answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer. Input The first line of input file PARITY.IN contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal to 1000000000. In the second line, there is one positive integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5000. The remaining lines specify questions and answers. Each line contains one question and the answer to this question: two integers (the position of the first and last digit in the chosen subsequence) and one word which is either 'even' or 'odd' (the answer, i.e. the parity of the number of ones in the chosen subsequence, where `even' means an even number of ones and 'odd' means an odd number). Output There is only one line in output file PARITY.OUT containing one integer X. Number X says that there exists a sequence of zeroes and ones satisfying first X parity conditions, but there exists none satisfying X+1 conditions. If there exists a sequence of zeroes and ones satisfying all the given conditions, then number X should be the number of all the questions asked. Example 1 PARITY.IN 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 oddPARITY.OUT 3 Example 2 PARITY.IN 10 5 1 2 even 1 4 even 2 4 odd 1 10 even 3 10 evenPARITY.OUT 5 In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method how to do it in an easy way is to assign letters to digits as shown in the following picture: 1 ij 2 abc 3 def 4 gh 5 kl 6 mn 7 prs 8 tuv 9 wxy 0 oqzThis way every word or a group of words can be assigned a unique number, so you can remember words instead of call numbers. It is evident that it has its own charm if it is possible to find some simple relationship between the word and the person itself. So you can learn that the call number 941837296 of a chess playing friend of yours can be read as WHITEPAWN, and the call number 2855304 of your favourite teacher is read BULLDOG. Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above. Input The first line of input file PHONE.IN contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB. Output The only line of output file PHONE.OUT contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text 'No solution.'. If there are more solutions having the minimum number of words, you can choose any single one of them. Example There is only one solution to the input file PHONE.IN containing 7325189087 5 it your reality real ourwritten in the output file PHONE.OUT, which is reality our(next possibility 'real it your' corresponding to the same number is longer). If the number is 4294967296the only correct result is: No solution.because no given word contains letters g and h which are necessary to obtain the digit 4. There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route. In the town there are N crossing points numbe"#008DDC" from 1 to N and M twoway roads numbe"#008DDC" from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_{1}, ..., y_{k}, k>2. The road y_{i} (1<=i<=k1) connects crossing points x_{i} and x_{i+1}, the road y_{k} connects crossing points x_{k} and x_{1}. All the numbers x_{1},...,x_{k} should be different. The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_{1})+L(y_{2})+...+L(y_{k}) where L(y_{i}) is the length of the road y_{i} (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible, because there is no sightseeing route in the town. Input The first line of input file TRIP.IN contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500). Output There is only one line in output file TRIP.OUT. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x_{1} to x_{k} from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them. Example 1 TRIP.IN 5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20TRIP.OUT (one of correct answers) 1 3 5 2 Example 2 TRIP.IN 4 3 1 2 10 1 3 20 1 4 30TRIP.OUT (the only correct answer) No solution. The stores manager has sorted all kinds of goods in an alphabetical order of their labels. All the kinds having labels starting with the same letter are sto"#008DDC" in the same warehouse (i.e. in the same building) labelled with this letter. During the day the stores manager receives and books the orders of goods which are to be delive"#008DDC" from the store. Each order requires only one kind of goods. The stores manager processes the requests in the order of their booking. You know in advance all the orders which will have to be processed by the stores manager today, but you do not know their booking order. Compute all possible ways of the visits of warehouses for the stores manager to settle all the demands piece after piece during the day. Input Input file ORDERS.IN contains a single line with all labels of the requested goods (in random order). Each kind of goods is represented by the starting letter of its label. Only small letters of the English alphabet are used. The number of orders doesn't exceed 200. Output Output file ORDERS.OUT will contain all possible orderings in which the stores manager may visit his warehouses. Every warehouse is represented by a single small letter of the English alphabet  the starting letter of the label of the goods. Each ordering of warehouses is written in the output file only once on a separate line and all the lines containing orderings have to be sorted in an alphabetical order (see the example). No output will exceed 2 megabytes. Example ORDERS.IN bbjdORDERS.OUT bbdj bbjd bdbj bdjb bjbd bjdb dbbj dbjb djbb jbbd jbdb jdbb (Cluj, Romania) Day 2: Falling  Sticks  Enlightened landscape All the inhabitants of the planet X build their houses in a triangular shape. In order to save time and effort, they use a special construction method. Everything starts with a straight wall. After that, for the construction of every new house they just add two new walls to an already existing wall, thus resulting in a closed, triangular shaped house. Of course, the two new added walls might also be used as starting walls for new houses. Sometimes, using this construction pattern, they arrive at situations where some houses are completely enclosed in others (like in the figure). However, this is not a problem, because kids might live in the included houses. To light up their houses, the Xhabitants install a light bulb on every corner of the final construction (a bulb in a corner is common to all the houses sharing that corner). On each corner, there is a switch whose touch toggles the state (on/off) of the bulb from both that corner and also that of all the bulbs of the connected corners. Two corners are conside"#008DDC" connected if they are placed at the end of the same wall. Write a program that finds a switch touch sequence that will turn on all the light bulbs, starting from a given state. Input File name: X.IN Output File name: X.OUT Example X.IN 6 1 3 1 4 1 5 2 3 2 4 3 4 3 6 4 5 4 6 0 1 1 1 0 0X.OUT 1 6In the figure below you can see a possible building steps for the example file; the labels for the bulbs initially illuminated are underlined.
The Romanian Ministry of Transport decides to upgrade the Romanian roads. Each road is bidirectional and directly connects two towns. No two towns are directly connected by more than one road. The existing road network ensures direct or indirect links between any two towns in Romania. However, upgrading the roads implies closing, in turn, each road and performing the necessary repairs. During these operations, it is necessary to preserve the road network connectivity. In order to do so, the Minister decides that new roads should be built, so that no matter which single road is closed at any given moment (exactly one road at a time), the traffic between any given pair of towns should still be possible. Of course, the number of these newly added roads should be minimized. Furthermore, no new road may directly connect two directly connected towns. Write a program that determines the minimum number of the additional roads to be built and the pairs of towns to be connected with them. If there are several optimal solutions, only one is requi"#008DDC". Input File name: ROADS.IN Output File name: ROADS.OUT Remark The order of town pairs in the output file is irrelevant. Example ROADS.IN 4 3 1 2 2 3 2 4ROADS.OUT 2 1 4 1 3 Definition:
The chain is not necessarily unique. For example, another possible chain for the second caterpillar is 3259. Given a caterpillar with N nodes, write a program which labels the nodes with numbers from 1 to N such that: each label from 1 to N is used exactly once and no two edges in the tree have the same absolute value of the difference between the labels of their adjacent nodes. For the second caterpillar above, a possible labeling is indicated below along with the corresponding differences on the edges: Input File name: CP.IN Output File name: CP.OUT Limits 2<=N<=10000 Example The following input (CP.IN) describes the caterpillar from the Figure 2 and the output (CP.OUT) the labeling from the Figure 3. CP.IN 9 1 2 6 5 5 7 4 2 2 3 8 5 2 5 5 9CP.OUT (one possible solution) 8 1 5 2 9 4 6 3 7 Consider a game based on the device shown in the image below: From a given position, a ball is released in free fall at moment 0. The ball falls at a constant speed of 1 meter per second. When the ball reaches a platform it starts rolling towards one or the other of its edges, at the choice of the player, at the same speed of one meter per second. When it reaches the edge of the platform, it continues its vertical free fall. The ball is not allowed to free fall for more then MAX meters at one time (between two platforms). Write a program that finds a way to roll the ball on the platforms so that it reaches the floor as soon as possible without breaking. Input File name: FALL.IN Remarks
Output File name: FALL.OUT Remark If there are several solutions possible, only one is requi"#008DDC" Limits 1<=N<=1000 Example FALL.IN 3 8 17 20 0 10 8 0 10 13 4 14 3FALL.OUT 23 2 4 1 1 11 1 3 16 1 Consider the following game between two players: N rows of sticks lie on a table with S_{i} sticks in row i (1<=i<=N). The sticks in each row i are labeled sequentially from 1 to S_{i}. The players alternately make a move. Each move consists of eliminating one, two or three sticks from the same row. These sticks must be labeled sequentially, i.e., they must be contiguous in the row. For example, if there is a row with 10 sticks and the first player eliminates the sticks labeled 4, 5, 6, only sticks 1, 2, 3, 7, 8, 9, and 10 remain. The second player, on his turn, has the possibility to eliminate the sticks 1, 2, 3 but not 3, 7, 8 since they are not numbe"#008DDC" sequentially (of course, there are other valid moves). The winner is the player performing the last move, i.e., eliminating the last stick(s) from the table. Write a program that implements a winning strategy, playing against a cyberopponent. Input File name: STICKS.IN Remark The test input data guarantees that a winning strategy exists for your program. Your program will play against a machine. The interaction between your program and its opponent will be made possible by the following software interface: with the following routines: procedure putMove(nr,label1,label2:Integer); (Pascal) getMove(var nr,label1,label2:Integer); (Pascal) Your program should alternately call these two routines until there are no more sticks on the table. Our module will terminate the game if your program makes an invalid move (of course you will get no points in this case).
Example STICKS.IN 2 1 3 1possible call succession in PASCAL getMove(nr, k1, k2); > nr=2, k1=2, k2=2 putMove(1, 1, 1); getMove(nr, k1, k2); > nr=2, k1=1, k2=1 putMove(2, 3, 3); **** your program wins **** You can copy from here a demo version of the Unit, but you must keep in mind that this is only a demo version, and it will not play at it's best:
{$A+,B,D+,E+,F,G,I+,L+,N,O,P,Q,R+,S+,T,V+,X+,Y+} {$M 16384,0,655360} unit sticks; interface procedure putMove(nr,label1,label2:integer); procedure getMove(var nr,label1,label2:integer); implementation const vturn:integer=2; var vx,vy,vi,vj,vk,vl,vm,vn:longint; vfi:text; vst:arrayof integer; vpp:arrayof integer; vxxx,vyyy,vzzz:integer; procedure readdata; begin assign(vfi,'sticks.in'); reset(vfi); readln(vfi,vn); for vi:=1 to vn do read(vfi,vst); readln(vfi); readln(vfi,vturn); close(vfi); for vi:=1 to vn do for vj:=1 to vst do vpp:=1; end; function empty:boolean; begin empty:=false; for vi:=1 to vn do for vj:=1 to vst do if vpp=1 then exit; empty:=true; end; procedure eroare(s:string); begin writeln(s); halt; end; procedure putMove(nr,label1,label2:integer); var vmm,vnn:integer; begin if vturn=2 then begin readdata; if vturn=1 then eroare('Wrong player started the game'); end; if vturn=1 then eroare('The other player''s turn'); vturn:=1vturn; if (nr<1)or(nr>vn) then eroare('Invalid move'); if (label1>label2)or(label2<1)or(label1>vst) then eroare('Invalid move'); if label2label1>2 then eroare('Invalid move'); for vi:=label1 to label2 do if vpp=0 then eroare('Invalid move'); for vi:=label1 to label2 do vpp:=0; vnn:=label2label1+1; vm:=0; vi:=label1; while vpp=1 do begin dec(vi); inc(vm); inc(vnn); end; vm:=0; vi:=label2; while vpp=1 do begin inc(vi); inc(vm); inc(vnn); end; if empty then begin halt; end; end; procedure getMove(var nr,label1,label2:integer); var vm:integer; begin if vturn=2 then begin readdata; if vturn=0 then eroare('Wrong player started the game'); end; if vturn=0 then eroare('The other player''s turn'); vturn:=1vturn; for vk:=1 to 100 do begin vi:=random(vn)+1; vj:=random(vst)+1; if vpp=1 then begin vm:=0; vk:=0; while vpp=1 do begin inc(vk); inc(vm); end; vk:=0; while vpp=1 do begin inc(vk); inc(vm); end; vk:=vm; dec(vk); vpp:=0; nr:=vi; label1:=vj; label2:=vj; exit; end; end; for vi:=1 to vn do for vj:=1 to vst do if vpp=1 then begin vk:=0; while vpp=1 do inc(vk); vpp:=0; nr:=vi; label1:=vj; label2:=vj; exit; end; end; end. #include <stdio.h> #include <stdlib.h> int va1_turn=2; long va1_n; int va1_st; int va1_pp; void va1_readdata(void) { int i, j; FILE *fi=fopen("sticks.in", "r"); fscanf(fi, "%d", &va1_n); for (i=1; i<=va1_n; fscanf(fi, "%d", va1_st+(i++))); fscanf(fi, "%d", &va1_turn); fclose(fi); for (i=1; i<=va1_n; i++) for (j=1; j<=va1_st=1); } int va1_empty(void) { int i, j; for (i=1; i<=va1_n; i++) for (j=1; j<=va1_st; j++) if (va1_pp==1) return 0; return 1; } void va1_eroare(char *s) { puts(s); exit(1); } void putMove(int nr, int label1, int label2) { int mm, nn, i, m; if (va1_turn==2) { va1_readdata(); if (va1_turn==1) va1_eroare("Wrong player started the game"); } if (va1_turn==1) va1_eroare("The other player's turn"); va1_turn=1va1_turn; if (nr<1  nr>va1_n) va1_eroare("Invalid move"); if (label1>label2  label2<1  label1>va1_st) va1_eroare("Invalid move"); if (label2label1>2) va1_eroare("Invalid move"); for (i=label1; i<=label2; i++) if (!va1_pp) va1_eroare("Invalid move"); for (i=label1; i<=label2; i++) va1_pp=0; nn=label2label1+1; m=0; i=label1; while (va1_pp==1) { i; m++; nn++; } m=0; i=label2; while (va1_pp==1) { i++; m++; nn++; } if (va1_empty()) { exit(0); } } void getMove(int *nr, int *label1, int *label2) { int m, i, j, k, xxx, yyy, zzz; if (va1_turn==2) { va1_readdata(); if (!va1_turn) va1_eroare("Wrong player started the game"); } if (!va1_turn) va1_eroare("The other player's turn"); va1_turn=1va1_turn; for (k=1; k<=100; k++) { i=rand()%va1_n+1; j=random(va1_st)+1; if (va1_pp==1) { m=k=0; while (va1_pp==1) { k++; m++; } k=0; while (va1_pp==1) { k++; m++; } k=m1; va1_pp=0; *nr=i; *label1=j; *label2=j; return; } } for (i=1; i<=va1_n; i++) for (j=1; j<=va1_st; j++) if (va1_pp==1) { k=0; while (va1_pp==1) k++; va1_pp=0; *nr=i; *label1=j; *label2=j; return; } } Consider a landscape composed of connected line segments: Write a program that determines the minimum number of light bulbs that must be switched on in order to illuminate the entire landscape. Input Input file name: LIGHT.IN Output File name: LIGHT.OUT Line 1: K (an integer: the minimum
number of light bulbs to be switched on) Limits 1<=M<=200 Example LIGHT.IN 6 1 1 3 3 4 1 7 1 8 3 11 1 4 5 1 5 6 10LIGHT.OUT 2 1 4 (Zalaegerszeg, Hungary) Day 2: Components of a Bitmap  Wildcard Patterns  Selecting a Majority Member Scientists are investigating a special kind of molecule. It is known that the molecule consists of N different atoms, labeled from 1 to N, and the structure of the molecule is a linear chain. The scientists are equipped with a distance meter. At one time, this instrument can measure the distance between any two atoms in the molecule. The distance, reported by the instrument, is the absolute value of the difference of the two atom positions in the chain. If you access no atom for more than three times no damage is done to the molecule. If you access one or more atoms four times the molecule gets damaged. If you access one or more atoms five times the molecule gets destroyed. You are to write a program that discovers the complete structure of the molecule by determining the sequence of the atoms in the molecule.
To operate the distance meter, you are given a library meter with three operations:
Instruction for Pascal programmers: Instructions for C/C++ programmers: Experimentation You can experiment with the library by creating a text file chain.in. The file must contain two lines. The first line should contain the integer N, the number of atoms. The second line should contain a test case: a sequence of the atom labels, consisting of N different integers between 1 and N. Example for experimentation chain.in 5 1 3 5 2 4chain.out Size=5 Span(1,2)=3 Span(1,3)=1 Span(2,3)=2 Span(4,5)=2 Span(1,4)=4 Span(3,5)=1 Your Answer: 1 3 5 2 4 Max. Access/Atom: 3 Constraints A printed circuit is a board that consists of nodes and wire segments connecting pairs of nodes. We consider a special kind of printed circuits where the nodes are arranged in a rectangular grid, and the wire segments connect (vertically or horizontally) adjacent nodes only. A printed circuit is called connected if any two distinct nodes are connected with a series of wire segments. Given is a printed circuit where wire segments already connect several adjacent nodes. We have to add new wire segments in order to make the printed circuit connected. The cost of a new wire segment is 1 if it is vertical and 2 if it is horizontal in the grid.
You are to write a program that computes a least cost completion of a given circuit. Your program should solve the following three subtasks:
Input The first line of the file circuit.in contains two integers, N and M. N (1<=N<=100) is the number of rows and M (1<=M<=100) is the number of columns in the grid. The nodes of the circuit are identified by their coordinates; the node in the upper left corner is at (1,1), and the node in the lower right corner is at (N, M). Each of the next N lines contains M integers. The number in row i and column j of these lines describes the wire segments between the pair of nodes (i,j) and (i+1,j), and also between the pair of nodes (i,j) and (i,j+1) in the following way. 0 means that neither the pair of nodes (i,j) and (i+1,j) nor the pair of
nodes (i,j) and (i,j+1) are connected by wire segments. Note that not all 4 values are valid at certain positions (e.g. at position (N,M) only value 0 is valid). Output The first line of the file circuit.out should contain two integers, K and V. The integer K is the number of new wire segments of a least cost completion; and the integer V is the value of the least cost. The rest of the file must contain K lines; the list of wire segments of a least cost completion (in arbitrary order). Each line must contain three numbers describing exactly one new wire segment: i, j and d, where (i,j) are the coordinates of a node, and d is either 1 or 2. 1 means that the new wire segment connects the nodes (i,j) and (i+1,j), and 2 means that the new wire segment connects the nodes (i,j) and (i,j+1) Example The example input file corresponds to the circuit in 1st figure. The example output file is a possible least cost completion, and is depicted in Figure 2. circuit.in 4 5 2 1 1 2 1 0 3 0 1 0 3 0 0 3 1 0 2 0 2 0circuit.out 5 6 1 1 1 3 2 1 3 3 1 3 3 2 2 5 1 Your team decided to take a round trip in the host country after the competition. You want to travel to a destination city and return to the starting city. The only requirement your team specified is that the forward route to the destination city and the return route back to the starting city must contain the least possible number of common roads. (A route can not contain any road twice or more times.) You are to write a program that computes two routes between the starting city and the destination city so that the number of common roads in the two routes is as small as possible. Input The first line of the file trip.in contains two integers, S and D (S<>D), the labels of the starting and the destination cities, respectively. The second line contains two integers, N and M, where N (3<=N<=1000) is the number of the cities and M (2<=M<=100000) is the number of the roads between the cities. The cities are labeled from 1 to N. Each of the next M lines in the file contains two integers, P and Q (1<=P,Q<=N, P<>Q), meaning that there is a twoway road between city P and city Q. There is at most one road between any two cities. Output The first line of the file trip.out must contain one integer, the least possible number of common roads of the forward and the return routes. The second line should contain a forward route as a sequence of city labels, including the starting and ending city. The third line should contain a return route as a sequence of city labels (again including the starting and ending cities). If there are more possible pairs of routes with the same least number of common roads then your program may output any one of them. If there is no route from the starting city to the destination city then the first and only line must contain 1. Example input and output trip.in 1 6 7 8 2 1 1 3 2 3 4 2 4 5 5 6 7 5 6 7trip.out 2 1 3 2 4 5 7 6 6 5 4 2 1 Black and white pictures are usually sto"#008DDC" as bitmaps. A bitmap is a rectangular grid of pixels. A polyline between pixels P and Q is a sequence of black pixels P=P_{1}, P_{2}, ..., P_{k}=Q, where P_{i} and P_{i+1} (i=1, ..., k1) are (vertically or horizontally) adjacent pixels. A polyline P_{1}, P_{2}, ..., P_{k} is closed if P_{1}=P_{k}, and P_{i}<>P_{j} (i=1,...,k1, j=2,...,k) for i<j unless i=1 and j=k (that is the polyline does not contain the same pixel twice). A set of black pixels S is connected if for each pair of pixels (P,Q) in S there is at least one polyline L between P and Q with all pixels of L belonging to S. A component of a bitmap is a maximal connected set of black pixels. A component may enclose holes. A hole consists of white pixels that are inside a closed polyline. A compact component encloses no holes. Note that in Figure 1 the white pixel in the middle, marked with x, is not inside the highlighted closed polyline.
Figure 2 shows a bitmap with five components, of which two are compact ones. You are to write a program that computes the total number of components and the number of compact components of a given coded bitmap. The bitmaps under investigation are coded (compressed) with the following method. Each row is coded with a sequence of integers W_{1}, B_{1}, ..., W_{k}, B_{k}, where W_{i} is the number of consecutive white pixels, and B_{i} is the number of consecutive black pixels, respectively. For example, the code of the first line of the bitmap in Figure 2 is the sequence 4 7 4 4 1 0. Components 4 and 5 are compact, while components 1, 2 and 3 are not compact. Input The first line of the file bitmap.in contains two positive integers, N and M. N (2<=N<=10000) is the number of rows and M (2<=M<=1000) is the number of columns of the bitmap. The next N lines contain the coded bitmap according to the paragraph on encoding. Each line terminates with 1. Output The file bitmap.out must contain two lines, with a single integer in each line. The first line contains the number of all components and the second line contains the number of compact components of the input bitmap. Example bitmap.in 10 20 4 7 4 4 1 0 1 0 4 1 4 1 4 1 1 1 3 1 1 3 4 6 2 4 1 0 7 9 4 1 0 1 4 9 1 1 4 0 1 0 1 1 3 1 8 1 5 1 0 1 1 1 1 1 1 8 1 1 3 1 1 0 1 1 3 1 1 3 1 2 1 1 1 3 1 1 0 1 5 1 1 6 1 1 3 1 1 0 7 3 4 1 1 3 1 1bitmap.out 5 2 Wildcard patterns are frequently used to specify sets of names. For example, we can specify all file names which start with h and end with bak by the pattern h*bak. A wildcard pattern is a string that may contain * characters as wildcards. A string W matches a pattern P if W can be obtained from P by substituting some (possibly empty) string for each * character in P. (Different strings may be substituted for different occurrences of *.) For a pair of patterns P_{1} and P_{2}, Q is a common pattern of P_{1} and P_{2} if any string that matches Q also matches both P_{1} and P_{2}. A set Q_{1}, Q_{2}, ..., Q_{L} of common patterns is called complete if any string that matches both P_{1} and P_{2} matches at least one Q_{i} (1<=i<=L). You are to write a program that for a given pair of patterns P_{1} and P_{2} computes
Input The first and the second lines of the file pattern.in contain the patterns P_{1} and P_{2}. The patterns are composed of the lowercase letters from 'a' to 'z' and the '*' character. Each pattern contains no more than 20 characters. The number of the * characters in each pattern is between 0 and 6. Output The first line of the file pattern.out must contain the integer K, the number of common patterns computed as a solution. The next K lines contain one common pattern in each line; these constitute the solution. The order of the common patterns is irrelevant. Both case B and C can be solved within the specified limit of 6666 entries. If there is no common pattern of P_{1} and P_{2}, then the first and only line must contain the number 0. Example input and output pattern.in *ab* ba*bpattern.out for case C 4 ba*ab*b bab*b ba*ab bab Students in your school belong to two disjoint groups. It is known that one group, called the majority group, contains more students than the other group. We want to select a student who belongs to the majority group. Student's identifiers are integers from 1 to the number of students. The only operation that we can perform is to query whether two students belong to the same group. You are to write a program that finds a student who belongs to the majority group, while it performs as few queries as possible. To perform queries, you are given a library query with three operations:
The dialogue between your program and the library procedures is logged in the text file select.out. This log file also contains your answer and an indication whether your answer was correct. Your answer is accepted only if for any two disjoint groups of all students A and B, for which all your queries give the same result, your answer identifies a member of the largest group of A and B. The library forces your program to issue all the queries that are necessary to identify a member of the majority group. That is, there are no predefined test cases but the library produces them "on the fly". Instruction for Pascal programmers: Instructions for C/C++ programmers: Experimentation You can experiment with the library by creating a text file select.in. The first and only line must contain the integer N, the number of all students. N must be an odd number! Example for experimentation select.in 7select.out Size=7 Member(1,2)=0 Member(3,4)=1 Member(5,6)=1 Member(4,6)=0 Your Answer: 7, Correct Majority Group: 2 5..7 Nonmajority Group: 1 3 4 Number of Queries: 4 Full Possible Score: 3 Your Score: 3 Constraints (Košice, Slovakia) Day 2: A highway and the seven dwarfs  Royal guards  Birthday party Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte QRAM chip. Each chip consists of six unit squares arranged in a form of a 2×3 rectangle. The way QRAM chips are made is such that one takes a rectangular plate of silicon divided into N×M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.
Finally, the plate of silicon is cut into memory chips. Each chip consists of 2×3 (or 3×2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible. Task You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate. Input description The first line of the input file consists of a single integer D (1<=D<=5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1<=N<=150), M (1<=M<=10), K (0<=K<=MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1<=x<=N, 1<=y<=M)  coordinates of one bad square (the upper left square has coordinates ). Output description For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate. Example input 2 6 6 5 1 4 4 6 2 2 3 6 6 4 6 5 4 3 3 6 1 6 2 6 4 Example output 3 4
In the whole history of mankind one can find several curious battles, like the following one in France, in 1747... There was a fortress in BassignacleHaut, a small village lying on the left bank of river Dordogne, just over the Chastang dam. From the dam up to the fortress there was a wide staircase made out of "#008DDC" marble. One day in the morning, the guard spotted a large battalion approaching the fortress, with a dreaded leader  The Conqueror. When The Conqueror reached the fortress, he was already awaited by its commandant. As the commandant had only a small part of his soldiery available, he proposed to The Conqueror: "I see that you have many soldiers behind you, standing on the stairs. We can play a small 'game': In each round, you will divide your soldiers into two groups in an arbitrary way. Then I will decide which one of them stays and which one goes home. Each soldier that stays will then move up one stair. If at least one of your soldiers reaches the uppermost stair, you will be the winner, in the other case, you will be the loser. And your destination will be the dam down there...", added the commandant, pointing to the Chastang dam by his hand. The Conqueror immediately liked this game, so he agreed and started to 'conquer'. Task Your role is The Conqueror's now. There are N stairs to the fortress (2<=N<=2000) and you have at most 1 000 000 000 soldiers. For each stair, you are given the number of soldiers standing on it, with number 1 being the uppermost stair and N the bottom one. None of your soldiers stands on stair 1 at the beginning. For each starting position given to your program, if the position is winning (i.e. there is a strategy that enables you to win the game regardless of your opponent's moves), your program should win. Otherwise it should just play the game (and lose) correctly. This is an interactive problem; you will play against a library as specified below. In each round, your program will describe a group of soldiers to our library. The library returns 1 or 2 specifying which group of soldiers should stay (1 means the group you described, 2 means the rest of the soldiers). In case the game ends (either because you won or there are no more soldiers in the game), the library will terminate your program correctly. Your program may not terminate in any other way. Library interface The library libconq provides two routines:
Following are the declarations of these routines in FreePascal and C/C++: procedure start(var N: longint; var stairs:array of longint); function step(subset:array of longint): longint; void start(int *N, int *stairs); int step(int *subset); Below you can find examples of library usage in both FreePascal and C/C++; both fragments do the same  start the game and then play one round, with the chosen group containing all soldiers on randomly chosen stairs. Your real program will probably play the rounds in an infinite loop. You are strongly encouraged to define the arrays stairs and subset in the same way as they are defined in the example below. (Note that the FreePascal library returns its answer in the first N elements of the array regardless of how you defined it, the C/C++ library returns its answer in the elements with indices 1 to N.) FreePascal example uses libconq; var stairs: array of longint; subset: array of longint; i,N,result: longint; ... start(N,stairs); ... for i:=1 to N do if random(2)=0 then subset:=0 else subset; result:=step(subset); ... C/C++ example #include "libconq.h" int stairs; int subset; int i,N,result; ... start(&N, stairs); ... for (i=1;i<=N;i++) if (rand()%2==0) subset=0; else subset; result=step(subset); ... You have to link the library to your program  by uses libconq; in FreePascal and by #include "libconq.h" in C/C++, where you have to compile your program by adding libconq.c to the compiler arguments. An example of the game
Resources On the web page you may find example libraries for both C/C++ and FreePascal. These libraries are different from those that will be used during testing. You may use them to make sure your library calls are correct. The example library reads the input from the file libconq.dat, containing two lines. On the first line is the number N of stairs, the second line contains N integers  the numbers of soldiers on each of the stairs 1..N. The file libconq.dat for the example above would look like this: 8 0 1 1 0 3 3 4 0
unit libconq; interface const MAX_N = 2000; MAX_M = 1000000000; procedure start(var N: longint; var stairs: array of longint); function step(subset: array of longint): longint; implementation const game_N: longint = 0; lib_usage: longint = 0; var st: array of longint; lib_txt: string; procedure lib_error(code: longint; s: string); var f: text; begin assign(f,'libconq.out'); rewrite(f); writeln(f,s); close(f); halt(code); end; function int2str(i:longint): string; var s:string; begin str(i,s); int2str:=s; end; procedure start(var N: longint; var stairs: array of longint); var f: text; i: longint; begin if (lib_usage<>0) then lib_error(1,'start() called too many times'); inc(lib_usage); assign(f,'libconq.dat'); {$I} reset(f); {$I+} if IOResult<>0 then begin randomize; N:=2+random(MAX_N2); stairs:=0; for i:=1 to N1 do stairs:=random(i*i); end else begin read(f,N); for i:=0 to N1 do read(f,stairs); close(f); end; game_N:=N; for i:=1 to N do st; end; function decide(a: array of longint): longint; begin decide:=1+random(2); end; function step(subset: array of longint): longint; var choice,i,wrong,cnt: longint; begin if (lib_usage=0) then lib_error(1,'call start() first!'); inc(lib_usage); { check if a is a valid subset } wrong:=0; for i:=1 to game_N do begin if ((subset)) then wrong:=i; if (wrong<>0) then break; end; if (wrong<>0) then begin lib_txt:='wrong number of soldiers on stair '+int2str(wrong)+ ': '+int2str(subset)+ ' requested, '+int2str(st)+ ' available'; lib_error(1,lib_txt); end; { decide } choice:=decide(subset); { choice 1: move subset one stair up, discard the rest } if (choice=1) then begin for i:=1 to game_N do st; for i:=1 to game_N do st; end else { choice 2: discard subset, move complement one stair up } begin for i:=1 to game_N do dec(st); for i:=1 to game_N do st; end; { check if there are any soldiers left } { check if there is any soldier at position 1 } cnt:=0; for i:=1 to game_N do if st<>0 then inc(cnt); if (cnt=0) then begin lib_txt:='You lost!'; lib_error(0,lib_txt); end; if (st<>0) then begin lib_txt:='You won!'; lib_error(0,lib_txt); end; step:=choice; end; end.
#ifndef __LIBCONQ_H #define __LIBCONQ_H #define MAX_N 2000 #define MAX_M 1000000000 void start(int *N, int *stairs); int step(int *subset); #endif /* __LIBCONQ_H */
#include Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME1Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its preface he already knew, what makes a little wooden fence cute. A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met:
It is obvious, that there are many different cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a_{1},..., a_{N}) is in the catalogue before fence B (represented by b_{1}, ..., b_{N}) if and only if there exists such i, that (for all j<i)(a_{j}=b_{j}) and a_{i}<b_{i}. (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbe"#008DDC" (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number.
All cute fences made of N = 4 planks, orde"#008DDC" by their catalogue numbers. After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he orde"#008DDC", but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like. Input description The first line of the input file contains the number K (1<=K<=100) of input data sets. K lines follow, each of them describes one input data set. Each of the following K lines contains two integers N and C (1<=N<=20), separated by a space. N is the number of planks in the fence, C is the catalogue number of the fence. You may assume, that the total number of cute little wooden fences with 20 planks fits into a 64bit signed integer variable (long long in C/C++, int64 in FreePascal). You may also assume that the input is correct, in particular that C is at least 1 and it doesn't exceed the number of cute fences with N planks. Output description For each input data set output one line, describing the Cth fence with N planks in the catalogue. More precisely, if the fence is described by the permutation a_{1}, ..., a_{N}, then the corresponding line of the output file should contain the numbers ai (in the correct order), separated by single spaces. Example input 2 2 1 3 3 Example output 1 2 2 3 1 Once upon a time, there was a land where several families of dwarfs were living. This land was called Dwarfland. Each family lived in one house. Dwarfs were often visiting their friends from the other families. Because the Dwarfland was free of evil, it happened that each dwarf visited each other during some short period of time. Once, the humans living in countries around Dwarfland decided to build several straight highways. As the humans weren't aware of the dwarfs, some of the planned highways passed through Dwarfland. The dwarfs discove"#008DDC" this and were quite unhappy about it. The dwarfs are very little, and also very slow, so they are unable to cross the highway safely. The dwarfs managed to get the plans for the highways somehow, and now they need your help. They would like to keep on visiting each other, so they don't like those highways which divide their houses into two nonempty parts. After they find out which highways they don't like, they will magically prevent the humans from building them. The dwarfs are very little, and cannot reach the keyboard. So they asked for your help. Task Given is a number N of points (houses) in the plane and several straight lines (highways). For each given line, your task is to determine whether all N points lie on the same side of the line or not. Your program has to output the answer for the currently processed line before reading the description of the next one. You may assume that no highway passes through any of the houses. Input and output description Your program is supposed to read the input from the standard input (stdin in C/C++, input in FreePascal) and write its output to the standard output (stdout in C/C++, output in FreePascal). The first line of the input contains one integer N (0<=N<=100 000). N lines follow, the ith of them contains two real numbers x_{i}, y_{i} (10^{9}<=x_{i}, y_{i}<=10^{9}) separated by a single space  the coordinates of the ith house. Each of the following lines contains four real numbers X_{1}, Y_{1}, X_{2}, Y_{2} (10^{9}<=X_{1}, Y_{1}, X_{2}, Y_{2}<=10^{9}) separated by a single space. These numbers are the coordinates of two different points , lying on the highway. For each line of input, your program is supposed to output a line containing the string "GOOD" if all of the given points are on the same side of the given line, or "BAD" if the given line divides the points. After writing out each line of the output, your program should flush the output buffer. In the following sections you may find an example on how to do this. We will terminate your program after it gives the answer for the last highway. Your program is not supposed to terminate by itself. You may assume that there will be no more than 100 000 highways. Input and output routines in C/C++ Reading one line (note that there is no space after the last %lf): double X_1, Y_1, X_2, Y_2; scanf(" %lf %lf %lf %lf",&X_1,&Y_1,&X_2,&Y_2);Writing the output for one line: printf("GOOD\n"); fflush(stdout); Input and output routines in FreePascal Reading one line: var X_1, Y_1, X_2, Y_2 : double; read(X_1,Y_1,X_2,Y_2);Writing the output for one line: writeln('GOOD'); flush(output); Warning You are adviced to use the double data type (in both C/C++ and FreePascal) to store real numbers. Note that when using real number arithmetics, rounding errors may occur. If you want to test, whether two real numbers x, y are equal, don't test whether x = y but whether xy<e (where e is a small constant, 10^{4} will suffice). Example input 4 0.0 0 6.00 0.001 3.125 4.747 4.747 0.47 5 3 7 0 4 4.7 7 4.7 4 47 4 94 Example output GOOD BAD BAD
Once upon a time, there was a kingdom. It had everything a kingdom needs, namely a king and his castle. The groundplan of the castle was a rectangle that was divided into M×N unit squares. Some of the squares are walls, some of them are free. We will call each of the free squares a room. The king of our kingdom was extremely paranoid, so one day he decided to make hidden pits (with alligators at the bottom) in some of the rooms. But this was still not enough. One week later, he decided to place as many guards as possible inside his castle. However, this won't be so simple. The guards are trained so that immediately after they see someone, they shoot at him. And so the king has to place the guards carefully, because if two guards would see each other, they would shoot at themselves! Also evidently the king can't place a guard into a room with a pit. Two guards in a room see each other, so each room may contain at most one guard. Two guards in different rooms see each other if and only if the squares corresponding to their rooms are in the same row or in the same column of the plan of the castle and there is no wall between them. (The guard can see only in four directions, much like a rook in chess.) Task Your task is to find out, how many guards can the king place inside his castle (according to the rules above) and to find one possible assignment of that many guards into the rooms. Input description The first line of the input file contains two numbers M, N, 1<=M,N<=200  the dimensions of the groundplan of the castle. The ith of the following M lines contains N numbers a_{i,1}, ..., a_{i,N}, separated by single spaces, where:
Output description The first line of the output file should contain the maximum number K of guards the king may place inside his castle. The following K lines should contain one possible assignment of K guards into the free rooms of the castle so that no two guards would see each other. More precisely, the ith of these lines should contain two integers r_{i}, c_{i} separated by a single space  the coordinates of the room where ith guard will be placed (r_{i} is the row and c_{i} is the column).
Castle from the example input and one possible correct output
Example input 3 4 2 0 0 0 2 2 2 1 0 1 0 2 Example output 2 1 2 3 3 John's birthday is approaching slowly, and as every year, John is going to organize a great garden party. He wants all his friends to come, but (sadly) he knows, that it is almost impossible. For example Susie left Steve last week, and it will be almost impossible to make both of them come. John spent most of the last week visiting his friends and asking them to come. He got some promises, but even more requests. ('If you invite me, you just have to invite my boyfriend!' exclaimed Veronica. 'If you invite the Burdiliak twins, don't expect me or Joseph to come!' stated Peter.) Suddenly, John realized, that it will be quite hard just to satisfy all the requests he got. Task You are given a description of the requests John got from his friends. Your task is to find a group of people such that if John invites the people in this group (and nobody else) to his party, all the requests he got will be satisfied. The requests are described in the following way:
Input description You can find ten input files, called party1.in to party10.in, here. On the first line of the input file is the number of John's friends F, next F lines contain their names, one per line. On the next line is the number of requests N. Each of the following N lines contains one request. Output description For each file partyX.in you have to produce the corresponding output file partyX.out, containing one correct solution. The first line of the output file will be the number K of people John should invite. The following K lines should contain their names, one per line. You may assume that each of the input files has a (not necessarily unique) solution. If there are more possible solutions, you may output any of them. Example input 3 veronica steve dick 3 (veronica => dick) (steve => veronica) (steve & dick) Example output 2 steve dick (Munster, German) Hanoi: Description (PS, PDF), Solution (PDF), Solution Programs (CPP, PAS, PL), Test Data Square: Description (PS, PDF), Solution (PS, PDF), Solution Programs (CPP, PAS), Library Test Data The race: Description (PS, PDF), Solution (PS, PDF), Solution Programs (CPP, PAS) Test Data Pearls: Description (PS), Solution (PS, PDF), Solution Programs (CPP, PAS), Test Data, Library Register: Description (PS), Solution (PS), Solution Programs (C), Test Data Trip: Description (PS), Solution (PS), Solution Programs (C, CPP), Test Data 