Stone Machine Gun

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

The Pebble Automaton "Marge-2016" operates on a square grid divided into cells, each of which may contain a certain number of pebbles, possibly zero, at any given time. The automaton begins with two natural numbers, A and B, as input, representing the number of pebbles initially placed in the top-left and top-right cells of the grid, respectively. All other cells start with no pebbles. Each cell is associated with a function that determines how many pebbles should be moved to its neighboring cells (top, right, bottom, and left) in the next iteration, based on the current number of pebbles in the cell. During each iteration, pebbles are moved simultaneously according to these functions. The process continues until no pebbles are moved to any neighboring cell, at which point the "program" ends. The automaton outputs two numbers: the number of pebbles in the bottom-left and bottom-right cells.

The number of pebbles in all other cells at the end of the program is irrelevant and can be ignored.

Task

This problem consists of 5 subproblems:

Subproblem 1: The output should be (0, A + B), meaning there should be no pebbles in the bottom-left cell, and the bottom-right cell should contain the sum of the input numbers. This subproblem is worth 10 points.
Subproblem 2: The output should be (0, |A – B|), meaning the bottom-right cell should contain the absolute difference of the input numbers, with no pebbles in the bottom-left cell. This subproblem is worth 20 points.
Subproblem 3: The output should be (0, min{A, B}), where min{A, B} is the smaller of the two numbers A and B (if A = B, then min{A, B} = A = B). This subproblem is worth 15 points.
Subproblem 4: The output should be (0, max{A, B}), where max{A, B} is the larger of the two numbers A and B (if A = B, then max{A, B} = A = B). This subproblem is worth 15 points.
Subproblem 5: The output should be (1, 0) if A > B; (0, 1) if A < B; (0, 0) if A = B. This means a single pebble should be placed in the position corresponding to the larger of the two input numbers. This subproblem is worth 40 points.

Write a function or procedure automaton that determines how many pebbles should be moved to neighboring cells based on the number of pebbles in a cell and its coordinates, according to the subproblem requirements. You need to implement the pebble automaton algorithm for each of the five subproblems. Each subproblem consists of separate test blocks, each worth 5 points and may contain one or more tests. To earn the corresponding 5 points, your algorithm must pass all tests in the block.

Implementation Details

Submit a file containing the implementation of the automaton function/procedure and any additional code necessary for its operation, but do not include the main program body (i.e., the main function in C++ or the begin/end block in Pascal). During testing, your file will be supplemented with a special program body written by the jury, which will call your function and verify the correctness of the algorithm. The function should have the following form (see the electronic version for function signatures for each available programming language):

automaton(subproblem, size, row, column, pebbles, top, right, bottom, left)

Function Parameters

subproblem — the subproblem number (see above). This number remains constant during function calls within the same program.
size — the size of the square grid (number of cells in one horizontal/vertical line). This size remains constant during function calls within the same program.
row — the row in which the cell is located; numbered from 1 to size from top to bottom: 1 is the top row, size is the bottom row.
column — the column in which the cell is located; numbered from 1 to size from left to right: 1 is the left column, size is the right column.
pebbles — the number of pebbles in the cell, a positive integer (if this number is zero, no movements can be made, and the function is not called). You can change this variable within the function, but such changes will not affect the outcome: the number of pebbles after movements will automatically equal the initial number of pebbles minus the number moved to neighboring cells.
top — initially set to 0. If the cell has a neighbor above and pebbles need to be moved there, this value should be updated to reflect the number of pebbles moved.
right — initially set to 0. If the cell has a neighbor to the right and pebbles need to be moved there, this value should be updated to reflect the number of pebbles moved.
bottom — initially set to 0. If the cell has a neighbor below and pebbles need to be moved there, this value should be updated to reflect the number of pebbles moved.
left — initially set to 0. If the cell has a neighbor to the left and pebbles need to be moved there, this value should be updated to reflect the number of pebbles moved.

The final values of top, right, bottom, and left must be non-negative, and their sum must not exceed the value of pebbles.

At each step, the function should determine movements based solely on the data passed to it at that step. The function's result should not be influenced by previous interactions with the program body. Furthermore, the function should be deterministic, meaning it should always return the same values for the same input data.

Constraints

The grid size can range from 5 to 10 inclusive.
Input numbers can range from 1 to 100 inclusive.
The number of iterations after which the automaton stops must not exceed 10,000.

Manual Testing

The electronic version includes an example of the main program body automaton_tester.*, which runs the automaton function on input data specified in a file you create and outputs the final state of the grid (or the state after 10,000 iterations if the automaton has not stopped). To use this program, place it in the same directory as the file automaton.*, which contains your function implementation, and create a file automaton.dat in the same directory with the structure described below. Note that the main program body used for evaluating your function will differ from the example provided in automaton_tester.*. In particular, during testing, the function may be called for any cell in the grid and any number of pebbles from 1 to 200.

automaton_tester: Input Data

A single line contains four natural numbers: the subproblem number, the grid size, number A, and number B.

automaton_tester: Output Data

The first line of the output file will contain the pair of numbers output by the automaton or a verbal error diagnosis if the function violated technical requirements or iteration limits at any step. If there were no technical violations, the following lines will contain the complete final state of the grid.

Examples

Input #1

Answer #1