//
you're reading...
Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Đề thi Tin học quốc tế IOI

1991 – 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) 
 

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 209,568 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: