分数: 500 点
问题陈述
给你一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
您可以按任意顺序重复以下两种操作,使 P 按升序排序。
-
操作 A: 选择一个整数 i 这样 1 \leq i \leq N-1,并交换 P_i 和 P_{i+1}.
-
操作 B: 选择一个整数 i 这样 1 \leq i \leq N-2,并交换 P_i 和 P_{i+2}.
查找具有以下属性的操作序列:
-
操作次数 A 是可能的最小值。
-
操作总数不大于 10^5.
在这个问题的约束下,我们可以证明解总是存在。
约束
- 2 \leq N \leq 400
- 1 \leq P_i \leq N \,(1 \leq i \leq N)
- P_i \neq P_j \,(1 \leq i < j \leq N)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
让 S 是您答案中的操作数。 打印 S+1 行。
第一行应包含 S.
的 (s+1)-th (1 \leq s \leq S)行应包含以下内容:
-
A i如果 s- 第一个操作是操作 A,并且在此操作中选择的整数是 i. -
B i如果 s- 第一个操作是操作 B,并且在此操作中选择的整数是 i.
如果有多个满足条件的解,则打印其中任意一个。
示例输入 1
4 3 2 4 1
示例输出 1
4 A 3 B 1 B 2 B 2
在此示例输出中, P 变化如下: (3,2,4,1) \rightarrow (3,2,1,4) \rightarrow (1,2,3,4) \rightarrow (1,4,3,2) \rightarrow (1,2,3,4).
请注意,您不必最小化操作总数。
示例输入 2
3 1 2 3
示例输出 2
0
示例输入 3
6 2 1 4 3 6 5
示例输出 3
3 A 1 A 3 A 5