Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI's 1994 Problems
发信站: 哈工大紫丁香 (2002年03月29日13:22:08 星期五), 站内信件

The IOI'94 Competition
Index
Here is the index of problems for IOI'94.
Day 1 Problem 1
Day 1 Problem 2
Day 1 Problem 3
Day 2 Problem 1
Day 2 Problem 2
Day 2 Problem 3
The Problem Set for IOI'94
Here is the problem set for IOI'94. For each problem, the number of tests, t
he number of points per test, and the maximum execution time is given.
　
Day 1 (5 hours)
Problem 1: The Triangle
There are 6 tests. Each successfully completed test gives 5 points. Therefor
e the maximum number of points for this problem is 30. The maximum execution
 time is 30 seconds per test.
　
Problem 2: The Castle
There are 5 tests. Each successfully completed test gives 6 points. Therefor
e the maximum number of points for this problem is 30. The maximum execution
 time is 30 seconds per test.
　
Problem 3: The Primes
There are 4 tests. Each successfully completed test gives 10 points. Therefo
re the maximum number of points for this problem is 40. The maximum executio
n time is 90 seconds per test.
The maximum number of points for the first day is 100.
　
Day 2 (5 hours)
Problem 1: The Clocks
There are 5 tests. Each successfully completed test gives 6 points. Therefor
e the maximum number of points for this problem is 30. The maximum execution
 time is 30 seconds per test.
　
Problem 2: The Buses
There are 6 tests. Each successfully completed test gives 5 points. Therefor
e the maximum number of points for this problem is 30. The maximum execution
 time is 30 seconds per test.
　
Problem 3: The Circle
There are 8 tests. Each successfully completed test gives 5 points. Therefor
e the maximum number of points for this problem is 40. The maximum execution
 time is 30 seconds per test.
The maximum number of points for the second day is 100.
　
The Test Data Used for Judging IOI'94
N.B.The following test data were not available during the competition. They 
were used to judge the programs of the competitors after the competition.
The provided test output must be interpreted carefully, because the output i
s not always uniquely determined by the input. In Problem 2 of Day 1 (The Ca
stle), the third item of the output may be presented in different ways. Each
 test output file for this problem contains the first two items and a list o
f all possible presentations of the third item (the competitor's program nee
ds to produce only one of these). In Problem 3 of Day 1 (The Primes) and all
 the problems of Day 2, the order in which items, except the first item in P
roblem 3 of Day 3 (The Circle), are presented is free. The test output files
 contain the relevant items in one order only; all permutations, however, ar
e correct too.
　
Day 1
Problem 1: The Triangle (per test: 5 points and 30 seconds)
Input / Output (6 rows; maximum route sum = 469)
Input / Output (10 rows; maximum route sum = 727)
Input / Output (15 rows; maximum route sum = 976)
Input / Output (30 rows; maximum route sum = 2135)
Input / Output (60 rows; maximum route sum = 4466)
Input / Output (100 rows; maximum route sum = 7178)
　
Problem 2: The Castle (per test: 6 points and 30 seconds)
Input / Output (4 x 5 castle; has 7 rooms, largest is 6 modules)
Input / Output (5 x 10 castle; has 2 rooms, largest is 44 modules)
Input / Output (10 x 10 castle; has 9 rooms, largest is 36 modules)
Input / Output (14 x 15 castle; has 27 rooms, largest is 55 modules)
Input / Output (50 x 50 castle; has 306 rooms, largest is 905 modules)
　
Problem 3: The Primes (per test: 10 points and 90 seconds)
Input / Output (11, 5; has 1 solution)
Input / Output (37, 9; has 3 solutions)
Input / Output (35, 5; has 1 solution)
Input / Output (13, 4; has 1 solution)
　
Day 2
Problem 1: The Clocks (per test: 6 points and 30 seconds)
Input / Output (3 moves)
Input / Output (10 moves)
Input / Output (19 moves)
Input / Output (24 moves)
Input / Output (27 moves)
　
Problem 2: The Buses (per test: 5 points and 30 seconds)
Input / Output (12 arrival times; 3 bus routes)
Input / Output (44 arrival times; 4 bus routes)
Input / Output (43 arrival times; 5 bus routes)
Input / Output (31 arrival times; 7 bus routes)
Input / Output (40 arrival times; 11 bus routes)
Input / Output (70 arrival times; 17 bus routes)
　
Problem 3: The Circle (per test: 5 points and 30 seconds)
Input / Output (3, 1, 1; maximum is 7 with 2 solutions)
Input / Output (4, 2, 2; maximum is 13 with 2 solutions)
Input / Output (5, 3, 1; maximum is 22 with 2 solutions)
Input / Output (4, 16, 1; maximum is 23 with 6 solutions)
Input / Output (5, 16, 12; maximum is 20 with 24 solutions)
Input / Output (6, 1, 1; maximum is 31 with 10 solutions)
Input / Output (6, 2, 2; maximum is 29 with 2 solutions)
Input / Output (6, 4, 4; maximum is 31 with 6 solutions)
　
Documented Solutions for IOI'94
Below are the documented solutions for the problem set of IOI'94, as provide
d by Tom Verhoeff.
　
Day 1
Solution for Problem 1: The Triangle
Solution for Problem 2: The Castle
Solution for Problem 3: The Primes
　
Day 2
Solution for Problem 1: The Clocks
Solution for Problem 2: The Buses
Solution for Problem 3: The Circle

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

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