Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1890. Folding Snake Cube
Рекурсивный переборОлимпиадные задачи на английском языке
| 06/12/2012 | Занятие 13 (Задачи NEERC 2012) (F) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Snake Cube is a puzzle that consists of 27 wooden cubelets that are connected by an elastic band running
through them. The band starts in the center of the first cubelet, exits through the center of one of its
faces that is adjacent to the face of the second cubelet. Then the band enters through the center of
the adjacent face into the second cubelet, exits the second cubelet through the center of some other
face, enters the third cubelet and so on until the last cubelet where the band ends. This configuration
allows adjacent cubelets to freely turn around the center of their shared faces. Moreover, the elasticity
of the band allows to stretch it during intermediate steps and to fold the puzzle in a ways that would be
otherwise impossible with rigid connections between cubelets. The task is to fold it into a `3\ times\ 3\ times\ 3` cube
Cubelets in the Snake Cube puzzle are typically colored into two alternating colors. For the purpose of
this problem all cubelets are marked by alternating uppercase and lowercase letters. The first cubelet is
marked by 'A', the second one by 'a', the third one by 'B', the fourth one by 'b', and so on. The last
27th cubelet is marked by 'N'. The order of marking follows the path of the band through the cubelets.
Initially the puzzle is laid out on a flat surface and its layout is given the input file. Your task is to find
a way to fold it into a `3\ times\ 3\ times\ 3` cube and describe the resulting layout in the output file.
Input
The input file consists of 15 lines with 15 characters on each line that represent flat layout of the puzzle.
Dot characters ('.') represent empty space. Uppercase letters from 'A' to 'N' and lowercase letters from
'a' to 'm' represent marked cubelets with the band running through AaBb…N as explained in the problem
statement.
The input file represents a valid layout. In a valid layout:
- each marked cubelet appears exactly once;
- cubelets that are adjacent in the order that elastic band runs through them are also adjacent in the layout;
- a face that the band exists a cubelet from is adjacent to the face of the next cubelet that the band enters into.
The puzzle given in the input file is solvable and can be folded into a `3\ times\ 3\ times\ 3` cube.
Output
Write to the output file 3 lines with 11 characters on each line (3 groups of 3 characters separated by
single spaces) that represent the puzzle in the input file folded into a `3\ times\ 3\ times\ 3` cube. The output file
corresponds to 3 consecutive `3\ times\ 3` slices of the resulting layout.
The output file layout has to be valid in the same sense as in the input file.
Sample Input
............... ............... ......Ff....... .....EeG....... .....d.gHh..... ...CcD...Ii.... ...b......J.... .AaB......jK... ...........k... ..........lL... ........NmM....
Sample Output
AhI jJi DdE aHl KkL cFe BgM bGm CfN
Sample input and output correspond to the layouts that are shown on the pictures in the problem
statement.
Source: ACM ICPC NEERC, 2012
