Problem Description

经典的汉诺塔问题中有 3 根柱子，分别记为 A、B、C。初始时，$n$ 个大小互不相同的盘子按从小到大的顺序（编号 1 到 n，1 最小，n 最大）全部套在 A 柱上，目标是将所有盘子移动到 C 柱。移动规则：

1. 每次只能移动一个盘子；
2. 任何时候，大盘子都不能压在小盘子上面。

已知按照最短路径（总步数为 $2^n-1$ 的唯一最优解）进行移动。求在恰好完成第 $x$ 步移动之后，每个盘子分别位于哪根柱子。

Input Format

输入共一行，包含两个整数 n 和 x。n 为盘子总数；x 为已完成的移动步数（x=0 表示尚未开始）。

Output Format

输出一行长度为 n 的字符串，第 i 个字符表示编号为 i 的盘子所在柱子（'A'、'B' 或 'C'）。

3 0

AAA

3 3

BBA

4 10

CABC

Hint

说明/提示

【数据范围】

• 对于 $30\%$ 的数据，$1 \le n \le 10$。
• 对于 $60\%$ 的数据，$1 \le n \le 30$。
• 对于 $100\%$ 的数据，$1 \le n \le 60$，$0 \le x \le 2^n - 1$。

Source

原创