Всем известна классическая задача о Ханойских башнях. Имеется три стержня, на один из которых нанизано n колец, радиус которых убывает снизу вверх, т.е. первое снизу кольцо имеет наибольший радиус, а первое сверху – наименьший. Задача заключается в том, чтобы перенести все кольца в том же порядке на другой стержень за наименьшее возможное число ходов. В течение одного хода разрешается перенести одно кольцо с одного стержня на другой, при этом кольца большего радиуса не разрешается класть на кольца меньшего радиуса.

Вам предлагается решить модифицированную версию задачи о Ханойских башнях: вместо трех стержней имеется четыре. Все остальные правила задачи остаются неизменными.