eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Конструювання з блоків

Конструювання з блоків

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Одиничним кубом назвемо куб 1×1×1, вершини якого мають цілочисельні координати x, y, z. Два одиничних куби можуть утворювати новий об'єкт шляхом об'єднання їх по граням. Кубоїдом назвемом непорожнє з'єднання одиничних кубів (див. рисунок 1). Об'єм кубоїда дорівнює кількості одиничних кубів, з яких його складено. Блоком назвемо кубоїд з об'ємом не більше чотирьох. Будемо казати, що два блоки мають одинаковий тип, якщо один з них може бути отриманий з іншого при допомозі обертань та зсувів блоку (відмітимо, що віддзеркалювання робитит заборонено). Усьго існує 12 типів блоків (див. рисунок 2). Кольори об'єктів на рисунку показано лише для ілюстрації структури об'єктів, і вони не несуть ніякого змістовного навантаження.

Набір кубоїдів D назвемо декомпозицією кубоїдаS, якщо об'єднання усіх кубоїдів з D дорівнює S, і ніякий одиничний куб з кубоїда S не належить одночасно двом різним кубоїдам з D.

Напишіть програму, яка за заданим описом типів блоків та кубоїда S визначає найменший по кількоті елементів набір блоків, який є декомпозицією кубоїда S. Вам потрібно вивести лише типи блоків. Кожен тип повинен бути виведений стільки разів, скільки блоків цього типу зустрічається у декомпозиції.

Рисунок 1.

Рисунок 2.

Вхідні дані

Перший рядок містить об'єм V кубоїда (1V50). Наступні V рядків описують положення одиничних кубів, з яких складається кубоїд. Кажен з цих V рядків складається з трьо цілих чисел x, y, z (1x, y, z7).

Вихідні дані

Перший рядок містить одне ціле число M, яке дорівнює кількості блоків у мінімальному наборі, який є декомпозицією заданого кубоїда.

Файл з описом типів блоків наведено нижче.

Приклад

Вхідні дані #1
18
2 1 1
4 1 1
2 3 1
4 3 1
2 1 2
3 1 2
4 1 2
1 2 2
2 2 2
3 2 2
4 2 2
2 3 2
3 3 2
4 3 2
4 2 3
4 2 4
4 2 5
5 2 5
Вихідні дані #1
5