Камінчиковий автомат
Камінчиковий автомат «Мардж-2016» працює на квадратній таблиці, розбитій на комірки, у кожній з яких у довільний момент часу лежить певна (можливо, нульова) кількість камінців. На вхід автомат приймає два натуральних числа A та B у вигляді кількості камінців, розташованих у початковий момент часу в лівій верхній та у правій верхній комірках таблиці відповідно. У решті комірок у початковий момент часу камінців немає. Кожна комірка має прикріплену до неї функцію: ця функція приймає на вхід кількість камінців, розташованих на даний момент у комірці, а повертає кількості камінців, які на наступній ітерації необхідно перекласти з цієї комірки у сусідні з нею верхню, праву, нижню та ліву клітинки таблиці. Таким чином, на кожній ітерації камінчиковий автомат просто перекладає відповідні кількості камінців з усіх комірок у сусідні відповідно до інструкцій, які повернули прикріплені до комірок функції. Усі перекладання здійснюються водночас. Якщо під час чергової ітерації жодна комірка не переклала жодного камінця у жодну сусідню комірку, після цієї ітерації виконання «програми» завершується. На виході автомат повертає два числа: кількість камінців у лівій нижній та правій нижній комірках. Кількості камінців, які на момент завершення програми містили всі інші комірки, можуть бути довільними та ігноруються.
Завдання
Дана задача має 5 підзадач:
У першій підзадачі на виході потрібно отримати (0, A + B), тобто у лівій нижній комірці камінців бути не має, а в правій нижній кількість камінців має дорівнювати сумі чисел на вході. Ця підзадача має вартість 10 балів.
У другій підзадачі на виході потрібно отримати (0, |A – B|), тобто у правій нижній комірці кількість камінців має дорівнювати модулю різниці чисел на вході (а в лівій нижній комірці камінців бути не має). Ця підзадача має вартість 20 балів.
У третій підзадачі на виході необхідно отримати (0, minA, B), де minA, B позначає менше з двох чисел A та B (якщо A = B, то minA, B = A = B). Ця підзадача має вартість 15 балів.
У четвертій підзадачі на виході необхідно отримати (0, maxA, B), де maxA, B позначає більше з двох чисел A та B (якщо A = B, то maxA, 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 зі структурою, описаною в наступному абзаці. Зауважте, що основне тіло програми, яке буде використано для оцінювання вашої функції, відрізнятиметься від наданого вам у automaton_tester.* прикладу. Зокрема, під час перевірки функцію може бути викликано для довільної клітинки таблиці та довільної кількості камінців від 1 до 200.
automaton_tester: вхідні дані
Єдиний рядок містить чотири натуральних числа: відповідно номер підзадачі, розмір таблиці, число A та число B.
automaton_tester: вихідні дані
Перший рядок вихідного файла міститиме пару чисел на виході автомата або словесну діагностику помилки в разі, якщо на якомусь кроці функція порушила технічні вимоги чи обмеження на кількість ітерацій. Якщо технічних порушень не було, наступні рядки міститимуть повний кінцевий стан таблиці.