分数: 400 点
问题陈述
AtCoder 先生创建了一个设备,其中包含 N 小灯泡从左到右排成一排,有两个开关A和B。每个灯泡可以处于两种状态之一: 0 (关闭)和 1 (开)。按下每个开关会导致以下结果:
- 按下开关 A 将打开最左边的灯泡
0状态进入1. - 按下开关 B 将打开最左边的灯泡
1状态进入0.
如果没有适用的灯泡,则无法按下开关。
最初,所有灯泡都在 0 状态。他希望灯泡的状态是 S_1, S_2, \dots, S_N 从左到右。确定实现此目的应按下开关的顺序和次数。没有必要尽量减少按压次数,但最多应该 10^6 以便操作可以在现实的时间内完成。可以证明在该问题的约束下存在解。
约束
- 1 \leq N \leq 30
- 每个 S_1, S_2, \dots, S_N is
0or1. - 并非全部 S_1, S_2, \dots, S_N 是
0. - N 是一个整数。
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \dots S_N
请注意,第二行以长度为字符串的形式给出 N.
输出
如果您的解决方案按下开关 m 次 (1 \leq m \leq 10^6) 顺序 t_1, t_2, \dots, t_m (每个都是 A or B),按以下格式打印:
m t_1 t_2 \dots t_m
第二行应打印为长度的字符串 m.
示例输入 1
5 01100
示例输出 1
4 AAAB
此示例输出提供了一个按顺序按下开关 A、A、A、B 的解决方案。这会将灯泡设置为所需的状态,如下图所示:

或者,按 A、A、B、A、A、B 的顺序按下开关也可以将灯泡设置为所需状态。与此解决方案相对应的以下输出也将被接受:
6 AABAAB