<ПРЕД Задача:
СЛЕД>
Задачу решили 15 пользователей: WsemirZ, JohnJones_001, zloy_mipt, pmnox, UdH-WiNGeR, regal, defrager, Rizvanov, Dest, EAA2008, fetetriste, ripatti, dan, vi002, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Пятнашки 3D

Time limit = 5 секунд(ы)

Задача состоит в сборке "пятнашек" на трехмерном поле размера 3х3х3: дан куб размером 3х3х3, состоящий из 26 маленьких пронумерованных кубиков и одного кубика-пустышки с номером 'нуль'.

По правилам можно менять местами пустышку и любой из кубиков, который имеет общую грань с пустышкой. Цель — получить исходную позицию из заданной позиции.

В кубе есть три слоя в которых позиции элементов нумеруются следующим образом:

верхний		средний		нижний
слой 0:		слой 1:		слой 2:

0 1 2 9 10 11 18 19 20 3 4 5 12 13 14 21 22 23 6 7 8 15 16 17 24 25 26

Таким образом, в исходной позиции 0 может меняться местами с 1, 3 и 9.

Входные данные представляются строкой в 27 элементов:

Исходной позиции сответствует описание:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Ход отображается как последовательность 2х строк: до хода и после хода. Соответственно, 2 хода — последовательность 3х строк, и так далее.

Вход Строчка входа содержит 27 чисел от нуля до 26 влючительно.

Выход. Последовательность строчек, состоящих из чисел от 0 до 26, первая из которых — заданная, а последняя — исходная позиция.

Эта последовательность строк должна отражать последовательность ходов для получения заданной исходной позиции.

Число ходов не обязательно должно быть минимальным, но должно быть меньше 500.

Если сборка невозможна, на выходе должно быть слово "IMPOSSIBLE" без кавычек.

Вход#1
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Выход#1
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Вход#2
 0  2  1  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Выход#2
IMPOSSIBLE

Вход#3
 3  1  2  0  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Выход#3
 3  1  2  0  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Вход#4
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14  0 25 17 18 19 20 21 22 23 15 24 26

Выход#4
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14  0 25 17 18 19 20 21 22 23 15 24 26  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23  0 24 26  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23 24  0 26  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23 24 26  0  
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15 25 17 18 19 20 21 22 23 24  0 26 
 3  1  2  4 13  5  6  7  8  9 10 11 12 16 14 15  0 17 18 19 20 21 22 23 24 25 26 
 3  1  2  4 13  5  6  7  8  9 10 11 12  0 14 15 16 17 18 19 20 21 22 23 24 25 26 
 3  1  2  4  0  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  
 3  1  2  0  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26



Автор:
Поволоцкий Владимир
23 мая 2008

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 34.200.222.93