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

Конструирование из блоков

Конструирование из блоков

\textit{Единичным кубом} назовём куб \textbf{1}×\textbf{1×1}, вершины которого имеют целочисленные координаты \textbf{x}, \textbf{y}, \textbf{z}. Два единичных куба могут образовывать новый объект путём соединения их по граням. \textit{Кубоидом} назовём непустое соединение единичных кубов (см. рисунок 1). Объём кубоида равен количеству единичных кубов, из которых он составлен. \textit{Блоком} назовём кубоид с объёмом не больше четырёх. Скажем, что два блока имеют одинаковый тип, если один из них может быть получен из другого с помощью вращений и сдвигов блока (заметьте, что отражение делать запрещено). Всrего существует \textbf{12} типов блоков (см. рисунок 2). Цвета объектов на рисунке изображены лишь для иллюстрации структуры объектов, и они не несут никакой смысловой нагрузки. Набор кубоидов \textbf{D} назовём \textit{декомпозицией кубоида} \textbf{S}, если объединение всех кубоидов из \textbf{D} равно \textbf{S}, и никакой единичный куб из кубоида \textbf{S} не принадлежит одновременно двум разным кубоидам из \textbf{D}. Напишите программу, которая по заданному описанию типов блоков и кубоида \textbf{S} определяет наименьший по количеству элементов набор блоков, являющийся декомпозиций кубоида \textbf{S}. Вам нужно выдать только типы блоков. Каждый тип должен быть выведен столько раз, сколько блоков этого типа встречается в декомпозиции. \includegraphics{https://static.e-olymp.com/content/19/190ad3b0c6c23e5e0cc73b4350e58d3516409e06.jpg} Рисунок 1. \includegraphics{https://static.e-olymp.com/content/b3/b3f8080839438318310695ea004a6d56f1e421fd.jpg} Рисунок 2. \InputFile Первая строка содержит объём \textbf{V} кубоида (\textbf{1} ≤ \textbf{V} ≤ \textbf{50}). Следующие \textbf{V} строк описывают положение единичных кубов, из которых состоит кубоид. Каждая из этих \textbf{V} строк состоит из трёх целых чисел \textbf{x}, \textbf{y}, \textbf{z} (\textbf{1} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{7}). \OutputFile Первая строка содержит одно целое число \textbf{M}, которое равно количеству блоков в минимальном наборе, являющееся декомпозицией заданного кубоида. Файл с описанием типов блоков приведено ниже.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #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