|
Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 131072/131072/131072/131072 Кб.
Макс и кубик Рубика $$$2×2×2$$$ ограничение по времени на тест 2 секундыограничение по памяти на тест 64 мегабайтаввод стандартный вводвывод стандартный выводНедавно Максу подарили хитрую головоломку — кубик Рубика $$$2 \times 2 \times 2$$$. Это устройство представляет собой куб $$$2 \times 2 \times 2$$$ с $$$24$$$-мя видимыми цветными квадратами. Грани большого куба способны вращаться вокруг трёх внутренних осей куба. Каждая из шести граней состоит из четырёх квадратов и окрашена в один из шести цветов: белый, оранжевый, жёлтый, красный, синий и зелёный. Вращая грани куба, можно переупорядочивать цветные квадраты множеством различных способов. Задача состоит в том, чтобы путём вращения граней получить такой порядок, что все квадраты на одной грани будут иметь одинаковый цвет. Макс сразу же бросился изучать схемы сборки кубика. Для удобства он нарисовал его развёртку и пронумеровал квадраты от $$$1$$$ до $$$24$$$, как представлено на рисунке $$$1$$$. Также он обозначил грани буквами F (фронтальная), U (верхняя), D (нижняя), L (левая), R (правая), B (задняя), как представлено на рисунке $$$2$$$. С учётом этих обозначений он стал записывать вращения граней куба двумя символами $$$SC$$$, где $$$S$$$ — одна из букв, обозначающих грань, а $$$C$$$ — число от $$$1$$$ до $$$3$$$, обозначающее количество поворотов грани по часовой стрелке. Например $$$L2$$$ будет означать поворот левой грани $$$2$$$ раза по часовой стрелке. Направление по часовой стрелке для каждой из граней представлено на рисунке $$$3$$$.
Изучая различные схемы сборки, Макс наткнулся на такие понятия, как алгоритм Бога и число Бога. Он узнал, что алгоритмом Бога называют любой алгоритм, собирающий головоломку за оптимальное число ходов. А число Бога — это наибольшее количество ходов в алгоритме Бога из всех возможных начальных состояний кубика. Он узнал, что для кубика Рубика $$$2 \times 2 \times 2$$$ это число равно $$$11$$$, с учётом, что одним ходом считается поворот одной грани $$$1$$$, $$$2$$$ или $$$3$$$ раза по часовой стрелке. Макс сразу же захотел составить такой алгоритм, но так как он не Бог, он попросил вас помочь ему. Ваша задача по исходной конфигурации кубика Рубика вывести любую кратчайшую последовательность ходов, приводящую кубик в собранное состояние. Входные данные Ввод содержит $$$24$$$ числа $$$C_i (1 \le C_i \le 6)$$$, которые обозначают цвет $$$i$$$-го квадрата в исходной конфигурации кубика Рубика. Цвета нумеруются следующим образом:
Гарантируется, что состояние корректное и было получено путем вращений граней кубика из собранного состояния. При этом в собранном состоянии относительное расположение цветов граней совпадает с расположением цветов на рисунках $$$1$$$ и $$$2$$$, но куб может быть повернут, и фронтальной грани не обязательно соответствует белый цвет. Выходные данные В первой строке выведите целое число $$$M$$$ — количество ходов. Во второй строке выведите $$$M$$$ строк вида $$$SC$$$, где $$$S$$$ — одна из букв {F, U, D, L, R, B}, а $$$C$$$ — число от $$$1$$$ до $$$3$$$, обозначающих вращения граней кубика. Если решений несколько, выведите любое. Примеры Входные данные 6 6 6 6 3 3 4 4 5 5 5 5 2 2 1 1 2 2 3 3 4 4 1 1 Выходные данные 1 U1 Входные данные 5 5 5 5 3 3 3 3 6 6 6 6 1 1 1 1 4 4 4 4 2 2 2 2 Выходные данные 0 Входные данные 6 4 1 1 4 5 3 3 5 5 2 3 1 4 2 1 3 6 6 2 2 5 4 6 Выходные данные 6 U2 L3 F1 U1 L1 U3 Для отправки решений необходимо выполнить вход. |