The file FONT.DAT contains representations of 27 ideal character images in this order:
abcdefghijklmnopqrstuvwxyz
where represents the space character.
The file IMAGE.DAT contains one or more potentially corrupted character images. A character image might be corrupted in these ways:
In the case of a duplicated line, one or both of the resulting lines may have corruptions, and the corruptions may be different.
Recognise a character image by choosing the font character images that require the smallest number of overall changed '1's and '0's to be corrupted to the given font image, given the most favourable assumptions about duplicated or omitted lines. Count corruptions in only the least corrupted line in the case of a duplicated line. All characters in the sample and evaluation images used are recognisable one-by-one by a well-written program. There is a unique best solution for each evaluation dataset.
A correct solution will use precisely all of the data supplied in the IMAGE.DAT input file.
Each line of data is 20 digits wide. There are no spaces separating the zeros and ones.
The file FONT.DAT describes the font. FONT.DAT will always contain 541 lines. FONT.DAT may differ for each evaluation dataset.
Caution: the output format specified above overrides the standard output requirements specified in the rules, which require separator spaces in output.
Incomplete sample showing the beginning of FONT.DAT (space and 'a'). | Sample IMAGE.DAT, showing an 'a' corrupted |
FONT.DAT | IMAGE.DAT |
540
00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00000111111011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00000001000001110000 00001111111111110000 00001111111111110000 00001111111111000000 00001000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 |
19
00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00100111011011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00001111011111110000 00001111111111110000 00001111111111000000 00001000010000000000 00000000000000000000 00000000000001000000 00000000000000000000 00000000000000000000 |
Figure 1a | Figure 1b |
IMAGE.OUT | Explanation |
a | Recognised the single character 'a' |
[ Return to top ]
The map is a grid of 1000 x 1000 cells. Each city occupies a single cell on the map. City names are to be placed on the map in rectangular boxes of cells. Such boxes are called labels.
Fig. 1: A city with the four possible positions of its label
The placement of labels must satisfy the following constraints:
|
|
|
|
|
|
|
|||||||||
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|||||||||
|
|
||||||||||||||
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
represents a space
represents the position
of a city
Fig. 2: Section of a map
The leftmost column of the map has horizontal index 0 and the bottom row has vertical index 0. Figure 2 shows the bottom left section of a map for the cities Langa at (0,3), Ceres at (6,1) and Paarl at (7,3). All the labels are validly placed, but this is not the only valid placement.
No city name will be longer than 200 letters.
MAPS.DAT | Explanation |
3 | N=3 |
0 3 1 1 Langa | X=0, Y=3, W=1, H=1 |
6 1 1 1 Ceres | |
7 3 1 2 Paarl |
MAPS.OUT | Explanation: |
1 4 | Langa's label is at (1,4) |
0 0 | Ceres's label is at (0, 0) |
8 2 | Paarl's label is at (8, 2) |
Containers arrive at the depot for storage every hour on the hour. They stay at the depot for a positive integer number of hours. When a container arrives, its documentation contains the expected time when it will be removed. The first container arrives at time 1. The actual time a container is requested to be removed may ultimately be before or after the expected time by no more than 5 hours.
In this problem, the time in hours is expressed as an increasing positive integer which will not exceed 150.
A crane (lifting and moving apparatus) operates above the storage space, moves containers in and out of the storage space, and sometimes rearranges them inside the storage space. The crane may operate in space above the defined storage space.
The depot is a rectangular space. The length (X), width (Y) and height (Z) of the space are made available to the program.
Each container is a 1 x 1 x 1 cube. Containers are stacked on top of other containers or the floor. The crane can only move the top container of a stack.
Moving a container from one location to any other location is always
one crane move. All crane moves take place between container arrivals and
removals. Crane moves are instantaneous.
When the depot becomes full, your program must refuse to accept any more containers. Your program may become less efficient or unable to continue when the depot is nearly full. Your program may refuse to accept new containers at any time.
During your program testing, the library will return meaningful values for a small fixed set of test data.
Each container is identified by a unique positive integer.
Your program may call the following functions at any time:
int GetX();
function GetX: integer;
DECLARE FUNCTION GetX CDECL ()
Returns length of storage space (integer).
int GetY();
function GetY: integer;
DECLARE FUNCTION GetY CDECL ()
Returns width of storage space (integer).
int GetZ();
function GetZ: integer;
DECLARE FUNCTION GetZ CDECL ()
Returns height of storage space (integer).
X,Y,Z will not exceed 32.
The following functions provide information on the action sequence (container arrivals and removals). The arrivals take place on the hour, and removal requests are received between hours. Thus, for time-keeping purposes, each arrival marks the passing of one hour.
int GetNextContainer();
function GetNextContainer: integer;
DECLARE FUNCTION GetNextContainer CDECL ()
Returns a positive integer container number of the next container to be stored or retrieved. If there are no more containers to be stored or retrieved, returns 0, indicating your program should terminate, even if containers are still in the warehouse.
int GetNextAction();
function GetNextAction: integer;
DECLARE FUNCTION GetNextAction CDECL ()
Returns an integer representing the action to take: 1 to store a new container, 2 to remove a container.
int GetNextStorageTime();
function GetNextStorageTime: integer;
DECLARE FUNCTION GetNextStorageTime CDECL ()
Returns time in hours (since the start) when the container is expected to be removed. This value is for planning purposes for your program; the actual removal request might come at a slightly different time, which will differ by not more than 5 hours. This function only returns a meaningful value when GetNextAction returns 1.
The order in which the above three functions is called does not matter.
Consecutive calls to GetNextContainer, GetNextAction and GetNextStorageTime will always return information about the same container until the container is refused, stored or removed, at which point the above functions will return information about the next container.
int MoveContainer(int x1, int y1, int x2, int y2);
function MoveContainer(x1, y1, x2, y2: integer): integer;
DECLARE FUNCTION MoveContainer CDECL (BYVAL x1 AS INTEGER, BYVAL
y1 AS INTEGER, BYVAL x2 AS INTEGER, BYVAL y2 AS INTEGER)
Move the container on the top of the stack at x1, y1 to the top of the
stack at x2, y2.
Returns 1 if the action is valid, 0 if the action is illegal (i.e.
impossible).
void RefuseContainer();
procedure RefuseContainer;
DECLARE SUB RefuseContainer CDECL ()
Refuse to accept the incoming container.
void StoreArrivingContainer(int x, int y);
procedure StoreArrivingContainer(x, y: integer);
DECLARE SUB StoreArrivingContainer CDECL (BYVAL x AS INTEGER,
BYVAL y AS INTEGER)
Store the incoming container at the top of the stack at position x, y.
void RemoveContainer(int x, int y);
procedure RemoveContainer(x, y: integer);
DECLARE SUB RemoveContainer CDECL (BYVAL x AS INTEGER, BYVAL
y AS INTEGER)
Remove the container on the top of the stack at x, y from the depot.
If your program cannot carry out the required action, it should terminate.
Illegal moves are ignored by the library, and have no effect on the simulation state or scoring.
Your program is NOT required to write any output to a file. The library with which your program interacts will write a log file of actions. This file is used for evaluation.
The standard C and C++ libraries contain this library and will automatically be linked to your program when you include the appropriate header file.
If you are using QuickBasic you must include the library by typing
QB /L STACKLIB
Sample source code files are present in the task directory named TESTSTK.BAS, TESTSTK.PAS, TESTSTK.CPP, and TESTSTK.C.
[ Return to top ]