//
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

1990 – International Olympiad in Informatics

MINSK,BYELLORUSSIA, 1990 

Round 1. 
 
PROBLEM 1. 
Program the process transforming figure arrangement in A 
into that in B. A figure in a cell can be transferred 
into any one of neighbouring empty cells; in the case of 
such transformations the cell previously occupied by the 
figure becomes empty. 
+----+----+----+----+ 
|  7 |  3 |  5 | 14 | 
+----+----+----+----+ 
|    |  4 |  9 | 13 | 
+----+----+----+----+  --------> 
|  1 |    |  2 | 10 | 
+----+----+----+----+ 
| 11 |  8 | 12 |  6 | 
+----+----+----+----+ 
          A 
		+----+----+----+----+ 
		|  1 |  2 |  3 |  4 | 
		+----+----+----+----+ 
		|  5 |  6 |  7 |  8 | 
		+----+----+----+----+ 
		|  9 | 10 | 11 | 12 | 
		+----+----+----+----+ 
		| 13 | 14 |    |    | 
		+----+----+----+----+ 
		          B 
 
 
PROBLEM 2. 
The game of "BOXES" involves players joining dots in a 
gird one at a time. The player who completes a box scores 
a point and is entitled to another turn. The end of the 
game is when the grid has been completed with the winner 
naturally being the one with the more points. Only 
vertical and horizontal lines filling the space between 
two points are allowed. 
The example below shows a game between Red and Blue which 
is half completed: 
o----o    o----o----o 
|    |    |    |    | 
o----o----o----o----o 
|         | 
o    o    o    o----o 
| 
o----o    o----o    o 
     |              | 
o    o    o    o----o 
This can be represented with R & B showing lines filled 
by Red and Blue with O indicating a 'vacant' line: 



  R    O    B    R 
B    R    B    B    B 
  B    B    R    R 
R    O    R    O    O 
  O    O    O    B 
B    O    O    O    O 
  B    O    R    O 
O    R    O    O    R 
  O    O    O    B 
This is then condensed to produce the matrix shown below: 
ROBR 
BRBBB 
BBRR 
ROROO 
OOOB 
BOOOO 
BORO 
OROOR 
OOOB 
1. Write a program which scans a matrix of the type shown 
  above (which will ALWAYS represented a 5 x 5 point grid) 
  and determines the number of 3- sided boxes (of ANY 
  orientation). Data should be read from a single file as a 
  series of 9r lines representing r games which is 
  terminated by the word END starting a separate line. Your 
  program should output a one line message for each matrix 
  in the data: 
  MATRIX r contained x 3-sided box(es). 
2. Modify your answer to Part 1 to continue a single game 
  on behalf of Blue. Complete as many boxes as the single 
  move allows (bearing in mind that a complete box means 
  another move). The final move is irrelevant but should 
  NOT result in a 3-sided box unless forced to do so. 
  Your program should return: 
  x boxes have been completed. Final move = L, C where L & 
  C are the Line and Column representing the character in 
  the matrix and x should be the number NEW boxes which 
  have been formed, but NOT the total number of complete 
  boxes in the grid. 
 
 
*** PROBLEM 3. 
There are N books and two readers, A and B, wanting to 
read these books. Nonnegative integers A[I] and B[I] are 
given such as reader A (or B) needs A[I] (or B[I], 
respectively) hours to read book I, 1<=I<=N. Both the 
readers begin reading at time 0. At any time each reader 
is allowed to read at most one book and both readers 
cannot read the same book. 
Integer K, 2<=K<=N, is given and the books are supposed 
to be numbered in such a way that no reader can start 
reading book J, 2<=J<=K, until book J-1 is read by both 
the readers. 
The order of reading the other books is immaterial for 
each reader and may be arbitrary. 
Preemptions are allowed in the process of reading any 
book by any reader. It means that this process may be 
interrupted at any integer time and be resumed lately 
starting from the point of interruption. In between 
interruption and resumption of the process of reading the 
book a reader may read any other book he has not 
completed and has the right to read it. 
IT IS NECESSARY: 
1. To organize inputting the data in the form: 
  < ENTER  N -->  > 
  < ENTER  K -->  > 
  < ENTER: > 
  < A[1] --> >  < B[1] --> > 
  < A[2] --> >  < B[2] --> > 
  .......................... 
  < A[N] --> >  < B[N] --> > 
