1811 . Cube Coloring
TopCoder
Description
In a distant galaxy called Xos, there lives a robot named A. C. Magnifizer. Mr. Magnifizer — or
“A. C. M.,” as he prefers to be called — is extremely happy when he is at work coloring beautiful shapes.
Yesterday, an old artist came to Mr. Magnifizer and offered him a job. The artist needs a cube to be
colored, which is a significant part of his next installation. But he has only the vision of what the cube
should look like.
A face vision is what the cube should look like when observing a certain face of it. It consists of the color
of the face which the observer is looking at (the “main” face), followed by the list of colors of the faces
which have common edge with the main face. The order of adjacent faces is not fixed, because the face
vision defines the impression, not the particular details.
The vision of the cube consists of the face visions of all the cube’s faces, again, in no particular order.
Although Mr. Magnifizer is experienced in coloring cubes, as well as other shapes, this problem seems
very difficult to him. Help him! Given the vision of the cube, find a way to color a cube to satisfy it.
Warn: 本題有 specialjudge
Input Format
There are many test cases. They end with EOF.
The single line of the input file contains six words. Each word describes the face vision of a certain face
of the cube. The description consists of five English uppercase letters — the color of the main face (the
first letter) and the colors of its adjacent faces. Equal letters define equal colors and different letters
define different colors.
Output Format
If it is impossible to color the cube because some of the visions contradict each other, output
“Impossible”.
If there is a single way to color the cube (the ways that can be turned one into another by rotating the
cube are considered equal), output the colors of the faces in a single line, from the first face to the sixth
one, as shown on the picture below. Any rotation of the cube is acceptable.
If there are multiple ways to color the cube, output any two of them in the format described above, each
in its own line.
Sample Input 1
ABCDE FGHIJ KLMNO PQRST UVWXY ZABCD OZZZZ ZOZZZ ZZOZZ ZZZOZ ZZZZO ZZZZZ ABCOO BCAOO CABOO OOOAB OOOBC OOOCA
Sample Output 1
Impossible ZOZZZZ ABCOOO ACBOOO
Hints
Problem Source
Migrated from old NTUJ.
ACM ICPC 2011–2012, NEERC, Northern Subregional Contest
Subtasks
| No. | Testdata Range | Score |
|---|