Задача Newhanoy
Приклад
Введення: 3 3 10
Жюрі не сумнівається в тому, що всі фіналісти 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)Програма виводить на екран єдине число – шукану величину
.Задача про Ханойські вежі Є три стержні 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