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)