ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2029. Ханойские башни наносят ответный удар

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Известная задача о Ханойских башнях была придумана французским математиком Эдуардом Люка во второй половине XIX века. Она звучит так:
Есть три стержня, обозначенных буквами A, B, C, и n дисков размеров от 1 до n (все целые и различные). Изначально все диски нанизаны на стержень A, причём чем больше размер диска, тем он ниже. Можно снимать верхний диск с любого стержня и перекладывать его на другой стержень, но всегда должно выполняться следующее условие: для любых двух дисков на одном стержне выше тот, который меньше по размеру. Нужно переместить все диски на стержень B за наименьшее число ходов, причём в процессе можно использовать вспомогательный стержень C.
Состояние стержней в любой момент времени можно описывать строчкой из n букв A, B, C: на позиции номер i стоит буква, обозначающая стержень, на который в данный момент нанизан диск размера i. Например, начальное состояние задаётся строчкой из всех букв А, а конечное — строчкой из всех букв В. Верно и обратное: любая такая строчка задаёт ровно одно корректное состояние стержней, т.к. порядок дисков на стержне однозначно определяется их размером.
Представьте, что вам нужно перейти из начального состояния, в котором все диски нанизаны на стержень A, в некоторое заданное состояние. За какое минимальное количество ходов это можно сделать?

Исходные данные

В первой строке дано целое число n (1 ≤ n ≤ 50).
Во второй строке даны n заглавных латинских букв A, B, C, описывающих конечное состояние.

Результат

Если не существует способа получить из начального состояния конечное, выведите «-1» (без кавычек). Иначе выведите единственное число — минимальное количество ходов. Гарантируется, что если ответ существует, то он не превышает 1018.

Примеры

исходные данныерезультат
1
A
0
4
BBBB
15
7
BCCBABC
95
Автор задачи: Никита Сивухин и Эдуард Люка
Источник задачи: Уральская региональная командная олимпиада по программированию 2014