In one of the Buddhist
monasteries, monks have been rearranging discs for a thousand years. They have
three pegs with discs of different sizes. Initially a certain number of disks
are put on the first peg and ordered by size – from smallest to largest from
top to bottom. Monks must move all discs from the first peg to the third one,
satisfying the only condition - any disc cannot be placed on a smaller disc.
All three pegs can be used for moves. The monks move one disc in one second.
Once they finish their work, the world will come to an end.
Well, is it like a monk to
bring the end of the world closer? Wrong monks ... :)
Therefore, we will not be
interested in the answer to a question somehow related to the apocalypse, but
will be interested in the answer to a more familiar question in our everyday
life: What is the least number of
moves the monks will be able to complete their work, provided that they move
the disks in optimal way?
Input. Number of discs n (0 ≤ n ≤ 64) available to monks. By a strange coincidence, the
number of disks in this problem does not exceed the number of cells on an
ordinary chessboard.
Output. Print the smallest number of
moves for which the monks can complete their work.
|
Sample input |
Sample output |
|
3 |
7 |
Hanoi towers
To move n disks
from the first to the third peg, you should:
•
move
n – 1 discs from the
first to the second peg
•
move
the remaining one (largest) disc from the first to the third peg
•
move n – 1 discs from the
second to the third peg
Let f(n) be the required number of moves. Then we get
the recurrence relation:
f(n) = 2 * f(n – 1) + 1
Let's calculate
some values
of this
function:
f(1) =
1,
f(2) = 2
* f(1) + 1 = 3,
f(3) = 2
* f(2) + 1 = 7,
f(4) = 2
* f(3) + 1 = 15
Let us prove by
the method of mathematical induction that f(n)
= 2n – 1.
Base step. f(1) = 21
– 1 = 1.
Inductive step. f(n + 1) = 2 * f(n) + 1 = 2 * (2n
– 1) + 1 = 2n+1
– 1.
Since n ≤
64, the answer to problem 2n –
1 does not fit into a 64-bit signed type. Let's use an unsigned 64-bit integer type unsigned long
long.
Read the value of n.
scanf("%llu", &n);
Compute
res = 2n.
res = 1;
for (i = 0;
i < n; i++)
res = res * 2;
Print
the answer res – 1 = 2n – 1.
printf("%llu\n", res - 1);