The IOI'94 Competition
 Return to IOI'94 Competition Home
Competition Rules for IOI'94
Competition days
There are two competition days (Tuesday and Thursday), separated by one day of rest. Each day the competitors have to solve three problems. They have five hours for the task (from 12:00h to 17:00h).
The computer
Each competitor has a personal computer for the entire duration of the competition. The computer is an AST with a 33 MHz Intel 486 processor running MSDOS.
Programming languages
The following four programming languages are available: Turbo C++ 3.0
 Turbo Pascal 7.0
 QuickBasic 4.5
 LCN Logo 3.0
Competitors may not bring any aids of their own, such as program disks, manuals, or books.
Directories
Apart from a directory for each of the four programming languages, there are two directories: IOI_DAY1 and IOI_DAY2. In both these directories are five subdirectories called PROBLEM1, PROBLEM2, PROBLEM3, PROBLEM4 and PROBLEM5.Each programming problem will have its number marked on the paper given to the competitors. It is important that the solutions are put in the correct directory. If the title on the problem paper is "Day 1  Problem 3", the solution has to be put in the directory C:\IOI_DAY1\PROBLEM3.
The solution has to be an EXE file. The solution to the problem "Day 1  Problem 3" has to be called PROBLEM3.EXE.
The problems
The competitors get the three problems for each day in two copies, one written in English and one translated by their team leaders into their native language.
Input data
For all problems input data will come from an ASCII file which will always be called INPUT.TXT. This is the case even if the program will need only a single number. No tests of the input data are necessary. For all INPUT.TXT files one can assume that the input data correspond to the problem statements.Input data will be either integers or strings. Since the file always begins with one or more numbers defining the number of integers or strings that follow, competitors do not have to check for endoffile conditions. Two integers in the input file will be separated by either a single space character or a newline. The number of integers in a line will be clear from the problem statement. A string is always terminated by a newline. Every problem has an example input file which will also be shown on the problem paper.
Do not read anything from the keyboard, not even a keystroke.
Here are examples of how to open an ASCII file and read a value for the integer variable N in the four languages:
 Turbo Pascal

var infile: text; ... Assign(infile, 'INPUT.TXT'); Reset(infile); Read(infile, N);  Turbo C++

#include FILE *infile; ... infile = fopen("INPUT.TXT", "rt"); fscanf(infile, "%d", &N);  QuickBasic

OPEN "INPUT.TXT" FOR INPUT AS #1 INPUT #1, N  Logo

tell disk filepos "INPUT.TXT make N read number
Output data
The results of the program are always to be written to the ASCII file OUTPUT.TXT. The file has to be formatted exactly as stated in the problem. Never add any texts of your own!Do not write anything to the screen. The program has to exit when the output has finished.
Here are examples for the four languages of how to create an ASCII file and write the value of the integer variable N on it:
 Turbo Pascal

var outfile: text; ... Assign(outfile, 'OUTPUT.TXT'); Rewrite(outfile); Write(outfile, N, ' '); ... Close(outfile);  Turbo C++

#include FILE *outfile; ... outfile = fopen("INPUT.TXT", "wt"); fprintf(outfile, "%d", N); ... fclose(outfile);  QuickBasic

OPEN "OUTPUT.TXT" FOR OUTPUT AS #1 PRINT #1, N; ... CLOSE #1  Logo

tell disk newfile "OUTPUT.TXT tell disk filepos "OUTPUT.TXT write N
Printouts
During the competition competitors will be able to get printouts of their programs. If they want a printout they have to copy their file to one of the two diskettes and leave it to an official. See to it that the diskettes only contain files that need to be printed.
Diskettes
When the competition nears the end the competitors have to copy their solutions to both diskettes. Give both diskettes to an official. During testing one of them will be returned to the competitor or their team leader.No extra time will be allowed for copying. It might therefore be good to copy solutions as they are done.
It is the EXE file on the hard disk on the competitor's computer that will be tested. Only in case of hardware error during testing will the copy on the diskette be used.
Grading
Grading is done directly after the end of the competition. The competitors and their team leaders will take part in the grading. There will be lists with the approximate time for their turn to be graded.For each problem there is a set of up to 10 test examples that have been prepared in advance. Each test will be announced with the maximal allowed execution time (in seconds) and the number of points a correct answer will give.
The grading will be done by a program that looks in the various directories for an EXE file with the correct name. It starts the competitor's program, measures the execution time and checks the resulting file OUTPUT.TXT.
Note: All test data will have solutions.
The Problem Set for IOI'94
Here is the problem set for IOI'94. For each problem, the number of tests, the 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. Therefore 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. Therefore 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. Therefore the maximum number of points for this problem is 40. The maximum execution time is 90 seconds per test.
Day 2 (5 hours)
 Problem 1: The Clocks
There are 5 tests. Each successfully completed test gives 6 points. Therefore 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. Therefore 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. Therefore the maximum number of points for this problem is 40. The maximum execution time is 30 seconds per test.
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 is not always uniquely determined by the input. In Problem 2 of Day 1 (The Castle), 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 of all possible presentations of the third item (the competitor's program needs 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 Problem 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, are 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)
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 provided by Tom Verhoeff. A short introduction explains some general features of these solutions.
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
Index
Here is an index for the problem set of IOI'94. Clicking on a problem, brings up a page with pointers to the problem statement, the tests, and the solution.
Day 1
Day 2