2. To find the largest possible time T before which all 
  the books cannot be read by both the readers; to output 
  calculated value of T. 
3. To build a schedule of reading the books by each 
  reader which meets all the restrictions listed above and 
  under which the process of reading all the books 
  terminates at time T. The schedule for each reader is to 
  be written in the form. 
     < SCHEDULE FOR READER A ( or B ) > 
  < Book >  < Start > < Finish > 
    .....     .....     ..... 
    .....     .....     ..... 
  In the tables of the above form all the time intervals 
  within which reader A (or B) is reading a book and the 
  number of this book should be mentioned. 
4. Output the number of preemptions of each reader. Try 
  to reduce the number of preemptions for each reader. 
 
 
PROBLEM 4. 
It's given integer number K. 
A strip of paper is divided into N cells (K<=N<=40). Two 
players choose and cross out K empty adjacent cells one 
by one. The winner is the one who has made the last move. 
  1    2                             N 
+----+----+----+----+-        -----+----+ 
|    |    |    |    |   . . .      |    | 
+----+----+----+----+-        -----+----+ 
1. Input N and define, whether player 1 has winning 
  strategy (i.e. whether he can win under the best 
  following moves of player 2). Print message "Player 1 has 
  winning strategy" or "Player 1 doesn't have winning 
  strategy". 
2. Define for given N, if player 1 has winning strategy, 
  if his 1st move is entered into the computer from 
  keyboard. 
3. Make the game for given (paragraph 1 and 2) N and 
  player's 1 first move. Programme plays for player 2. 
  Moves of player 1 are entered from the keyboard. 
  Move is given by index of cell L (1<=L<=N-K+1). Cells 
  from L till L+K-1 are crossed out while doing this. After 
  each move current position of the game is printed out in 
  the form of: 
  1  2*  3*  ...  N 
  Index number is printed upside, crossed out cells are 
  marked by symbols '*'. 
  You must print 'Victory of Player 1 (Player 2)' when the 
  game is over. Entering N and K print message 'N>' and 
  'K>'. 
  Entering move print 'Move of Player 1>'. 
  Foresee the control of correctness of input data. 
 
 
PROBLEM 5. 
  [ PROLAN/M ] 
Suppose that the NePhihhan hardware company has developed 
a new RISC micro-processor capable to handle a single 
data type - string of characters - and to perform a 
single operation on them-context-sensitive replacement 
(searching a given substring in a string and replacing it 
by another substring). Two memory areas are used, one of 
each contains the program (a list of discriptions of the 
possible replacements), while the other one (we will call 
it R; its size is supposed to be virtually unlimited) is 
used to store the input data, the intermediary results 
and the final output. 
The programs for the processor are written in a language 
which we will call PROLAN/M. Before we describe it 
formally, we will give an example of a program: 
(aa,b) (ba,a) (bc,a) (c,start) (d,) (b,finish) (,) 
When executed string     abcabcd 
as input, the programs yields the string     finish 
as a final value, while the contents of R goes through 
the values 
     abcabcd, aaabcd, babcd, abcd, aad, db, b, finish 
successively. 
Now to the formal description of the syntax of PROLAN/M 
(we use "::=" to denote "is defined as" and ":" to denote 
"or"): 
<'PROLAN/M'-program>     ::=  <substitut.sequence>(,) 
<substitut.sequence>     ::=  <substitution>: 
     ::=  <substitut.sequence><substitution> 
