题目描述

汉诺塔问题（$Hanoi\ Towers$）由三根柱子（分别命名为 $A$、$B$ 和 $C$）和 $n$ 个不同直径的圆盘组成。初始时，所有圆盘按从大到小的顺序叠放在柱子 $A$ 上，形成圆锥形结构。

合法移动规则

• 每次只能移动最顶端的圆盘，从一根柱子（源柱子）移动到另一根柱子（目标柱子）。
• 移动时，目标柱子必须满足以下条件之一：
  • 空柱子
  • 顶端圆盘的直径 > 当前移动的圆盘直径
• 用两个大写字母表示一次移动，例如 $AB$ 表示从柱子 $A$ 移动到柱子 $B$。

胜利条件

• 所有圆盘成功移动到柱子 $B$（$A$ 和 $C$ 为空）或柱子 $C$（$A$ 和 $B$ 为空）。

解题算法

1. 策略列表：游戏共有 $6$ 种可能的移动方式（$AB$、$AC$、$BA$、$BC$、$CA$、$CB$），按给定顺序排列。
2. 移动规则：
   • 每次选择策略列表中第一个合法的移动。
   • 额外限制：不能连续两次移动同一个圆盘（例如，不能 $AB$ 后紧接着 $BA$）。
3. 算法保证：该策略一定能解决汉诺塔问题。

问题要求

给定策略，计算最少需要多少步才能完成游戏。

输入格式

• 第一行：一个整数 $n$（$1 \leq n \leq 30$），表示圆盘数量。
• 第二行：$6$ 种移动策略，用空格分隔（例如：$AB\ BC\ CA\ BA\ CB\ AC$）。

输出格式

• 输出最少移动步数（不超过 $10^{18}$）。

样例输入 1

3  
AB BC CA BA CB AC  

样例输出 1

7  

样例输入 2

2  
AB BA CA BC CB AC  

样例输出 2

5  

来源

$Northeastern\ Europe\ 2007$