Before the Quarterfinal contest, a team of programmers were given several
puzzles from the online shop ru-toys.ru
The most insidious of them was the cube snake: once you take it incautiously,
it unfolds immediately, and to fold it back into a cube you have to waste the precious
contest time. That is why the programmers decided to quickly write a program
that would solve the problem in the general form. The program would determine
if it were possible to fold a snake of an arbitrary configuration into a cube. If
yes, it would find how to do it.
A snake consists of 27 small cubes that are strung, as beads,
onto a strong thread. The thread is fixed inside the end cubes and goes through
each of the remaining cubes from the center of one face to the center of another face.
Though some of the cubes the thread goes straight, connecting opposite faces,
and inside other cubes it turns, going through the centers of adjacent faces.
The thread doesn't allow the cubes to move apart, but makes it possible to rotate
a part of the cubes with respect to the other part. It is required to fold the
snake into a 3 × 3 × 3 cube.
The only input line contains 27 letters describing the snake as a sequence of
“straight” (denoted by the letter “F”) and
“turning” (denoted by the letter “T”) small cubes.
The end cubes are considered as straight.
If you can make a cube from the given snake, output
26 letters describing the sequence of folding. Each letter shows the
position of a small cube (starting from the second one) with respect to the
preceding small cube. This position can be at the front (“F”),
behind (“B”), on the right (“R”), on the left
(“L”), on top (“U”), or below (“D”).
If it is impossible to make a cube from the given snake, output
Problem Author: Stanislav Vasilyev (prepared by Sergey Pupyrev)
Problem Source: NEERC 2008, Eastern subregion quarterfinals