Годинник | |
|
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 <263). Программа выводит на экран одно число – искомую величину.
Пример
Ввод: 3 3 10
Вывод: 1 |
|
|
