← 返回题目列表

AtCoder · arc177_b

B. 灯之谜

中文机器翻译题面 查看原题

分数: 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 0 or 1.
  • 并非全部 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