eolymp
bolt
Try our new interface for solving problems
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.
Time limit 1 second
Memory limit 64 MiB
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