Програміст та шестикутник#4635

Програміст та шестикутник

1 секунда

64 мегабайти

Дуже складна

Метою цієї задачі є розв'язати головоломку з $7$ дерев'яних шестикутників, які слід розмістити на $7$ кілочках, закріплених у дерев'яній основі. Кілочки розміщено, як показано на Рисунку 1, і пронумеровано від $0$ до $6$ для зручності. Шестикутники позначені великими літерами від 'A' до 'G' (див. Рисунок 2). Біля кожної сторони шестикутника зазначено ціле число (від $0$ до $9$ включно).

Коли $7$ шестикутників розміщено на $7$ кілочках, $3$ ребра кожного зовнішнього шестикутника та всі сторони шестикутника на кілочку $0$ є суміжними зі сторонами інших шестикутників. Щоб розв'язати головоломку, потрібно знайти розміщення та орієнтацію для всіх $7$ шестикутників так, щоб числа на кожній парі суміжних сторін збігалися (див. Рисунок 3).

Рисунок 3 — вигляд зверху на розв'язану головоломку

Вашій програмі слід прочитати опис семи шестикутників, знайти розв'язок, використовуючи ці $7$ шестикутників (якщо він існує), і вивести опис розв'язку. Якщо розв'язків декілька, дозволяється вивести будь-який з них. (Після знаходження одного розв'язку його можна перетворити, обертаючи шестикутник на кілочку $0$ і відповідно інші.) Якщо розв'язку не існує, виведіть відповідне повідомлення. Після розв'язання однієї головоломки слід продовжити з наступною.

Вхідні дані

Вхідні дані складаються з декількох тестів — кожен описує набір шестикутників. Кожен з перших $7$ рядків містить по $6$ цифр (без пробілів), які вказують числа на сторонах одного шестикутника. Перший рядок — шестикутник 'A', другий — 'B' і так до сьомого, який відповідає 'G'. Перша цифра — це число на стороні в позиції " $12$ Годин" або "ВЕРХ". Далі йде $5$ цифр за годинниковою стрілкою від "ВЕРХа". Наприклад, шестикутник з рисунка $2$ може бути заданий як $123456$ . Числа на сторонах одного шестикутника не обов'язково різні.

Після семи рядків іде рядок із символом зірочки (*), який слугує роздільником між тестами. Після виведення відповіді на поточний набір треба перейти до наступного, і так далі до кінця файлу. Розділювач присутній після кожного набору, включаючи останній.

Вихідні дані

Для кожного набору шестикутників виведіть розв'язок.

Розв'язок — це таблиця з $3$ стовпців:

Перший стовпець — кілочки від $0$ до $6$ .
Другий — букви шестикутників, які розміщено на кілочках від $0$ до $6$ .
Третій — числа на сторонах відповідного шестикутника, починаючи зі сторони у "ВЕРХ" і далі за годинниковою стрілкою.

Кожен стовпець має бути підписаний: "PEG", "HEX" і "POSITION".

Якщо розв'язку немає, виведіть: "No solutions possible".

Після кожної відповіді (чи повідомлення про відсутність розв'язку) виведіть $36$ зірочок (*), щоб візуально відокремити результати різних головоломок.

Приклади

Приклад 1