<substitution> ::=  (<left part>,<right part>) 
<left-hand part>    ::=  <string> 
<right-hand part>   ::=  <string>:<empty> 
<string>  ::=  <string symbol>:<string><string symbol> 
<empty string> ::= 
<string symbol>     ::=  <any ASCII character except ',' 
, ')' > 
After the input string has been loaded into R, the 
program is executed in the following way: the processor 
looks for the first <substitution> in the 
<substitut.sequence> for which the <left-hand part> is a 
substring of the string in R. If the search is 
successful, the <right-hand part> of the same 
<substitution> replaces the corresponding substring in R 
(the leftmost one if not unique). This procedure is then 
repeated from the beginning with the new R-value until mo 
<left-hand part> in the <'PROLAN/M'-program> is found as 
a substring in a current value R, which is then 
considered to be the final result, and the execution is 
aborted. 
--------------------------------------------------------- 
Problem 1. 
  Write and debug a PROLAN/M program that converts a string 
  of the type 
  <nat.nr1>+<nat.nr2>=? 
  (<nat.nr1> and <nat.nr2> are sequences of decimal digits 
  representing natural numbers) to a string of the type 
  <nat.nr1>+<nat.nr2>=<nat.nr3> 
  containing a mathematically correct statement (<nat.nr1> 
  and <nat.nr2> are the same). For example, the string 
  1990+123=? 
  should be transformed into 
  1990+123=2113 
  at the end of the execution. Store your program in a file 
  named SUM.PRM. 
Problem 2. 
  Write a PROLAN/M debugger. It should able to do the 
  following: 
  (a) request the name of a text file containing the 
    PROLAN/M program; 
  (b) request the initial contents of R; 
  (c) perform the transformations of the input string 
    according to the program in the file; 
  (d) display the result on the screen; 
  (e) it is desirable to enable a tracing mode. 
--------------------------------------------------------- 
Your grade for P.1 will depend on the number of 
<substitutions>s in the <substitution sequence>, as well 
as on the speed at which the tests which will be given by 
the jury will be performed. Therefore you may wish to 
hand in two versions of the program, each of which will 
be better at satisfying a different criterion. 
The program from P.1 will be tested using a programming 
system designed by the jury for this special purpose. 
Your grade for P.2 will depend on passing the jury's test 
and on your having implemented all the subproblems. 
 
 
PROBLEM 6. 
Given integers a and n (n<100). Suppose an imaginary 
programming language containing an assignment statement 
and a multiplication operator. Write a program that 
generates a text in that language for computation of 
b=a^n, with minimal number of multiplications. An example 
of generated text for n=13, where each pair of brackets 
{} contains comments, is presented below: 
X1:=a;    {=a} 
X2:=X1*X1;     {=a^2} 
X3:=X2*X2;     {=a^4} 
X4:=X3*X1;     {=a^5} 
X5:=X3*X3;     {=a^8} 
X6:=X5*X4;     {=a^13} 
b:=X6; 
 
********************************************************* 


2nd International Olympiad in Informatics 
MINSK, 1990 
Round 2. 
 
 
PROBLEM 1. 
Each watchman in a certain art gallery is on duty during 
some continuous time period. The Guard Schedule is 
defined to be a set of pairs [T1(i),T2(i)] - the starting 
and the ending times of the i'th watchman's duty. Given a 
Guard Schedule you are required: 
(a) To check whether there are at least two watchman in 
  the gallery at each moment of the period [0, EndTime]. 
  If the condition (a) is not fulfilled, 
(b) Determine all the periods when the guard is 
  insufficient (less then two watchmen on duty). 
(c) Find the minimal number of additional watchmen with 
  duties of a prescribed equal length needed to obtain a 
  valid Guard Schedule, i.e. one with condition (a) 
  fulfilled. 
INPUT: 
 (All times are given in integer minutes.) 
 EndTime   -    the time when the guard is over, i.e. the 
   gallery should be guarded within the period [0, EndTime]. 
 N    -    the number of watchmen. 
 T1[i]. T2[i], i=1, ..., N     -    the starting and the 
   ending times of the i'th watchman's duty. 
 Length    -    the prescribed length of the duty for each 
   additional watchman. 
