1. Newhanoy

Задача Newhanoy

Жюри не сомневается в том, что все финалисты NetOI-2008  умеют решать такую задачу:

Задача о  Ханойских башнях     

Имеются три стержня A, B, C и N колец разных диаметров, которые можно надевать на стержни. Сначала все кольца находятся на одном стержне (А) в порядке убывания их диаметров (диаметр верхнего кольца 1, а нижнего - N). Необходимо за минимальное количество ходов переместить всю пирамиду на  стержень С, используя в качестве вспомогательного  стержень B,  соблюдая при этом два правила:
-        за один ход можно перенести только одно кольцо;
-        любое кольцо можно надевать либо на пустой стержень, либо на стержень с  верхним кольцом большего диаметра.
Задача состоит в определении последовательности перемещений колец для переноса их с A на С

             

Но на сей раз после  решения задачи  конечный стержень становится начальным, вспомогательный - конечным, начальный - вспомогательным и  игра продолжается без перерыва. Потом вспомогательный стержень станет начальным, начальный - конечным, конечный - вспомогательным и т.д.   От начала игры с N дисками сделано K ходов. Определите, сколько раз перекладывался диск   диаметром T. 

Технические условия 

Программа Newhanoy читает с клавиатуры  три натуральных числа  N - количество дисков, (1 <= N <  64), T - диаметр  нужного диска (1<=T<=N),  K - количество ходов (1<= K <2⁶³). Программа выводит на экран одно число – искомую величину. 

Пример
Ввод:   3 3 10