Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2293. Пасьянс
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 02/10/2016 | Личное первенство по спортивному программированию (D) |
| 04/09/2025 | Входной контроль ЧОМЛИ 2025 (проводит sartasova) (C) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Чтобы успокоиться после сеанса психотерапии, мистер Маки раскладывает пасьянс.
Для его любимого пасьянса используется `N` карт, пронумерованных от 1 до `N`. Сначала карты раскладываются в `N`
стопок по одной карте. Новые стопки в процессе игры не появляются, но стопка остается существующей,
даже если в ней не осталось ни одной карты.
Разрешается перемещать верхнюю карту из стопки на соседнюю стопку, только если номер верхней карты в ней больше
или соседняя стопка пуста. Игра заканчивается, когда во всех стопках снова по одной карте, и при этом они образуют
числовой ряд от 1 до `N` слева направо.
Напишите программу, определяющую, сходится ли пасьянс и какое минимальное количество ходов
потребуется для его решения.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 7`). Вторая строка содержит перестановку
чисел от 1 до `N` – начальное расположение карт.
Вывести одно целое число – минимальное количество ходов для решения пасьянса. Если решение пасьянса невозможно, то
вывести сообщение "IMPOSSIBLE".
Пример ввода #1
3 3 2 1
Пример вывода #1
20
Пример ввода #2
2 2 1
Пример вывода #2
IMPOSSIBLE
| Ход | 1 | 2 | 3 |
| - | 3 | 2 | 1 |
| 1 | 3 | 12 | |
| 2 | 13 | 2 | |
| 3 | 13 | 2 | |
| 4 | 3 | 1 | 2 |
| 5 | 3 | 12 | |
| 6 | 3 | 12 | |
| 7 | 13 | 2 | |
| 8 | 1 | 3 | 2 |
| 9 | 1 | 23 | |
| 10 | 123 | ||
| 11 | 23 | 1 | |
| 12 | 2 | 3 | 1 |
| 13 | 2 | 13 | |
| 14 | 12 | 3 | |
| 15 | 12 | 3 | |
| 16 | 2 | 1 | 3 |
| 17 | 2 | 13 | |
| 18 | 2 | 13 | |
| 19 | 12 | 3 | |
| 20 | 1 | 2 | 3 |
