题目描述

三根柱子编号为 $A,B,C$。初始时 $n$ 个盘全在 $A$ 上，小盘叠在大盘上。每步只能从某根柱顶取一个盘放到另一根柱顶，且不能把大盘压在小盘上。移动方向只能是 $A\to B$、$B\to C$、$C\to A$。求把所有盘从 $A$ 移到 $C$ 的最少步数。

输入格式

一行一个正整数 $n$，表示圆盘数。

输出格式

输出最少移动步数。

2

7

3

21

样例说明

两个盘的一种最优移动顺序是：小盘 $A\to B$，小盘 $B\to C$，大盘 $A\to B$，小盘 $C\to A$，大盘 $B\to C$，小盘 $A\to B$，小盘 $B\to C$。

数据范围

$1\le n\le20$。

来源

洛谷 B4579 · CCF GESP C++ 四级。