Monkey Tower
Time limit2sMemory limit128 MB
Compute the minimum number of moves to solve a 4-peg Tower of Hanoi with up to one million disks, using the Frame-Stewart recurrence modulo 9901.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Math, Recursion, Number theory
- Solved
- No attempts yet
Problem
Monkey Tower follows the same rules as the Tower of Hanoi, except that it has 4 pegs.
Initially, N disks of distinct sizes are stacked on peg 1. The goal is to move all disks to peg 4.
Each move must follow these rules.
- A larger disk may not be placed on top of a smaller disk.
- Exactly one disk may be moved to another peg at a time.
Find the minimum number of moves needed to move all N disks from the initial state to peg 4.
Input
The first line contains the number of disks N. N is a positive integer not greater than 1,000,000.
Output
Print the minimum number of moves needed to move the N disks, modulo 9901.
Hint
This problem can be solved using the Frame-Stewart conjecture for the optimal number of moves in the four-peg Tower of Hanoi.