Каменный автомат
Камешковый автомат «Мардж-2016» работает на квадратной таблице, разделённой на ячейки. В каждой ячейке в любой момент времени может находиться определённое количество камешков, включая ноль. На вход автомат принимает два натуральных числа A и B, которые представляют количество камешков в начальный момент времени в левой верхней и правой верхней ячейках таблицы соответственно. Все остальные ячейки изначально пусты. Каждая ячейка имеет прикреплённую функцию, которая принимает количество камешков в ячейке и возвращает, сколько камешков нужно переместить в соседние ячейки: верхнюю, правую, нижнюю и левую. На каждой итерации автомат перемещает камешки между ячейками в соответствии с этими функциями. Если в ходе итерации ни одна ячейка не переместила камешки в соседние, выполнение программы завершается. На выходе автомат возвращает два числа: количество камешков в левой нижней и правой нижней ячейках.
Количество камешков в остальных ячейках на момент завершения программы может быть любым и не учитывается.
Задача
Задача состоит из 5 подзадач:
В первой подзадаче необходимо получить
(0, A + B)на выходе, то есть в левой нижней ячейке не должно быть камешков, а в правой нижней должно быть сумма входных чисел. Эта подзадача оценивается в 10 баллов.Во второй подзадаче на выходе должно быть
(0, |A – B|), то есть в правой нижней ячейке должно быть модуль разности входных чисел, а в левой нижней ячейке камешков быть не должно. Эта подзадача оценивается в 20 баллов.В третьей подзадаче необходимо получить
(0, min{A, B}), гдеmin{A, B}— меньшее из двух чиселAиB(еслиA = B, тоmin{A, B} = A = B). Эта подзадача оценивается в 15 баллов.В четвёртой подзадаче необходимо получить
(0, max{A, B}), гдеmax{A, B}— большее из двух чиселAиB(еслиA = B, тоmax{A, B} = A = B). Эта подзадача оценивается в 15 баллов.В пятой подзадаче на выходе должно быть
(1, 0)еслиA > B;(0, 1)еслиA < B;(0, 0)еслиA = B. То есть, в ячейке, где на входе было большее число, должен быть один камешек. Эта подзадача оценивается в 40 баллов.
Напишите функцию/процедуру automaton, которая определяет, сколько камешков нужно переместить в соседние ячейки, исходя из количества камешков в текущей ячейке и её координат, в соответствии с требованиями подзадачи. Вам нужно реализовать алгоритм работы камешкового автомата для каждой из пяти подзадач. Все подзадачи состоят из отдельных блоков тестов; каждый блок оценивается в 5 баллов и может содержать один или несколько тестов. Чтобы получить 5 баллов, ваш алгоритм должен пройти все тесты блока.
Детали реализации
Вы должны предоставить файл с реализацией функции/процедуры automaton и, при необходимости, другого кода, необходимого для её работы, но без основного тела программы (например, функции main в C++ или блока begin/end в Pascal). При тестировании ваш файл будет дополнен специальным телом программы, написанным жюри, которое вызовет вашу функцию и проверит корректность её работы. Функция должна иметь следующий вид:
automaton(subproblem, size, row, column, pebbles, top, right, bottom, left)
Параметры функции:
subproblem — номер подзадачи. Он остаётся неизменным в течение всех запусков функции на одной программе.
size — размер квадратной таблицы (количество ячеек в строке/столбце). Он остаётся неизменным в течение всех запусков функции на одной программе.
row — номер строки ячейки; нумерация сверху вниз от 1 до size: 1 — верхняя строка, size — нижняя строка.
column — номер столбца ячейки; нумерация слева направо от 1 до size: 1 — левый столбец, size — правый столбец.
pebbles — количество камешков в ячейке, положительное целое число. Если это количество равно нулю, перекладывание невозможно, и вызова функции не происходит. Вы можете изменить это значение внутри функции, но это не повлияет на количество камешков после перекладывания: оно автоматически станет равным разнице между начальным количеством и количеством переложенных камешков.
top — начальное значение 0. Если у ячейки есть сосед сверху и туда нужно переложить камешки, это значение следует изменить на соответствующее количество.
right — начальное значение 0. Если у ячейки есть сосед справа и туда нужно переложить камешки, это значение следует изменить на соответствующее количество.
bottom — начальное значение 0. Если у ячейки есть сосед снизу и туда нужно переложить камешки, это значение следует изменить на соответствующее количество.
left — начальное значение 0. Если у ячейки есть сосед слева и туда нужно переложить камешки, это значение следует изменить на соответствующее количество.
Конечные значения параметров top, right, bottom, left должны быть неотрицательными и в сумме не превышать pebbles.
На каждом шаге функция должна определять перекладывания, основываясь только на данных, переданных на этом шаге. Результат работы функции не должен зависеть от предыдущих взаимодействий с программой. Функция должна быть детерминированной, то есть для одинаковых входных данных всегда возвращать одинаковые значения.
Ограничения
Размер таблицы может быть от 5 до 10 включительно.
Входные числа могут быть от 1 до 100 включительно.
Количество итераций, после которых автомат должен остановиться, не должно превышать 10 000.
Самостоятельное тестирование
В электронном варианте условий приведён пример основного тела программы automaton_tester.*, который запускает функцию automaton на входных данных из файла и выводит конечное состояние таблицы (или состояние после 10 000 итераций, если автомат не остановился). Чтобы использовать эту программу, разместите её в одном каталоге с файлом automaton.*, содержащим вашу реализацию функции, и создайте файл automaton.dat с описанной структурой. Учтите, что основное тело программы для оценки вашей функции будет отличаться от предоставленного примера. В частности, функция может быть вызвана для произвольной ячейки и произвольного количества камешков от 1 до 200.
automaton_tester: входные данные
Единственная строка содержит четыре натуральных числа: номер подзадачи, размер таблицы, число A и число B.
automaton_tester: выходные данные
Первая строка выходного файла содержит пару чисел на выходе автомата или сообщение об ошибке, если функция нарушила технические требования или ограничения на количество итераций. Если нарушений не было, следующие строки содержат полное конечное состояние таблицы.