Ханойские башни
Каждый программист знает головоломку "Ханойские башни". Вкратце напомним ее условие.
Имеется 3 стержня: A, B, C. Изначально n дисков разного диаметра расположено на стержне A: наименьший диск расположен сверху, и далее вниз по увеличению диаметра. Второй и третий стержни пустые.
Необходимо перенести все диски со стержня A на стержень B, используя стержень C как дополнительный.
За один шаг разрешается снять один верхний диск и положить его либо на пустой стержень, либо на стержень, верхний диск которого имеет больший диаметр.
Почти все книги по программированию содержат рекурсивное решение задачи. Например, ниже приведено решение на языке Паскаль.
Procedure Hanoi (A, B, C: integer; N:integer);
Begin
If N>0 then
Begin
Hanoi (A, C, B, N-1);
Writeln('Disk ', N, ' from ', A, ' to ', B);
Hanoi (C, B, A, N-1)
End
End;
Известно, что приведенное выше решение требует выполнения (2^n–1) шагов. С учетом начального расположения, имеется всего 2^n комбинаций расположения n дисков на трех стержнях. Некоторые комбинации никогда не встречаются во время выполнения алгоритма. Например, комбинация "CAB" никогда не встретится в игре с n = 3 (наименьший диск расположен на стержне C, средний на стержне A, а наибольший на B).
Напишите программу, которая установит, встретится ли в игре заданная комбинация.
Входные данные
Первая строка содержит количество дисков n (1 ≤ n ≤ 250). Вторая строка содержит n заглавных букв ("A", "B" или "C") – расположение n дисков на стержнях. Первая (самая левая) буква задает позицию (имя стержня) наименьшего диска, вторая буква – позицию второго наименьшего и так далее…
Выходные данные
Вывести "YES" или "NO" в зависимости от того, достижима ли в игре заданная комбинация.