ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


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

Задачи раздела

• Умножение матриц
• Умножение матриц
• Уравнение
• Уравнение
• Условия (подсказки к задачам)
• Факторизация
• Ферма
• Функции (подсказки к задачам)
• Ханойские башни
• Хилла
• Хорошая погода
• Цезарь
• Ценителям хорошей музыки
• Цикл
• Циклы (подсказки к задачам)
• Четвертьфинал
• Четвертьфинал

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Ханойские башни
Ханойские башни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Головоломка «Ханойские башни» представляет собой три стержня. На стержень #1 нанизана пирамида из N дисков увеличивающегося диаметра.

Требуется перенести пирамиду со стержня #1 на стержень #3, пользуясь стержнем #2 как вспомогательным. При этом следует придерживаться следующих правил:

  • За один ход разрешается перенести верхний диск с одного стержня на другой;
  • Диск большего диаметра нельзя класть на диск меньшего диаметра.

Выведите инструкцию по решению головоломки за наименьшее число ходов.

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

Ввод содержит целое число N (1 ≤ N ≤ 20) — количество дисков на стержне #1.

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

Выведите одну или более строк вида X Y (1 ≤ X, Y ≤ 3) — «перенести верхний диск со стержня #X на стержень #Y», позволяющих решить головоломку в соответствии с правилами. Количество строк в выводе должно быть минимально возможным.

Примеры

Входные данные
2
Выходные данные
1 2
1 3
2 3
Входные данные
3
Выходные данные
1 3
1 2
3 2
1 3
2 1
2 3
1 3

Для отправки решений необходимо выполнить вход.

www.contester.ru