Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI'97 Day 1
发信站: 哈工大紫丁香 (2002年03月29日13:56:35 星期五), 站内信件

IOI'97 Day 1
Tasks
----------------------------------------------------------------------------
----
Mars Explorer - The Game of Hex - The Toxic iShongololo
----------------------------------------------------------------------------
----
Mars explorer
In a future mission to Mars, a pod, containing a number of Mars exploration 
vehicles (MEVs), will be landing on the surface of Mars. All the MEVs will b
e released at the pod's landing site, from which they will move towards a tr
ansmitter that has landed a short distance away. While the vehicles move tow
ards the transmitter, they are required to gather rock samples. A rock may o
nly be gathered once, by the first MEV to visit the rock. After that, the ro
ck may not be gathered again, but other MEVs may pass the same position.
The vehicles cannot move onto rough terrain.
The design of the vehicle is such that it can only move south or east in a p
ath that follows the grid pattern from the pod to the transmitter. More than
 one MEV may occupy the same position at the same time.
Warning: If a MEV cannot continue to move legally before arriving at the tra
nsmitter, its samples are irrevocably lost.
Task:
Calculate the individual movement of the vehicles to maximise your score by 
maximising the number of rock samples collected and taken to the transmitter
 and the number of MEVs that reach the transmitter.
Input:
The surface of the planet between the pod and the transmitter is represented
 by a P by Q grid with the pod position always at (1,1) and the transmitter 
located at
(P, Q). The definitions of the different types of terrain are as follows:
Clear terrain: 0
Rough terrain:1
Rock sample: 2
The input file consists of:
NumberOfVehicles
P
Q
(X1Y1) (X2Y1) (X3Y1)...(XP-1Y1) (XPY1 )
(X1Y2) (X2Y2) (X3Y2)...(XP-1Y2) (XPY2)
(X1Y3) (X2Y3) (X3Y3)...(XP-1Y3) (XPY3 )
...
(X1YQ-1) (X2YQ-1) (X3YQ-1)...(XP-1YQ-1) (XPYQ-1)
(X1YQ) (X2YQ) (X3YQ)...(XP-1YQ) (XPYQ)
P and Q are the size of the grid, and NumberOfVehicles is an integer less th
an 1000, representing the number of vehicles released by the pod. Q lines ea
ch represent a row in the surface representation. P and Q will not exceed 12
8.
Sample input:
MARS.DAT Explanation:
2  Number of vehicles
10 P
8 Q
0 0 0 0 0 0 0 0 0 0 Row 1
0 0 0 0 0 1 1 0 0 0 Row 2
0 0 0 1 0 2 0 0 0 0 Row 3
1 1 0 1 2 0 0 0 0 1 Row 4
0 1 0 0 2 0 1 1 0 0 Row 5
0 1 0 1 0 0 1 1 0 0 Row 6
0 1 2 0 0 0 0 1 0 0 Row 7
0 0 0 0 0 0 0 0 0 0 Row 8
Output:
A sequence of lines representing the movements of the MEVs towards the trans
mitter. Each line contains a vehicle number and a digit 0 or 1, where 0 is a
 move South and 1 a move East.
