Problems
Building with Blocks
Building with Blocks
\textit{A unit cube} is a \textbf{1}×\textbf{1×1} cube, whose corners have integer \textbf{x}, \textbf{y}, and \textbf{z} coordinates. Two unit cubes are connected when they share a face. A \textbf{3}-dimensional solid object (solid, for short) is a non-empty connected set of unit cubes (see Figure 1). The volume of a solid is the number of unit cubes it contains. A \textit{block} is a solid with volume at most \textbf{4}. Two blocks have the same type when one can be obtained from the other by translations and rotations (not reflections). There are exactly \textbf{12} block types (see Figure 2). The colors in the figures only help to clarify the structure of the solids; they have no other meaning.
A set \textbf{D} of blocks is a \textit{decomposition} of a solid \textbf{S} when the union of all blocks in \textbf{D} equals \textbf{S}, and no two distinct blocks in \textbf{D} have a unit cube in common.
Your task is to write a program that, given a description of a solid \textbf{S}, determines a smallest set of blocks into which \textbf{S} can be decomposed. It only needs to report the types of these blocks as often as they occur in the decomposition.
\includegraphics{https://static.e-olymp.com/content/19/190ad3b0c6c23e5e0cc73b4350e58d3516409e06.jpg}
Figure 1.
\includegraphics{https://static.e-olymp.com/content/b3/b3f8080839438318310695ea004a6d56f1e421fd.jpg}
Figure 2.
\InputFile
Your program is to read from standard input. The first line contains the volume \textbf{V} of the solid (\textbf{1} ≤ \textbf{V} ≤ \textbf{50}). The remaining \textbf{V} lines contain three integers \textbf{x}, \textbf{y}, \textbf{z}, being the coordinate triple of its corner that minimizes \textbf{x + y + z}, each identifying one unit cube of the solid (\textbf{1} ≤ \textbf{x}, \textbf{y}, \textbf{z} ≤ \textbf{7}).
\OutputFile
Your program is to write to standard output. The first line must contain one integer \textbf{M}, being the smallest number of blocks into which the input solid can be decomposed.
The file describing the types of units listed below.
Input example #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
Output example #1
5