501. Octahedron And Dominoes

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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 ≤ 4). 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 4 triangles. 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.
sample input
sample output

sample input
sample output

Online Contester Team © 2002 - 2010. All rights reserved.