Кожен програміст знає ломиголовку "Ханойські вежі". Коротко нагадаємл її умову.
Є 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" у залежності від того, чи досяжна у грі задана комбінація.