eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ханойские башни

Ханойские башни

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Головоломка "Ханойские башни" достаточно известная. Имеются 3 пронумерованных колышка: #1, #2 и #3. N дисков разного диаметра находятся на первом колышке в следующем порядке: чем ниже находится диск, тем больший диаметр он имеет. Необходимо перенести все диски на второй колышек, используя колышек #3 как дополнительный. По правилам за один ход можно перенести только один самый верхний диск. При этом запрещается класть диск большего диаметра на диск меньшего диаметра. Распределение дисков по колышкам во время игры будем описывать последовательностью D (элемент #i последовательности равен номеру колышка, на котором находится диск #i). Например, состояние игры после третьего перемещения однозначно определяется последовательностью D = (3, 3, 1) (первый и второй диски находятся на третьем колышке, а третий диск на колышке #1). Пример. Пусть 3 диска расположены на колышке #1. Перемещение дисков отобразим в следующей таблице (диски пронумерованы в порядке возрастания диаметра):

Ваша задача - определить (используя произвольную последовательность D) количество шагов с начала игры, за которое можно получить заданную позицию в случае оптимального выполнения алгоритма. Если это совершить невозможно, то вывести "-1" - случай имеет место, если задана некорректная последовательность (то есть заданная последовательность не может быть получена в результате выполнения оптимального алгоритма).

Справка. Оптимальный алгоритм описывается следующей рекурсивной процедурой.

procedure Hanoi(N:integer; From, To_, Temp : integer);Begin if N>0 then begin Hanoi(N-1, From, Temp, To_); writeln (N, From, To_); Hanoi(N-1, Temp, To_, From) endEnd;

Например, для переноса 5 дисков достаточно вызвать Hanoi(5,1,2,3) Указание. Очевидно, что во время игры расположение дисков на всех колышках (#1, #2, #3) никогда не повторяется, поэтому ответ всегда определен.

Входные данные

Первая строка содержит целое число N (1N31). Следующие N последовательных строк содержат целые числа D_1, D_2, …, D_N.

1D_1, D_2, …, D_N3.

Выходные данные

Вывести либо количество ходов, либо −1.

Пример

Входные данные #1
3
3
3
1
Выходные данные #1
3
Источник NEERC 2000 Central Subregional, Rybinsk State Avia Academy