|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||9||5||5||55.556%|
Leonardo invented the original odometer: a cart which could measure distances by dropping pebbles as the cart's wheels turned. Counting the pebbles gave the number of turns of the wheel, which allowed the user to compute the distance travelled by the odometer. As computer scientists, we have added software control to the odometer, extending its functionalities. Your task is to program the odometer under the rules specified below.
The odometer moves on an imaginary square grid of 256 × 256 unit cells. Each cell can contain at most 15 pebbles and is identified by a pair of coordinates (row, column), where each coordinate is in the range 0, …, 255. Given a cell (i, j), the cells adjacent to it are (if they exist) (i - 1, j), (i + 1, j), (i, j - 1) and (i, j + 1). Any cell laying on the first or last row, or on the first or last column, is called a border. The odometer always starts at cell (0, 0) (the north-west corner), facing north.
The odometer can be programmed using the following commands.
left— turn 90 degrees to the left (counter clockwise) and remain in the current cell (e.g. if it was facing south before, then it will face east after the command).
right— turn 90 degrees to the right (clockwise) and remain in the current cell (e.g. if it was facing west before, then it will face north after the command).
move— move one unit forwards (in the direction the odometer is facing) into an adjacent cell. If no such cell exists (i.e. the border in that direction has been already reached) then this command has no effect.
get— remove one pebble from the current cell. If the current cell has no pebbles, then the command has no effect.
put— add one pebble to the current cell. If the current cell already contains 15 pebbles, then the command has no effect. The odometer never runs out of pebbles.
halt— terminate the execution.
The odometer executes the commands in the order they are given in the program. The program must contain at most one command per line. Empty lines are ignored. The symbol
# indicates a comment; any text that follows, up to the end of the line, is ignored. If the odometer reaches the end of the program, execution is terminated.
Consider the following program for the odometer. It takes the odometer to the cell (0, 2), facing east. (Note that the first
move is ignored, because the odometer is on the north-west corner facing north.)
move # no effect right # now the odometer is facing east move move
Labels, borders and pebbles
To alter the flow of the program depending on the current status, you can use labels, which are case-sensitive strings of at most 128 symbols chosen from
9. The new commands concerning labels are listed below. In the descriptions below,
L denotes any valid label.
Lfollowed by a colon ‘
:’) — declares the location within a program of a label
L. All declared labels must be unique. Declaring a label has no effect on the odometer.
jump L— continue the execution by unconditionally jumping to the line with label
border L— continue the execution jumping to the line with label
L, if the odometer is on a border facing the edge of the grid (i.e. a
moveinstruction would have no effect); otherwise, the execution continues normally and this command has no effect.
pebble L— continue the execution jumping to the line with label
L, if the current cell contains at least one pebble; otherwise, the execution continues normally and this command has no effect.
The following program locates the first (westmost) pebble in row 0 and stops there; if there are no pebbles in row 0, it stops on the border at the end of the row. It uses two labels
right leonardo: pebble davinci # pebble found border davinci # end of the row move jump leonardo davinci: halt
The odometer starts by turning to its right. The loop begins with the label declaration
leonardo: and ends with the
jump leonardo command. In the loop, the odometer checks for the presence of a pebble or the border at the end of the row; if not so, the odometer makes a
move from the current cell (0, j) to the adjacent cell (0, j + 1) since the latter exists. (The
halt command is not strictly necessary here as the program terminates anyway.)
You should submit a program in the odometer's own language, as described above, that makes the odometer behave as expected. Each subtask (see below) specifies a behavior the odometer is required to fulfill and the constraints the submitted solution must satisfy. The constraints concern the two following matters.
In Example 1, the program size is 4 and the execution length is 4. In Example 2, the program size is 6 and, when executed on a grid with a single pebble in cell (0, 10), the execution length is 43 steps: right, 10 iterations of the loop, each iteration taking 4 steps (
pebble davinci; border davinci; move; jump leonardo), and finally,
pebble davinci and
There are exactly two pebbles somewhere in row 0: one is in cell (0, x), the other in cell (0, y); x and y are distinct, and x + y is even. Write a program that leaves the odometer in cell (0, (x + y) / 2), i.e., exactly in the midpoint between the two cells containing the pebbles. The final state of the grid is not relevant.
For testing purposes, you are provided with an odometer simulator, which you can feed with your programs and input grids. Odometer programs will be written in the same format used for submission (i.e., the one described above).
Grid descriptions will be given using the following format: each line of the file must contain three numbers, R, C and P, meaning that the cell at row R and column C contains P pebbles. All cells not specified in the grid description are assumed to contain no pebbles. For example, consider the file:
0 10 3 4 5 12
The grid described by this file would contain 15 pebbles: 3 in the cell (0, 10) and 12 in the cell (4, 5).
You can invoke the test simulator by calling the program
simulator.py in your task directory, passing the program file name as argument. The simulator program will accept the following command line options:
-hwill give a brief overview of the available options;
-g GRID_FILEloads the grid description from file
GRID_FILE(default: empty grid);
-s GRID_SIDEsets the size of the grid to
GRID_SIDE(default: 256, as used in the problem specification); usage of smaller grids can be useful for program debugging;
-m STEPSlimits the number of execution steps in the simulation to at most
-centers compilation mode; in compilation mode, the simulator returns exactly the same output, but instead of doing the simulation with Python, it generates and compiles a small C program. This causes a larger overhead when starting, but then gives significantly faster results; you are advised to use it when your program is expected to run for more than about 10 000 000 steps.