OUTPUT: 
 (1) The answer for point (a) in the form "Yes/No". 
 (2) If the previous answer is "no", the list of pairs 
 (k,1) - the beginnings and the ends of all time periods 
   with insufficient guard, and the number of watchmen in 
   each (0 or 1). 
 (3) The number of additional watchmen and the list of 
   starting and ending times of every additional watchman's 
   duty. 
 
 
PROBLEM 2. 
N segments are given on the plane by the co-ordinates of 
their endpoints, N>0. Endpoints of segment are specified 
by two pairs (x1[i], y1[i]), and (x2[i], y2[i]), 1<=i<=N. 
The endpoints of any segment are belong to it. 
You are required: 
1. To organize inputting the data in the form kind of 
  <Enter N -- the number of segments :> 
  <Enter co-ordinates of i'th segment:> 
  x1[1]--> y1[1]--> 
  x2[1]--> y2[1]--> 
    :::      ::: 
2. To find a straight line which has common points with 
  as many segments as possible. Any of the common points is 
  allowed to be an endpoint of a segment. To output in 
  increasing order the number of the segments that have 
  common points with found straight line. 
 
 
***PROBLEM 3. 
Nodes numbered by 1, 2, ..., N (N<=50) are connected by a 
network of roads, each of which is of length 1. The roads 
are going at different heights and are intersected at the 
nodes only. At the initial moment 0 there are robots in 
some of the nodes. The total number of the robots is M (M 
= 2 or 3). The robots keep moving continuously from one 
node to another independently and can change the 
direction of their moving at the nodes only. The robots 
are not allowed to stop. The speed of the i'th robot 
equals speed[i] (speed[i] = 1 or 2). The robots are being 
controlled in such way as to minimize the time all of the 
robots need to get together at the same place. 
You are required to find the minimal time T after which 
the meeting of all the robots at the same place can occur 
and to indicate this time T, or else to determine that 
the meeting of all M robots at the same place is 
impossible at any time t>=0. 
The form of the input should be: 
<Input N:> 
<Input number of roads K:> 
<Road 1 connects points:> 
     ... 
<Road K connects points:> 
     (pairs are input as I J) 
<Input number of robots M:> 
<Input speed of robot 1:> 
     ... 
<Input speed of robot M:> 
<Input initial position of robot 1:> 
     ... 
<Input initial position of robot M:> 
     (All numbers above must be non-negative integers.) 
The form of output is 
<Time = ...> 
 


 
PROBLEM 4. 
All streets in a certain rectangular-shaped city situated 
in an uneven area are going either from south to north (N 
streets) or from west to east (M streets), so that the 
city is divided into square blocks with sides equal to 1. 
Every segment of a street enclosed between two 
neighbouring crossings goes either only down or only up, 
or else it may be horizontal. 
Matrix K[y,x] (with dimension MxN) contains the heights 
of the crossings above the sea level. 
     /\ Y 
     | 
M    +---+---+---+---+---+---+ 
     |   |   |   |   |   |   | 
     +---+---+---+---+---+---+ 
.    |   | A |   |   |   |   | 
.    +---+---o---+---+---+---+ 
.    |   |   |   |   |   |   | 
     +---+---+---+---+---+---+ 
     |   |   |   |   | B |   | 
2    +---+---+---+---*---+---+ 
     |   |   |   |   |   |   | 
1    +---+---+---+---+---+---+--------->X 
     1   2      ...          N 
You are required to write a program that: 
1. Inputs dimension of matrix - M and N. 
2. Inputs the matrix elements H[i,j]. i=1,M , j=1,N. 
3. Inputs the coordinates of two crossings - A and B. 
4. Reports the answer to the question whether it is 
  possible to move from A to B or from B to A, going down 
  all the time. 
  If the answer to the question from P.3 proves to be 
  affirmative, the program also 
5. Determines at least one such path and displays the 
  coordinates of the crossings involved on the screen. 
6. Determines all paths of this kind. 
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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

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

NCT Computer

Flickr Photos

Merle running

Sentinels

Papilio Machaon...

More Photos

Thống kê

  • 136,495 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: