215. Towers of Hanoi
Three pegs, and n discs stacked on the first in decreasing size. Move the
whole stack to the third peg. You may move one disc at a time, and a larger
disc may never sit on a smaller one.
Print the smallest number of moves needed.
The recursive argument is worth following, because it is the whole answer: to
move n discs, first move the top n-1 out of the way, then move the largest
one, then move the n-1 back on top of it.
Do not simulate the moves. At n = 62 there are more moves than a computer
could print in a lifetime, and the count itself is a one-line formula.
Constraints - `1 ≤ n ≤ 62`
Input
A single line containing one integer n, the number of discs.
Output
Print one integer, the minimum number of moves.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.