Sample output:
MARS.OUT Explanation:
1 1 vehicle 1 moves east
1 0 vehicle 1 moves south
2 1 vehicle 2 moves east
2 0 vehicle 2 moves south
1 1 etc.
1 1
2 0
2 1
2 0
2 0
2 0  　
2 0
1 1
1 0
1 0
1 0
1 0
1 0
1 0
2 0
2 1
1 1
1 1
1 1
1 1
1 1  　
2 1
2 1
2 1
2 1
2 1
2 1  　
　
2 MEVs and 3 samples reach the transmitter for a score of 5 points out of a 
possible 5. Thus 100% score.
Scoring:
The calculation of the score will be based on the number of samples collecte
d and taken to the transmitter, with adjustments made for the arrival or non
-arrival of MEVs at the transmitter.
An illegal move invalidates a solution set and is scored as zero points. An 
illegal move occurs when a MEV is moved over rough terrain or outside the gr
id.
Score = (number of samples collected and taken to the transmitter + number o
f MEVs reaching the transmitter
- number of MEVs not reaching the transmitter) as a % of the maximum possibl
e score for the solution set.
A maximum of 100% and a minimum of 0% can be scored.
[ Return to top ]
----------------------------------------------------------------------------
----
The Game of Hex
The aim of the game is for the first player to connect a hex counter owned b
y her on column 1 to a hex counter owned by her on column N.
Rules of Hex:
Hex is a two player strategy game played on a NxN rhombus of hexagons, as il
lustrated here for N=6.
The two players of the game are your program and the evaluation library.
Your program always has the first move.
Players alternately place hex counters on the board.
A hex counter may be placed at any open position on the board.
Two hexagons are adjacent if they share an edge.
Hex counters on adjacent hexagons of the same player (contestant next to con
testant, or evaluator next to evaluator) are connected.
Connectivity is transitive (and commutative): if hex1 is connected to hex2 a
nd hex2 is connected to hex3 then hex3 is connected to hex1 and hex1 is conn
ected to hex3.
Task:
You are required to write a program which plays the game of Hex.
The goal of the first player (your program) is to connect a hex counter of y
ours on column 1 to a hex counter of yours on column N.
The other player (evaluator's program) attempts to connect an evaluator's he
x counter on row 1 to an evaluator's hex counter on row N.
If your program plays optimally, it will always win.
Input and Output:
Your program must not read from or write to any files. Your program must not
 receive keyboard input, and must not produce output on the screen. It will 
receive all its input from the functions in the hex library. The library wil
l produce an output file named HEX.OUT; you should ignore its contents.
At the start of the game your program will be presented with a board that ma
y have hex counters already placed, representing a state of a game such that
 the first player may still win. Your program must use the functions GetMax 
and LookAtBoard to determine the state of the board.
At the start of the game, an equal number of hexes belongs to the evaluation
 program and your program.
Constraints:
The size of the board will always be in the range 1 to 20 inclusive.
Your program may have to make up to 200 moves to complete a game. The entire
 game must be finished within 40 seconds. It is guaranteed that the evaluati
on library will complete its processing within 20 seconds.
Library:
A library called HexLib is provided which you must link to your code. An exa
mple file, for each programming language, showing how this is done is includ
ed in the task directory. These files are TESTHEX.CPP, TESTHEX.C, TESTHEX.PA
S, and TESTHEX.BAS. If you are using QuickBasic you must include the library
 by typing
QB /L HEXLIB
The functions in HexLib are:
(in order of Pascal, C/C++ and Basic respectively)
function LookAtBoard (row, column: integer): integer;
int LookAtBoard (int row, int column);
declare function LookAtBoard cdecl (byval x as integer, byval y as integer)
Returns
-1 if row<1 or row>N or column<1 or column>N
0 if there is no hex counter at the position
1 if the hex counter at the specified position belongs to your program (play
er 1)
2 if the hex counter at the specified position belongs to the evaluation lib
rary (player 2)
procedure PutHex (row, column: integer);
void PutHex (int row, int column);
declare sub PutHex cdecl (byval x as integer, byval y as integer)
Places a contestant's hex counter at the specified row and column if the pos
ition is not occupied.
function GameIsOver: integer;
int GameIsOver (void);
declare function GameIsOver cdecl ()
Returns one of the following integers
0 the game is not over.
1 every position on the board is occupied by a hex counter.
2 your program has won.
3 the evaluation library has won.
procedure MakeLibMove;
void MakeLibMove(void);
declare sub MakeLibMove cdecl ()
Allows the evaluation library to calculate its next move and places its hex 
counter on the board. The change to the board will be indicated by LookAtBoa
rd and the other functions.
function GetRow: integer;
int GetRow (void);
declare function GetRow cdecl ()
Returns the row of the hex counter placed by the evaluation library, or -1 i
f no hex counter has been placed yet. This function always returns the same 
value until your program calls MakeLibMove again.
function GetColumn: integer;
int GetColumn (void);
declare function GetColumn cdecl ()
Returns the column of the last hex counter placed by the evaluation library,
 or -1 if no hex counter has been placed yet. This function always returns t
he same value until your program calls MakeLibMove again.
function GetMax: integer;
int GetMax (void);
declare function GetMax cdecl ()
Returns the size of the board, N.
Scoring:
If your program wins a game, it will score full marks for that data set.
If your program loses a game, it will score 20% for that data set.
If your program terminates before the end of a game or runs out of time, it 
will score 0 for that data set.
[ Return to top ]
----------------------------------------------------------------------------
----
The Toxic iShongololo
“iShongololo” is the Zulu name for a millipede. They are long, shiny, blac
k arthropods with many legs.
The iShongololo eats through an edible “fruit” which for the sake of this 
problem can be considered a rectangular solid with integer dimensions of L (
length), W (width) and H (height).
Task:
You are required to write a program that maximizes the number of blocks eate
n by the iShongololo without violating the constraints given. The program mu
st output the actions that the iShongololo makes as it eats its way through 
the fruit.
The iShongololo starts outside the fruit. The first block the iShongololo mu
st eat is 1, 1, 1 and it must then move to this block. It stops when no more
 blocks can be legally eaten and it can no longer move.
Constraints:
The iShongololo occupies exactly one empty block.
The iShongololo can only eat one complete block at a time.
The iShongololo cannot move to a position where it has previously moved to (
that is, move backwards or cross its path).
The iShongololo cannot move to a solid (uneaten) block, or outside the fruit
.
The iShongololo may only move to or eat blocks with whom it shares a face. I
t may only eat blocks which have no other faces exposed to empty eaten block
s.
Input:
As input your program will receive three numbers (integers) which are the le
ngth (L), width (W) and height (H) of the solid.
The three integers L, W, H, are each on a separate line. The three integers 
will be between 1 and 32 (inclusive).
Sample input:
TOXIC.DAT Explanation:
2
3
2  Length of solid is 2.
Width of solid is 3.
Height of solid is 2.
Output:
The output consists of lines that begin with “E” (eat) or “M” (move) fol
lowed by 3 integers that represent the block eaten or moved to on the axes c
orresponding to L, W, H.
For example the following is a valid solution for the input example.
Sample output (this may not be optimal):
TOXIC.OUT Explanation:
E 1 1 1
M 1 1 1
E 2 1 1
E 1 1 2
E 1 2 1
M 1 2 1
E 1 3 1
M 1 3 1
E 2 3 1
E 1 3 2
M 1 3 2  Eat the block 1 1 1
Move to the block 1 1 1
Eat the block 2 1 1
Eat the block 1 1 2
Eat the block 1 2 1
Move to the block 1 2 1
Eat the block 1 3 1
Move to the block 1 3 1
Eat the block 2 3 1
Eat the block 1 3 2
Move to the block 1 3 2
Scoring:
If the iShongololo violates the constraints, then your solution receives 0 p
oints.
The total score is the percentage of blocks eaten as a proportion of our bes
t known solution.
A solution cannot score more than 100%

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]