Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 4 Contest LoginRegister Exam
Problem 1059. -- The Priest Mathematician

The Priest Mathematician

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 8  Solved: 0
[Submit][Status][Discuss]

Description

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.

Input

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.

Output

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.

Sample Input

1
2
28
64

Sample Output

1
3
769
18433

HINT

Source

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin