Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
864. Головоломка
Генерация всех подмножеств, сочетаний, перестановокПоиск в ширину (BFS)
Предрасчеты, кэширование вычислений
Олимпиадные задачи на русском языке
| 20/04/2008 | Региональная олимпиада Информатика-2008 (D) |
| 08/07/2020 | Летние сборы - 5 (E) |
Ограничения: время – 6s/12s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Головоломка состоит из 10 деталей, обозначенных числами от 1 до 10. Начальное состояние головоломки показано на рис. 1.
Рис. 1. Начальное состояние
Можно поворачивать левую часть головоломки из 7 деталей (1, 2, 4, 5, 6, 8, 9) на 60 градусов по или против часовой стрелки, либо таким же образом правую часть (2, 3, 5, 6, 7, 9, 10). Например, после поворота левой части против часовой стрелки из начального состояния получается состояние, показанное на рис. 2.
Рис.2. После поворота левой части головоломки
Напишите программу, которая определяет с помощью какой минимальной последовательности ходов можно получить из начального состояния некоторое заданное.
Ввод содержит 3 строки, содержащих перестановку целых чисел от 1 до 10 – требуемое состояние головоломки.
Вывод содержит в первой строке одно целое минимальное число ходов. Во второй строке указывается последовательность ходов. Ход "L+" означает поворот левой части по часовой стрелке, "L-" – поворот левой части против часовой стрелки, "R+" – поворот правой части по часовой стрелке, "R-" – поворот правой части против часовой стрелки. Если существует несколько минимальных последовательностей, можно вывести любую из них.
Пример ввода
2 5 6 1 8 9 3 4 10 7
Пример вывода
2 L- R+
