AT_arc177_b [ARC177B] Puzzle of Lamps

AtCoder 君制作了一个装置，由从左到右排列的一列 $N$ 个小灯泡和两种开关 A、B 组成。每个小灯泡有两种状态，`0`（关）和 `1`（开）。每当按下某个开关时，会发生以下情况： - 按下开关 A 时，最左侧处于 `0` 状态的小灯泡会变为 `1`。 - 按下开关 B 时，最左侧处于 `1` 状态的小灯泡会变为 `0`。 如果不存在符合条件的小灯泡，则无法按下该开关。 最开始，所有小灯泡都处于 `0` 状态。AtCoder 君希望将小灯泡的状态依次变为 $S_1,\ S_2,\ \dots,\ S_N$。请你回答应该按照什么顺序、按多少次开关，才能实现目标状态。这里不要求按下开关的次数最少，但为了保证操作能在合理时间内完成，按下开关的总次数不得超过 $10^6$。在本题的约束下，可以证明一定存在解。

输入通过标准输入给出，格式如下： > $N$ > $S_1\ S_2\ \dots\ S_N$ 注意，第二行以长度为 $N$ 的字符串形式给出。

如果你的操作方案是按下 $m$ 次开关（$1 \leq m \leq 10^6$），依次按下的开关为 $t_1,\ t_2,\ \dots,\ t_m$（每个都是 `A` 或 `B`），请按如下格式输出： > $m$ > $t_1\ t_2\ \dots\ t_m$ 第二行应输出长度为 $m$ 的字符串。

### 约束条件 - $1 \leq N \leq 30$ - $S_1,\ S_2,\ \dots,\ S_N$ 仅为 `0` 或 `1` - $S_1,\ S_2,\ \dots,\ S_N$ 不全为 `0` - $N$ 为整数 ### 样例解释 1 该输出样例对应的操作顺序是依次按下开关 A、A、A、B。如下图所示，可以将小灯泡变为目标状态。  另外，也可以按下 A、A、B、A、A、B 的顺序，同样能达到目标状态。对应的输出如下，也是正确答案。 ``` 6 AABAAB ``` 由 ChatGPT 4.1 翻译