发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: IOI's 1990 Problems
发信站: 哈工大紫丁香 (2002年03月29日13:17:58 星期五), 站内信件
2nd 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.
--
不在乎天长地久，就怕你从来没有！
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]