Langton's Ant
Мураха Лангтона, названа на честь математика Крістофера Лангтона, є клітинним автоматом з дуже простими правилами, але з цікавою поведінкою, що виникає; ця поведінка є предметом дослідження деяких математиків. Аналогія між мурахами та клітинним автоматом Лангтона полягає в тому, що можна визначити стан автомата як "мураху", а динаміку автомата - як можливість мурахи подорожувати в особливому світі.
Світ мурахи є nn площиною, де квадрати (або клітини) на площині пофарбовані або в синій, або в червоний колір. Число n називається розміром світу. Клітина позначається парою (i, j), (1 ≤ i, j ≤ n). Мураха живе і рухається поодинокими кроками, дотримуючись наведених нижче правил:
якщо вона знаходиться на синій клітині, вона змінює колір клітини, повертає ліворуч і рухається вперед до наступної клітини в напрямку, в якому вона дивиться;
якщо вона знаходиться на червоній клітині, вона змінює колір клітини, повертає праворуч і рухається вперед до наступної клітини в напрямку, в якому вона дивиться;
якщо рух неможливий (оскільки мураха не може вийти за межі світу), то мураха гине.
Наприклад, припустимо, що мураха знаходиться на червоній клітині, дивлячись на схід. Якщо немає клітини безпосередньо на південь від неї, то мураха гине. Навпаки, якщо є клітина безпосередньо на південь від неї, то мураха робить один крок, переміщаючись до цієї клітини, до якої вона прибуває, дивлячись на південь, і колір її вихідної клітини змінюється на синій. Потім мураха намагатиметься зробити ще один крок, і так далі.
Ваше завдання - визначити, чи може мураха дійти до клітини (n, n) світу, враховуючи (i) конфігурацію світу, та (ii) початкову позицію мурахи. Ви повинні припустити, що початковий напрямок мурахи - північ.
Вхідні дані
Конфігурація світу nn може бути закодована як натуральне число в двійковій нотації, використовуючи n^2 бітів. Ми приймаємо наступні умовності: 0 = синій, 1 = червоний, а двійкове представлення конфігурації ідентифікує клітини світу зліва направо і знизу вгору (враховуючи біти від найбільш значущого до найменш значущого). Наприклад, двійкове число 0100 (4 у десятковій нотації) представляє світ 22 з наступною конфігурацією:
Послідовно, двійкове число 011010100 (212 у десятковій нотації) представляє світ 33 з наступною конфігурацією:
Вхідні дані задачі містять кілька тестових випадків. Кожен випадок складається з одного рядка, що містить список з чотирьох натуральних чисел, n, c, x, y, розділених пробілами, які слід інтерпретувати як:
n (1 ≤ n ≤ 16): розмір світу;
c (0 ≤ c < 2^{(n2)}): десяткове представлення n^2-бітного двійкового числа, що описує початкову конфігурацію світу, як пояснено вище;
(x, y): координати початкової позиції мурахи у світі (1 ≤ x, y ≤ n), де позиція (n, n) відповідає найменш значущому біту c.
Кінець введення вказується рядком, де n = c = x = y = 0.
Вихідні дані
Для кожного тестового випадку ваше рішення повинно вивести:
"Так" якщо мураха досягає клітини (n, n) з початкової позиції;
"Капут!" якщо мураха гине, не досягнувши клітини (n, n) з початкової позиції.
Для кожного тестового випадку гарантується, що після скінченної кількості кроків мураха досягає клітини (n, n) або гине, не досягнувши клітини (n, n).