3rd International Olympiad in Informatics ATHENS,GREECE, May 19-25, 1991 I. PLAYCARD PROBLEM A pack of cards consists of 52 cards, which have 13 different values 1,2,3,4,5,6,7,8,9,10,J,Q,K, and four different suits: Spades, Clubs, Diamonds, Hearts (Spade and Club are black, Diamonds and Hearts are red). We have a pack of full cards, which we shuffle. Pulling out successively 12 cards of the pack we create 3 rows of 4 cards each, which we place on the table. If, in that phase, we pull out a J, Q or K we put that card at the end of the pack and continue pulling out cards until 3 rows of 4 cards each are completed. We now proceed checking if among the cards, we have put on the table, there are pairs of cards whose values give 10 as sum. If there are two cards with the value of 10 each, one of them is considered as having value 0. On the above pairs of cards we place two cards of the pack ( one on each card of the pair ). If during this phase we pull out a J, Q or K we place this on one card of the pair and this card does not take part in the procedure any more. The procedure continues until the 12 faces of the cards are covered by J,Q,K or there are no more pairs of cards with sum 10. Write a program which simulates the above procedure with the following demands: 1. - The number N of repetitions of the above procedure must be entered from the keyboard. When N equals 1, each of 2,3 and 4 below takes place. 2. - (a) The pack of cards must be created and, for each repetition the pack of cards must be shuffled by the program. (b) The pack of cards must be displayed on the screen. 3. - (a) The 12 cards must be placed on the screen according to the procedure described above. (b) The remaining cards in the pack must be displayed on the screen. 4. - (a) The cards that are covered according to the above procedure must be replaced with the cards that replace them and this must be shown on the display. (b) After each replacement, the remaining cards of the pack must be displayed on the screen. 5. - After 5 repetitions, a histogram must be presented which will display the number of cards which remain in the pack after the end of each procedure. Evaluation: 1 10 points 2(a) 15 points (b) 5 points 3(a) 10 points (b) 5 points 4(a) 10 points (b) 5 points 5 15 points Code 10 points Jury 15 points --------------------------------------------------------- II. TREES PROBLEM A farmer wants to preserve a rare class of ancient cypress trees. In order to do that he has taken note of the position of each tree and he has decided to surround the trees with wire drawing a polygon such that they lie entirely inside it. In order to reduce his costs, he needs to minimize the length of wire. The farmer wants to build a rectangular house, one of its sides being parallel to the X-axis, and he needs to know the relative location of the house: (1) The house is outside the polygon. (2) The house is inside the polygon. (3) The wire divides the house in two regions whose areas are different from zero. Write a program capable of accomplishing the following tasks: (A) Finds the trees that will be the vertices of the polygon. (B) Calculates the length of wire that will be used. (C) Indicates in which of the above mentioned locations (1,2,3) the farmer's house is. Input: - N: The number of the trees. - (Xi,Yi) 1<=i<=N, N<=20, Xi,Yi>0; The coordinates of the points corresponding to each tree. - (a,b), (c,d), a,b,c,d>0; The beginning and ending points of the house's main diagonal. Output: - A sequence of M points (1<=M<=N) with the property that if we trace through the points in the order in which they appear, we trace the outline of the polygon. - The length of wire that will be used. - The indication of the position of the house in the form "1","2", or "3". Evaluation: Input 10 points A 40 points B 10 points C 30 points 10 points reserved for the Jury --------------------------------------------------------- III. ***SQUARE PROBLEM (Selected for the 1st round) Enumerate the position of a 5x5 matrix, in the following way: If the number i (1<=i<=25) has been assigned to a matrix position with coordinates (x,y), then the number i+1 can be assigned to the matrix position with coordinates (z,w) according to one of the following rules: (1) (z,w) = (x+-3,y) (2) (z,w) = (x,y+-3) (3) (z,w) = (x+-2,y+-2) The problem is: (A) Write a program that enumerates the positions of the 5x5 matrix for a given starting position with the number 1. (B) Compute the number of all possible enumerations for every starting position at the upper right part of the matrix, including the maindiagonal. Example: If the matrix position with coordinates (2,2) is selected as the starting position, then the next matrix position to which number 2 will be assigned, can be one of the following positions with coordinates: (2,5) or (5,2) or (4,4). These positions are marked in figure 1 by an asterisk (*). 1 2 3 4 5 +---+---+---+---+---+ 1 : : : : : : +---+---+---+---+---+ 2 : : 1 : : : * : +---+---+---+---+---+ 3 : : : : : : +---+---+---+---+---+ 4 : : : : * : : +---+---+---+---+---+ 5 : : * : : : : +---+---+---+---+---+ Note: It will be appreciated if the output looks like the one in Figure 1. Evaluation: (A) 50 points (B) 25 points Output 15 points 10 points reserved for the Jury. --------------------------------------------------------- IV. LANGUAGES PROBLEM You are given an ASCII text file which contains some natural language text (eg. English, French, German, etc.) where the language used is unknown, but the characteristic of the language is the Latin style (Latin alphabet). The problem is: Analyze the contents of this file to determine the language used. (A) Write a program which will read the contents of the file and count the number of characters in it. Print the total. (B) Modify the program in (A) to also count the number of occurrences of each letter of the alphabet, converting delimiters and punctuation to the space (' ') character, and lowercase characters to uppercase ones, i.e. the only characters considered in the count will be elements of the set [' ','A'..'Z']. Sort the characters in this set in order of frequency, i.e. the most frequently occurring characters appearing at the start of the list. Print the sorted list out. (C) Modify the program written in (B) to count the frequency of characters. Normalise the counts, i.e. divide the frequency of each character by the total number of characters read; this will give you a relative frequency which is independent of the number of the characters in the text. Write the relative frequency counts to a data file. (D) Extend the program written in (C) so that it may accept to read a text data file and compare it with given text files of known languages. The comparison method will be of your own invention. The result should be a report of the language which the program thinks the original text is written in. Note: The given text files of the known languages are under the names ITA, FRA, etc. for Italian, French, etc. respectively. The text data file has the name TEXT. Evaluation: (A) 10 points (B) 20 points (C) 20 points (D) 40 points 10 points reserved for the Jury. Sample text: Morire in consequenza di anabolizzanti intrapresa per migliorare le proprie prestazioni atletihce 'e poi molto diverso dal morire al volante di un'auto di formula uno mentre si tentra di battere un record affrontando i rischi legati a quelle prove, o dal perire vittime di una scarica di sassi mentre si tenta una prima salita su una parete Nord di qualche colosso alpino? Che ci sia o no di mezzo la farmacologia, l'artificiale,il chimico, conta relativamente poco,sul piano essenziale, anche se sembra molto rilevante dal punto di vista dell'immaginario cillettivo; il quale ancora considera spesso un eroe il pilota di auto da corsa o il grande alpinista, e ha invece un atteggiamento molto diverso nel caso di chi perisca vittima di un doping incauto. Naturalmente , qui entrano in gioco altri elementi,solo indirettamente morali. Fare uso di stimolanti chimici 'e in genere vietato nello sport, chi viola questa norma commette una grace slealta: ma qui l' esecrazione morale non 'e motivata anzitutto dal fatto che viene messa a repentaglio l'integrita fisica dell'atleta, bensi dal mancato rispetto per regole del gioco. Le quali, per altro,vietano il doping anche e soprattutto per il danno fisico che esso alla lunga provoca; ma in base allo stesso principio, forse, dovrebbero vietare anche pratiche sportive "leali" e tuttavia non memo pericolose per chi le pratica.. --------------------------------------------------------- V. *** S-TERMS PROBLEM (Selected for the 2nd round) An s-term is a sequence of S's and parentheses defined recursively as follows: S is an s-term, and if M and N are s-terms, (MN) is also an s-term. Example of an s-term: ((((SS)(SS))S)(SS)) The right parentheses provide no new information, so they can be omitted, i.e. (MN instead of (MN), so that the previous s-term becomes: ((((SS(SSS(SS 1. Write a procedure 'gensterm' to generate s-terms: your procedure should generate n (n=length=number of S's) textfiles containing all s-terms of length 1,...,n respectively. S-terms should be separated by ";". The end of the last s-term in each file should be marked with ".". Write a program that accepts an integer n(<=10), uses the above procedure and displays all generated s-terms on the screen. Consider a calculus with s-terms. The only algebraic rule (s-rule) that can be used is the following: any subterm of an s-term that has the form (((SA)B)C) (where A,B and C are s-terms) can be rewritten as: ((AC)(BC)) i.e. Context1(((SA)B)C)Context2->Context1((AC)(BC))Context2 The application of this rule on an s-term is called 'reduction' of the s-term. There are different ways (strategies) of choosing a subterm to apply the s-rule. The succesive application of the s-rule on an s-term until no more applications of the s-rule are possible is called 'normalization' of the s- term. Example of a reduction chain: ((((SS)(SS))S)(SS)) -> (((SS)((SS)S))(SS)) -> ((S(SS))(((SS)S)(SS))) -> ((S(SS))((S(SS))(S(SS)))) 2. Choose an appropriate data structure for representing s-terms which can facilitate the application of the s-rule. Write two procedures 'readterm' and 'printterm' that transform s-terms to (and from) your representation from (and to) the form generated by 'gensterm'. Your program should be able to demonstrate these transformations. 3. Write a procedure 'reduce' to perform one reduction step according to the s-rule on a specified subterm of an s-term given in yout representation. Your program should be able to demonstrate this. 4. Write a procedure 'normalize': given an s-term, it should repeatedly choose a subterm to apply the s-rule, until no further reducations are possible or until the number of reduction steps exceeds some maximum, e.g. 30. Your program should be able to demonstrate this. 5. Finally, incorporate all of the above in a program that: a) requests a length n from the user, b) uses s-terms of length n, generated by 'gensterm', c) transforms s-terms into your representation, d) normalizes (if possible), e) outputs the resulting (normalized) s-terms, f) outputs the number of reduction steps performed for each s-term, or a 'not normalized' message in case of unsuccessful normalization in 30 steps, and g) outputs the number of not normalized vs. the total number of s-terms for the given length n. EVALUATION: (1) 20 points (2) 25 points (3) 15 points (4) 20 points (5) 10 points Jury 10 points (clearity, elegance, style) ----------------------------------------------------- VI. MAXIMUM GANG A Police captain knows well all the outlaw persons of his city, as well as, every possible collaboration among them. He would like to find the maximum gang of the city. In this case, a gang is a subset of outlaw persons so that any person in it collaborates with all others in the subset. Maximum gang means that there does not exist another gang with greater cardinality. Create a program capable of carrying out the following tasks: (A) Accept the police captain's data with a total number of outlaw persons less than 41. Use as input data file an ASCII one with the following structure: a(1,1) a(2,1)a(2,2) a(3,1)a(3,2)a(3,3) ........................ a(n,1)a(n,2)a(n,3)..........a(n,n) where a(i,j)=1, if person i is collaborating with person j or i=j, and a(i,j)=0, otherwise. For instance (in the case of 6 persons): 1 01 101 1011 01101 101111 In this example an output can be the following one: A Maximum Gang is : 1 3 4 6 cardinality = 4 (B) Extend the input part of the program, so that to generate data in a random way under a given pro- pability 0 < d < 1 of collaboration of outlaw persons. (C) Using random data or input file, find the maximum gang of the city. Use the same output format as in the example above ( see task A ). EVALUATION (A) 5 points (B) 15 points (C) 50 points Total Machine Time 20 points Jury 10 points --------------------------------------------------------- VII. MEDICAL VISITOR'S REGISTER A medical visitor would like to have a program which would schedule all his medical appointments and help him meet as many doctors as possible in one day in order to advertise the medical products of the company he represents. You are asked to write the program which would do this task for him. The input file consists of lines, each of which contains the name of a doctor, the beginning and the end of the interval when the doctor is ready to meet the medical visitor, as well as the name of his medical institute. The rules for scheduling the appointments are as follows: 1. An appointment has at least 70 minutes duration; furthermore the medical visitor needs at least 30 minutes between any two appointments to travel to the next medical institute. 2. All the times in the input file belong to the same day, and the medical visitor does not want to meet any doctor twice on the same day. 3. Also, two consequtive appointments cannot be held at the same institute. 4. Among several doctors the medical visitor always prefers the one whom he can meet earlier. 5. If there is more than one doctor whom the medical visitor would be able to meet at the same time (either because by the time he finishes from the previous appointment there are doctors already waiting or because their proposed appointment would begin later but at the same time during the day) he prefers the one who has less remaining time for the given day ( but of course this time at the beginning of the appointment must be enough for the required 70 minutes). 6. To visit as many doctors as possible, the medical visitor always ( even during an appointment ) keeps in mind the next appointment's starting time, therefore if it is necessary he can terminate the on-going appointment after the minimal 70 minutes expire, take his 30 minutes for traveling and begin the next appointment according to rule 5. 7. If he is not in a hurry for a new appointment (according to rule 6 ), the medical visitor stays with a doctor as long as he can. Input file: consists of lines each of which contains a name ( with the English alphabet ), a blank space , a time ( in hh.mm form ) indicating the possible beginning of an appointment, a dash ('-'), a time again indicating the last possible moment of the appointment, a blank space, and a name (with the English alphabet) of the medical institute. The input file does not contain empty lines, nor is the end of it marked with special characters. A possible input file is as follows: Bob 16.00-17.25 Cross John 09.30-11.50 Health Charles 11.00-20.00 Chest Don 08.00-13.20 Cross Norman 22.00-23.05 Brain Jerry 10.00-17.00 Health Charles 09.20-10.40 Orthopedic Evelyn 19.15-20.40 Orthopedic Peter 09.35-11.55 Brain Don 18.00-20.00 Eye Output file: should contain a table in which all the possible appointments appear in their proposed chronological order. The appointments which are ruled out by any of the rules above should not appear in the table. The table should consist of lines containing the realizable beginning and end time of the possible appointments, their place, and the proposing doctor's name. The exact spacing of the output table is not important, but should look similar to the one below. The output for the previous input file is as follows: 08.00-09.10 Cross Don 09.40-10.50 Health John 11.20-12.30 Chest Charles 13.00-15.30 Health Jerry 16.00-17.25 Cross Bob 19.15-20.40 Orthopedic Evelyn 8. Solve the above problem for two medical visitors A and B preserving the same scheduling rules and the additional restriction that they are not allowed to visit the same doctor. Each time an appointment is available, it is taken by that medical visitor who has been free for the longest period. If both have been free for the same time period, Mr. A takes the appointment. The output consists of two appointment lists. Evaluation: One medical visitor 45 points Two medical visitor 45 points Jury 10 points (elegance, clarity, progr. style)