21/11/2024 22:00:04

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2293. Пасьянс

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Чтобы успокоиться после сеанса психотерапии, мистер Маки раскладывает пасьянс. Для его любимого пасьянса используется `N` карт, пронумерованных от 1 до `N`. Сначала карты раскладываются в `N` стопок по одной карте. Новые стопки в процессе игры не появляются, но стопка остается существующей, даже если в ней не осталось ни одной карты. Разрешается перемещать верхнюю карту из стопки на соседнюю стопку, только если номер верхней карты в ней больше или соседняя стопка пуста. Игра заканчивается, когда во всех стопках снова по одной карте, и при этом они образуют числовой ряд от 1 до `N` слева направо.

Напишите программу, определяющую, сходится ли пасьянс и какое минимальное количество ходов потребуется для его решения.

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 7`). Вторая строка содержит перестановку чисел от 1 до `N` – начальное расположение карт.

Вывести одно целое число – минимальное количество ходов для решения пасьянса. Если решение пасьянса невозможно, то вывести сообщение "IMPOSSIBLE".

Пример ввода #1

3
3 2 1

Пример вывода #1

Пример ввода #2

2
2 1

Пример вывода #2

IMPOSSIBLE

Пояснение к примеру 1

Ход	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