Ханойская башня
(Время: 1 сек. Память: 16 Мб Сложность: 54%)
 |
| A | B | C |
Многим известна классическая задача о ханойской башне. Напомним ее условие.
Имеется три стержня: A, B и C. На один из стержней нанизаны N колец, причем кольца пронумерованы от 1 до N сверху вниз и номер каждого кольца соответствует его диаметру. Таким образом, на каждом кольце лежит кольцо меньшего диаметра. Требуется перенести данную пирамиду из N колец с одного стержня на другой с выполнением следующих двух условий:
- за один раз разрешается переносить только одно кольцо;
- нельзя класть большее кольцо на меньшее.
Требуется решить эту задачу, а также аналогичную ей, с выполнением еще одного условия:
- один из стержней должен использоваться при каждом перекладывании кольца (каждый раз мы должны перекладывать кольцо либо с него, либо на него);
Поясним последнее условие. Пусть стержень B должен всегда использоваться. Это означает, что допустимы только следующие перекладывания кольца: с A на B, с C на B, с B на A и с B на C. А перекладывания с A на C и с C на A при этом недопустимы.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество колец (N ≤ 10). Во второй строке через пробел записаны значения S, D и M (M может отсутствовать) – это соответственно исходный стержень, конечный стержень и стержень, который обязательно должен использоваться при каждой операции перекладывания кольца. В том случае, когда M отсутствует, следует решать классическую задачу без третьего условия. Гарантируется, что S≠D и S, D и M – прописные латинские символы (A, B или C – имена стержней).
Выходные данные
В выходной файл OUTPUT.TXT выведите последовательность перемещений, в результате которой все N колец будут перемещены со стержня S на стержень D через стержень M (если указан). Каждую операцию перекладывания кольца необходимо вывести в отдельной строке через пробел: номер кольца, исходный стержень и конечный стержень. При этом алгоритм не обязательно должен быть оптимальным, но нельзя использовать более 100 000 операций.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1
A B | 1 A B |
| 2 | 1
A B C | 1 A C
1 C B |
| 3 | 2
A B | 1 A C
2 A B
1 C B |
| 4 | 2
A B B | 1 A B
1 B C
2 A B
1 C B |
| 5 | 3
A C | 1 A C
2 A B
1 C B
3 A C
1 B A
2 B C
1 A C |
Пояснение
В примере №5 приведена классическая задача для трёх колец, иллюстрация решения которой представлена ниже:
Исходное положение |
1. Операция "1 A C" |
2. Операция "2 A B" |
3. Операция "1 C B" |
4. Операция "3 A C" |
5. Операция "1 B A" |
6. Операция "2 B C" |
7. Операция "1 A C" |
Система оценки
Решения, работающие только для N ≤ K (1 ≤ K ≤ 10), будут оцениваться в 10×K баллов.
Решения, работающие только для классической задачи (в случае отсутствия во входных данных информации о стержне M) будут оцениваться в 60 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
