[NOIP 2007 Junior] Double Tower of Hanoi

Problem Description

Given three sufficiently long pegs A, B, C. On peg A there are $2n$ center-holed disks, of $n$ different sizes, and for each size there are exactly two identical disks (the two disks of the same size are indistinguishable). The figure below shows the case $n = 3$.

The goal is to move all these disks onto peg C, using peg B for temporary storage during the process. Requirements:

1. Only one disk may be moved at a time;
2. On pegs A, B, and C, the disks must always remain in order of decreasing size from bottom to top.

Task: Let $A_n$ be the minimum number of moves needed to complete the task for $2n$ disks. For the given $n$, output $A_n$.

Input Format

A positive integer $n$, meaning there are $2n$ disks on peg A.

Output Format

A positive integer: the minimum number of moves $A_n$ needed to complete the task.

Sample Input 1

1

Sample Output 1

2

Sample Input 2

2

Sample Output 2

6

Constraints

• For $50\%$ of the data, $1 \le n \le 25$;
• For $100\%$ of the data, $1 \le n \le 200$.

Hint

Try to derive a recurrence relation between $A_n$ and $A_{n-1}$.