题目描述
The ancient folklore behind the “Towers of Hanoi'' puzzle is quite well known. A more recent legend tells us that once the Brahmin monks discovered how long it would take to finish transferring the 64 discs from the needle which they were on to one of the other needles, they decided to find a faster strategy and be done with it.
The Four Needle (Peg) Tower of Hanoi
One of the priests at the temple informed his colleagues that they could achieve the transfer in single afternoon at a one disc-per-second rhythm by using an additional needle. He proposed the following strategy:
First move the topmost discs (say the top k discs) to one of the spare needles.
Then use the standard three needles strategy to move the remaining n – k discs (for a general case with n discs) to their destination.
Finally, move the top k discs into their final destination using the four needles.
He calculated the value of k which minimized the number of movements and found that 18,433 transfers would suffice. Thus they could spend just 5 hours, 7 minutes, and 13 seconds with this scheme versus over 500, 000 million years without the additional needle!
Try to follow the clever priest's strategy and calculate the number of transfers using four needles, where the priest can move only one disc at a time and must place each disc on a needle such that there is no smaller disc below it. Calculate the k that minimizes the number of transfers under this strategy.
输入
The input file contains several lines of input. Each line contains a single integer 0<= N<=10, 000 giving the number of disks to be transferred. Input is terminated by end of file.
输出
For each line of input produce one line of output which indicates the number of movements required to transfer the N disks to the final needle.
样例输入
1
2
28
64
样例输出
1
3
769
18433
参考代码
暂无
解析
暂无
