Керування ікосаедричним ровером
Після десятиліть безуспішних пошуків, одна з експедиційних команд ІТО (Міжзоряна Туристична Організація) нарешті виявила планету, яка, без сумніву, стане однією з найпривабливіших туристичних атракцій у радіусі десяти світлових років від нашої сонячної системи. Найбільш вражаючою особливістю планети, окрім комфортної гравітації та спокійної погоди, є область під назвою Mare Triangularis. Незважаючи на назву, ця область не вкрита водою, а є великою рівниною. Її унікальність полягає в тому, що вона розділена на рівносторонні трикутні секції однакового розміру, які називаються тригонами. Тригони створюють унікальний вражаючий ландшафт, обов'язковий для відвідування туристами. Не дивно, що рада ІТО вирішила інвестувати значні кошти в цю планету.
Як завжди, Товариство Астрогеології швидко отримало цю інформацію, незважаючи на очікувану секретність персоналу. Вони негайно надіслали листа від президента до Інституту Науки та Освіти Співдружності Галактика, вимагаючи, щоб авторитетні академічні інспекції були завершені до того, як будь-яка комерційна експлуатація може пошкодити природу.
На щастя, астрогеологи не планують проводити всі можливі інспекції на всіх тригонах; їх надто багато. Інспекції плануються лише на деяких характерних тригонах і, для кожного з них, в одному з двадцяти різних наукових аспектів.
Щоб прискорити будівництво цього нового туристичного курорту, команда будівельної техніки ІТО вже успішно впровадила свій новий винахід у практичне використання. Це ровер у формі ікосаедра, правильного багатогранника з двадцятьма гранями у формі рівносторонніх трикутників. Машина налаштована так, що кожна з двадцяти граней точно підходить до кожного з тригонів. Керуючи високотехнологічним гіромотором, встановленим всередині його корпусу, ровер може перекочуватися на один з трьох тригонів, що межують з тим, на якому знаходиться його дно.
Кожна з двадцяти граней має свою функцію. Набір обладнання, встановлений на нижній грані, що торкається землі, може бути застосований до тригона, на якому він знаходиться. Звичайно, ровер був призначений для прискорення будівництва розкішних готелів для прийому багатих міжзоряних мандрівників, але, змінюючи встановлені набори обладнання, його також можна використовувати для прискорення академічних інспекцій.
Ви є водієм цього ровера і повинні перемістити транспортний засіб на тригон, вказаний керівником наукової комісії, з найменшою можливою кількістю кроків. Що ускладнює ваше завдання, так це те, що призначена грань з відповідним набором обладнання повинна бути внизу. Напрямок ровера не має значення.
Тригони Mare Triangularis мають двовимірні координати, як показано на Рисунку 2. Як і карти, що використовуються для Землі, вісь x йде з заходу на схід, а вісь y з півдня на північ. Зверніть увагу, що всі тригони з координатами (x, y) мають сусідні тригони з координатами (x-1), і (x + 1, y). Крім того, коли x+y парне, він має сусіда (x, y + 1), в іншому випадку, тобто, коли x+y непарне, він має сусіда (x, y-1).
Рисунок 3 показує розгортку поверхні ровера. Верхня грань розгортки утворює зовнішню поверхню. Тобто, якщо номери на гранях розгортки були б фактично нанесені на грані ровера, вони повинні були б бути читабельними ззовні. Ці номери використовуються для ідентифікації граней.
Коли ви запускаєте ровер, він знаходиться на тригоні (0, 0) і грань 0 торкається землі. Ровер розміщено так, що перекочування на північ на тригон (0, 1) робить грань з номером 5 внизу.
Як перший крок, ви можете вибрати один з трьох сусідніх тригонів, а саме ті, що мають координати (-1, 0), (1, 0), і (0, 1), для відвідування. Внизу буде грань з номером 4, 1, і 5, відповідно. Якщо ви вирішите піти до (1, 0) на першому кроці перекочування, другий крок може привести ровер до одного з (0, 0), (2, 0), або (1, -1). Внизу буде або 0, 6, або 2, відповідно. Ровер може відвідати будь-який з тригонів двічі або більше, включаючи стартовий і цільовий тригони, коли це доречно.
Теоретичний відділ ІТО показав, що ровер може досягти будь-якого цільового тригона на вказаній нижній грані за кінцеву кількість кроків.
Вхідні дані
Вхід складається з кількох наборів даних. Кількість наборів даних не перевищує 50.
Кожен з наборів даних містить три цілі числа x, y, і n в одному рядку, розділені пробілом. Тут, (x, y) вказує координати тригона, до якого ви повинні перемістити ровер, а n вказує грань, яка повинна бути внизу.
Кінець вводу позначається рядком, що містить три нулі.
Вихідні дані
Вихід для кожного набору даних повинен бути рядком, що містить одне ціле число, яке вказує мінімальну кількість кроків, необхідних для встановлення ровера на вказаний тригон з вказаною гранню, що торкається землі. Жодні інші символи не повинні з'являтися у виході.
Ви можете припустити, що максимальна кількість необхідних кроків не перевищує 100. Mare Triangularis достатньо широка, щоб жоден з її країв не міг бути досягнутий за цю кількість кроків.