501. Octahedron And Dominoes
Time limit per test: 0.25
Memory limit: 262144
Andrew has just made a breakthrough in puzzle making: he's invented
a new puzzle that is both simple to understand and unlike everything
that has been invented before.
His new puzzle looks like an octahedron with each of its (triangular) faces
split into n2
smaller triangles by 3(n
-1) lines, n
-1 parallel to each
side of the face.
Some of smaller triangles are black and some are white. The objective is to
cover all white triangles with triangular dominoes without overlapping, leaving all black triangles uncovered.
A triangular domino is two
small triangles with one common side. Please note that a domino can cover
one small triangle on a side of the octahedron and another on the adjacent
side of the octahedron (in other words, you can bend your domino in the
middle). You must place each domino so that it covers exactly two white small
triangles (that means you can't cover some part of a triangle with one domino
and the rest with another domino, for example).
How many solutions does the given puzzle have?
The first line of the input file contains an integer n
(1 ≤ n
The next 2n lines describe which small triangles are black and which are
white. Imagine the octahedron standing on its vertex, with one of its other
vertices pointing on us. Then the small triangles
can be split into horizontal layers. The topmost layer contains 4 triangles,
one per each side that ends in the top vertex. The next layer contains 12
triangles, 3 per each side that ends in the top vertex, and so on. The size
of each layer increases by 8 until it reaches 8n-4 in the middle,
then the next layer is again of 8n-4 small triangles (here we switched from
the top 4 faces to the bottom 4 faces), and then the size of each next
layer is less by 8 until we reach the bottommost layer that has just
The octrahedron is given layer-by-layer, and each layer is started with the leftmost small triangle on the visible part of the octahedron (the four
"front" faces), goes from left to right along the visible part, and then
switches to the invisible part and goes back from right to left. One layer
is highlighted on the picture above.
Each small triangle is specified either by '
', denoting a white
triangle, or by '
', denoting a black triangle.
Output one integer — the number of possible coverings of white triangles
of the given octahedron with triangular dominoes.