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

Турниры > Тренировочный турнир сезона «Лето — 2022» > задача:


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

Тренировочный турнир сезона «Лето — 2022»

Старт: 01.июня.2022 в 14:00:00
Финиш: 31.авг.2022 в 23:00:00
Осталось: 362:36:30
• Турнирная таблица

Задачи турнира

• K. Макс и аквариумистика
• L. Автоформатирование
• M. Макс и продажа кристаллов
• N. Макс и доллары
• O. Макс и невзламываемый пароль
• P. Макс и лотерея
• Q. Макс и розы
• R. Макс и сериал
• S. Ханойские башни
• T. Простейшая задача

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

Если у вас есть предложения или пожелания по работе 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