Twelve problems were presented to the jury of IOI. Nine problems for the first day. Three problems for the second day. The IOI jury selected three problems for the first day: 1. The necklace of beads. 2. The companies's shares. 3. Rectangles of different colours. And one problem for the second day: 1. The travel around Canada. For further information FIRST DAY Problem 1.1.a: You have a necklace of n beads (n <100) some of which are red, others blue and others white, arranged at random. Let's see two examples for n = 29: 1 2 1 2 o x x o x o o x o x x x o o x o o o @ o x o @ @ x x o o x x x x x x o x o o x o x o o o x o o o o o o x o x o o o @ Figure a Figure b o red bead x blue bead @ white bead (The beads considered first and second in the text that follows have been marked in the picture). The configuration in Fig. a) may be represented as a string of b's and r's, where b represents a blue bead and r a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb Suppose you are to break the necklace, lay it out straight, and then collect beads of the same colour from one end until you reach a bead of a different colour, and do the same for the other end (which may not be of the same colour as the beads collected before this). Determine the point where the necklace should be broken so that the most number of beads can be collected. For example, for the necklace in Fig. a), 8 beads can be collected, with the breaking point either between bead 9 and bead 10, or between bead 24 and bead 25. In some necklaces, white beads had been included as shown in Figure b) above. When collecting beads, a white bead that is encountered may be treated as either red or blue, and painted with the desired colour. The string that represents this configuration will include the symbols: r, b and w. Write a program to do the following: 1. Read a configuration from an ASCII input file, NECKLACE.DAT, with each configuration on one line. Write this data into an ASCII output file, NECKLACE.SOL. An example of an input file would be: Example: NECKLACE.DAT brbrrrbbbrrrrrbrrbbrbbbbrrrrb bbwbrrrwbrbrrrrrb 2. For each configuration, determine the maximum number, M, of beads collectable, along with a breaking point. 3. Write to the outfile, NECKLACE.SOL, the number M and the breaking point. The solutions for different configurations should be separated with a blank record. Example of a possible solution: NECKLACE.SOL brbrrrbbbrrrrrbrrbbrbbbbrrrrb 8 between 9 and 10 bbwbrrrwbrbrrrrrb 10 between 16 and 17 Problem 1.2.a: The economic situation has turned bad. Due to a shortage of money in circulation and lack of credit, many factories have contracted debts that they cannot pay. There are, at most, 1000 factories. All factories act as sellers (they sell their production) as well as buyers (they buy raw materials and component parts). So they contract debts among themselves. Finally, someone has had the idea of paying debts with ... debts. Say factory A owes $100 to factory B, factory B owes $50 to factory C, and C owes $75 to A. The sum of all the debts is $225. Factory A uses its credit with factory C to pay part of its debt to factory B. So, A to B $25 B to C $50 C to B $75 This way, the total debt may be reduced to a minimal sum and the list of debts becomes: A to B $25 C to B $25 The problem is to write a program for paying debts with debts. 1. Read a list of debts from an ASCII input file, DEBT.DAT, and write this data to an ASCII output file, DEBT.SOL. Each record in the list consists of three items: two factory codes and the amount owed by the first to the second. Different lists will be separated by a blank record as shown in the example below. Calculate and output to DEBT.SOL the total amount of debts. 2. Reconstruct the list of debts so that the total amount of debts is minimal. Write to DEBT.SOL the new list of debts in the same form as the input list. 3. Calculate and output to DEBT.SOL the total amount of debts in the new list. Example: DEBT.DAT A B 100.00 B C 50.00 C A 75.00 A B 1500.00 B C 1100.00 D A 1400.00 Example of a possible solution: DEBT.SOL A B 100.00 B C 50.00 C A 75.00 Total = $225.00 A B 25.00 C B 25.00 Total = $50.00 A B 1500.00 B C 1100.00 D A 1400.00 Total = $4000.00 A B 100.00 D B 300.00 D C 1100.00 Total = $1500.00 Problem 1.3.a: In the city of Sinistra, the Town Council has forbidden right turns. In order to enforce this rule, all car drivers are required by the Town Council to install a computer in their vehicles. This computer records the vehicle coordinates every time the vehicle turns right or left. At the end of each trip, a sequence of positions is transmitted to a Council computer, which calculates the amount of the traffic ticket by charging a fine of $50 for each right turn. The problem to solve is: given the sequence of positions of a car, calculate the amount of the traffic ticket. Details: A trip is represented by a sequence of 2 or more points: p1, p2, ...., pN. Each point is a pair of numbers (i, j), where i and j are the coordinates of the position of the car in a coordinate system with origin at the Town Hall. p1 is the position where the trip began, pN is the position where it ended, and the other points are the corners where the car turned left or right. The streets are straight lines of arbitrary direction. The problem is to write a program to: 1. Read from the input ASCII file, SINISTRA.DAT, and write in an output file, SINISTRA.SOL, the number N of points in the trip on one line and each point in the trip on the next N lines. Each data set will be separated from the next by a blank line. Each point in the input sequence is a pair of numbers separated by a blank with consecutive points on consecutive lines, appearing in the order p1, ..., pN. 2. Compute the traffic ticket for the given trip. 3. Write in the output ASCII file SINISTRA.SOL the amount of the traffic ticket that must be paid to the Town Council for each trip. Separate the amounts for the trips with a blank record. Example: SINISTRA.DAT 3 4 1 5.5 4 5 2 4 0 1 -1 0 0 -1 1 0 SINISTRA.SOL 3 4 1 5.5 4 5 2 Traffic ticket: $50 4 0 1 -1 0 0 -1 1 0 Traffic ticket: $0 Problem 1.1.b: The computer and a child are playing in the following way: The child thinks of a sequence of four colours (not necessarily different) chosen out of six possible colours. For convenience, let us use the numbers between 1 and 6 for denoting the six colours. The computer (your program) must find this sequence using the information it obtains from the child's answers. The computer displays a sequence on the screen and the child must answer, using the keyboard to enter the answers, the following two questions: a) How many colours are right but not in the right positions? b) How many right colours are in the right positions? Example: Suppose the child has chosen the sequence: 4655. One possible way to find this sequence may be: COMPUTER YOUR ANSWER 1234 a) 1 b) 0 5156 a) 2 b) 1 6165 a) 1 b) 1 5625 a) 1 b) 2 5653 a) 1 b) 2 4655 a) 0 b) 4 Write a program that will always find the sequence chosen by the child in at most 6 steps. If you cannot do this, write a program to find the sequence chosen by the child in at most 10 steps. Problem 1.2.b: Some companies are partial owners of other companies because they have acquired part of their total shares. For example, Ford owns 12% of Mazda. It is said that a company A controls company B if, at least, one of the following conditions is satisfied: a) A = B b) A owns more than 50% of B c) A controls k (k > 1) companies, C(1), ..., C(k), so that: C(i) owns x(i)% of B for 1 < i < k and x(1) + .... + x(k) > 50. The problem to solve is: Given a list of triples (i,j,p) which means that the company i owns p% of company j, calculate all the pairs (h,s) so that company h controls company s. There are at most 100 companies. Write a program to: 1 Read from an ASCII input file, COMPANY.DAT, the list of triples, (i,j,p), to be considered for each case (that is, each data set), where i, j and p are positive integers. Different cases (data sets) will be separated with a blank record. 2 Find all the pairs (h,s) so that company h controls company s. 3 Write to an ASCII output file, COMPANY.SOL, all the pairs (h,s) found, with h different from s. The pairs (h,s) must be written in consecutive records and in increasing order of h. The solutions for different cases must be separated with a blank record. Example: COMPANY.DAT 2 3 25 1 4 36 4 5 63 2 1 48 3 4 30 4 2 52 5 3 30 1 2 30 2 3 52 3 4 51 4 5 70 5 4 20 4 3 20 COMPANY.SOL 4 2 4 3 4 5 2 3 2 4 2 5 3 4 3 5 4 5 Problem 1.2.c: A sequence of positive integers a1,.... aN is called an additive chain of length N if for every k, 1 < k < N, there exists indices i and j, 1< i < j < N, so that: ak = ai + aj For example: 1 2 3 5 1 2 3 4 5 1 2 4 5 are additive chains. The problem is, given a positive integer a, find an additive chain with minimal length N that has a1 = 1 and aN = a. Write a program to: 1 Read from an ASCII input file, CHAIN.DAT the number a. Different cases will be separated with a blank record. 2 Find an additive chain of minimal length which starts with 1 and ends with a. 3 Write to an ASCII output file, CHAIN.SOL, the additive chain obtained. The solutions for different cases must be separated with a blank record. Example: CHAIN.DAT 3 5 Example of a possible solution: CHAIN.SOL 1 2 3 1 2 3 5 Problem 1.1.c: You are given a general chessboard of nxn squares, n < 10. White squares and black squares of the chessboard are arbitrarily arranged, but satisfy the following conditions: i) Each column contains at least one white square. ii) There is at least one column that contains only white squares. You are requested to place castles into squares of the chessboard so that: 1) castles are only placed on white squares. 2) on every row and every column there is at most one castle. 3) each white square not containing a castle that is dominated by a castle on the same row must also be dominated by another castle on the same column. Write a program that does the following tasks: a. Read from an ASCII input file, CHESS.DAT, the number n and the configuration for an nxn chessboard, that is, n strings of 1's and 0's where 1 represents a white square and 0 represents a black square. Write this data to an ASCII output file, CHESS.SOL. b. Place as many castles as possible on the squares of the chessboard so that the three above conditions are satisfied. c. Output to CHESS.SOL the total M of castles placed and the chessboard where the white squares have been replaced by the character "X" if you have placed a castle there. Example: CHESS.DAT 3 010 110 011 4 1111 0001 0001 0001 CHESS.SOL 3 010 110 011 3 0X0 X10 01X 4 1111 0001 0001 0001 1 1111 000X 0001 0001 Problem 1.2.c: New Makeup Ltd. is an important factory which produces N different cosmetics. Every month, New Makeup sends a shipment to its branch in Mallorca. Each cosmetic has different price and volume. This week the longshoremen of Buenos Aires Port have announced they will go on strike starting next Monday. Nobody knows when port activities will be normalized. New Makeup's next shipment is on Saturday and, for economic reasons, the factory needs to maximize the shipment's value. You have to give an answer to New Makeup's General Manager. For this, different data sets have been written in an ASCII input file, MAKEUP.DAT. Each data set will look like this: N (the total number of different products) M (ship hold's capacity) P1 V1 (price and volume of each unit of product 1) P2 V2 (price and volume of each unit of product 2) ......... PN VN (price and volume of each unit of product N) where the numbers N, M, Pi, Vi (1 < i < N) are positive integers. Write a program to: 1. Read the next data set from MAKEUP.DAT. 2. Determine how many units of each product have to be included in the shipment so that: * the shipment's volume doesn't exceed the ship hold's capacity * the shipment's value is maximum. 3. Write into the ASCII output file, MAKEUP.SOL: * the quantity of units of each product included in the shipment * the shipment's value * the shipment's volume The solutions to different data sets must be separated by a blank record. Example: MAKEUP.DAT 2 6 4 3 7 4 5 20 2 3 3 4 12 10 17 11 7 6 MAKEUP.SOL Prod. 1 = 2 Prod. 2 = 0 Value = $8 Volume = 6 Prod. 1 = 1 Prod. 2 = 0 Prod. 3 = 0 Prod. 4 = 1 Prod. 5 = 1 Value = $26 Volume = 20 Problem 1.3.c: N rectangles of different colours are superposed on a white sheet of paper. The sheet's sizes are: a cm wide and b cm long. The rectangles are put with their sides parallel to the sheet's borders. All rectangles fall within the borders of the sheet. As result, different figures of different colours will be seen. Two regions of the same colour are considered to be part of the same figure if they have at least one point in common; otherwise, they are considered different figures. The problem is to calculate the area of each of these figures. a, b are even positive integers not greater than 30. The coordinate system considered has origin at the sheet's center and the axes parallel to the sheet's borders: Different data sets are written in an ASCII input file, RECTANG.DAT: a, b and N will be in the first line of each data set, separated by a blank space. * In each of the next N lines you will find: * the integer coordinates of the position where the left lower vertex of the rectangle was put. * followed by the integer coordinates of the position where the upper right vertex of the rectangle was put * and, then, the rectangle's colour represented by an integer between 1 and 64. White colour will be represented by 1. The order of the records corresponds to the order used to put the rectangles on the sheet. Different data sets will be separated with a blank record. Write a program to: 1. Read the next data set from RECTANG.DAT 2. Calculate the area of each coloured figure 3. Write in an ASCII output file, RECTANG.SOL, the colour and the area of each coloured figure as shown in the example below. These records will be written in increasing order of colour. The solutions to different data sets will be separated by a blank record. Example: RECTANG.DAT 20 12 5 -7 -5 -3 -1 4 -5 -3 5 3 2 -4 -2 -2 2 4 2 -2 3 -1 12 3 1 7 5 1 30 30 2 0 0 5 14 2 -10 -7 0 13 15 RECTANG.SOL 1 172 2 47 4 12 4 8 12 1 1 630 2 70 15 200 SECOND DAY Problem 2.1: You have won a contest organized by a Canadian airline. The prize is a free ticket to travel around Canada, beginning in the most western point visited by this airline, then traveling only from West to East until you reach the most eastern point visited by this airline, and then coming back only from East to West until you reach the starting point. No city may be visited more than once, except for the starting city, which must be visited exactly twice (at the beginning and the end of the trip). You are also not allowed to use any other airline or any other means of transportation. The problem to solve is: given a list of cities and a list of direct flights between pairs of cities, find out an itinerary which visits as many cities as possible satisfying the above conditions. Different data sets are written in an ASCII input file, C:\IOI\ITIN.DAT. Each data set consists of: * in the first line: the number N of cities visited by the airline and the number V of direct flights that will be listed. N will be a positive integer not larger than 100. V is any positive integer. * in each of the next N lines: a name of a city visited by the airline. The names are ordered from West to East in the input file. That is, the i-th city is East of the j-th city if and only if i > j (There aren't two cities in the same meridian). The name of each city is a string of, at most, 15 digits and/or characters of the Latin alphabet, for example: AGR34 or BEL4 * in each of the next V lines: two names of cities, taken from the list of cities, separated by a blank space. If the pair city1 city2 appears in a line, it indicates that there exists a direct flight from city1 to city2 and also a direct flight from city2 to city1. Different data sets will be separated by an empty record (that is, a line containing only the end of line character). There will be no empty record after the last data set. The following example is stored in file C:\IOI\ITIN.DAT. 8 9 Vancouver Yellowknife Edmonton Calgary Winnipeg Toronto Montreal Halifax Vancouver Edmonton Vancouver Calgary Calgary Winnipeg Winnipeg Toronto Toronto Halifax Montreal Halifax Edmonton Montreal Edmonton Yellowknife Edmonton Calgary 5 5 C1 C2 C3 C4 C5 C5 C4 C2 C3 C3 C1 C4 C1 C5 C2 The input may be assumed correct and no checking is necessary. The solution found for each data set must be written to an ASCII output file, C:\IOI\ITIN.SOL: in the first line, the total number of cities in the input data set; in the next line, the number M of different cities visited in the itinerary, and in the next M+1 lines the names of the cities, one by line, in the order in which they will be visited. Note the first city visited must be the same as the last. If no solution is found for a data set, only two records for this data set must be written in ITIN.SOL, the first one giving the total number of cities, and the second one saying: "NO SOLUTION". A possible solution for the above example: ITIN.SOL 8 7 Vancouver Edmonton Montreal Halifax Toronto Winnipeg Calgary Vancouver 5 NO SOLUTION Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL. Problem 2.2: Once upon a time there was a gardener whose works were easy to recognize: he divided the garden in triangles and he planted flowers of the same colour in each of them. A millionaire called the gardener to design his garden so that: * each of the N beautiful fountains of his garden, numbered from 1 to N, had to be a vertex of at least one of the triangles. No fountain could be on the side of a triangle of which it was not a vertex. * a bee could fly in a straight line from any fountain to any other fountain flying continuously over flowers or fountains. * two adjacent triangles (those with a common side) always had to be planted with different colours. * once he had chosen the triangles, he had to use flowers of as few colours as possible. Write a program to solve the gardener's problem. Different data sets are written in an ASCII input file, C:\IOI\GARDEN.DAT. Each data set will look like this: N (the number of fountains) x1 y1 (coordinates of fountain 1) ...... xN yN (coordinates of fountain N) where N, xi, yi , 1 < i < N < 100, are integers. Different data sets will be separated by an empty record (that is, a line containing only the end of line character). There will be no empty record after the last data set. The solution to each data set must be written in an ASCII output file, C:\IOI\GARDEN.SOL, as follows: N (the number of fountains in the input) m (the number of triangles drawn) p (the number of colours used) r1 s1 t1 C1 (r1,s1,t1 are the fountains at the vertices of triangle 1, and C1, a number between 1 and p, is the colour of triangle 1) .................... rm sm tm Cm (rm,sm,tm are the fountains at the vertices of triangle m and Cm, a number between 1 and p, is the colour of triangle m) The input may be assumed correct, no checking is necessary. The solutions to different data sets must be separated by an empty record. The following example is stored in file C:\IOI\GARDEN.DAT. 7 -2 2 2 2 -2 -2 2 -2 0 1 1 0 -1 0 9 -1 1 0 1 1 1 -1 0 0 0 1 0 -1 -1 0 -1 1 -1 A possible solution appears below. 7 8 3 1 3 7 1 1 7 5 2 1 5 2 1 2 5 6 2 2 6 4 1 4 6 3 2 3 6 7 3 7 5 6 1 9 8 2 5 1 2 2 5 2 3 1 5 3 6 2 5 6 9 1 5 9 8 2 5 8 7 1 5 7 4 2 5 4 1 1 Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL. Problem 2.3: Imagine you are at a social get-together with at most 500 guests. The host invites you all to have dinner. There are several tables in the dining-room. The way the guests sit down at the tables is the following: each one sitting not alone at a certain table must know at least one person sitting at the same table and no one else sitting at other tables. It is supposed that if a person knows a second person, the second one knows the first person too. No one introduces himself to the other persons sitting in the same table. That means that if two persons are sitting at the same table, but initially they do not know each other, they do not know each other afterwards either. a) Determine how many tables are necessary and the persons sitting at each table. At each table there is only one person who will talk to the waiter, he is called the leader of the table. Each person relays his wishes concerning the menu to the persons he knows. The time allotted to each person to relay his wishes to each person he knows is supposed to be the same for each person. b) Find the most suitable person as leader of each table in order to receive information from all the persons sitting at the same table in the shortest possible period of time; produce at output the leader of each table. Afterwards, the host wishes to unify the tables. For this purpose, he calls some friends. Each of them, when coming, is introduced to the leaders of two tables, links the tables, sits down at the new formed table and becomes the leader of this table. c) What is the order of linking the tables in this way, so that at last all tables are unified into a single one and the conditions of point b) are satisfied? Specify the minimum necessary period of time for the leader to get information from all the other persons. After the complete linking, the friends of the host are leaving and the tables get their initial structure until the end of the dinner. When dinner is over, the persons start leaving the tables. d) Determine, for each table, the minimum number of persons and the order in which they are leaving the table, until the persons who are still at the table do not know each other. Different data sets will be separated by an empty record (that is, a line containing only the end of line character). There will be no empty record after the last data set. The following example is stored in file C:\IOI\MEETING.DAT. 8 1 2 1 3 2 4 7 6 4 3 5 6 7 1 2 1 3 2 3 4 5 5 6 6 7 C:\IOI\MEETING.SOL Table 1: 1 2 3 4 Table 2: 5 6 7 Table 3: 8 Leader table 1: 2 Leader table 2: 6 Leader table 3: 8 6 8 New leader: 9 2 9 New leader: 10 Period of time: 3 Persons leaving table 1: 2 3 Persons leaving table 2: 6 Persons leaving table 3: Table 1: 1 2 3 Table 2: 4 5 6 7 Leader table 1: 1 Leader table 2: 5 1 5 New leader: 8 Period of time: 3 Persons leaving table 1: 1 2 Persons leaving table 2: 5 6 Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL. Amalia B. de Capatto e-mail: ab@berma.org.ar Home: Naon 3099 (1430) Buenos Aires ARGENTINA TE: +54-1-5430274