/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。あなたは以下の 2 種類のどちらかの操作を行うことを繰り返すことで P を昇順に並び替えたいです。
-
操作 A：1 \leq i \leq N-1 を満たす整数 i を選び、P_i と P_{i+1} を入れ替える
-
操作 B：1 \leq i \leq N-2 を満たす整数 i を選び、P_i と P_{i+2} を入れ替える
操作 A の回数が最小となり、かつ操作回数の合計が 10^5 回以下であるような操作の手順を 1 つ示してください。
なお、この問題の制約のもとで、条件を満たす解が存在することが証明できます。
制約
- 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\,(0 \leq S \leq 10^5) 回としたとき、S+1 行出力せよ。
1 行目には S を出力せよ。
s+1\,(1 \leq s \leq S) 行目には、
-
s 回目の操作が操作 A で、選ぶ整数が i\,(1 \leq i \leq N-1) の場合、
A iを -
s 回目の操作が操作 B で、選ぶ整数が i\,(1 \leq i \leq N-2) の場合、
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
Score : 500 points
Problem Statement
You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
You can repeat the following two kinds of operations in any order to make P sorted in increasing order.
-
Operation A: Choose an integer i such that 1 \leq i \leq N-1, and swap P_i and P_{i+1}.
-
Operation B: Choose an integer i such that 1 \leq i \leq N-2, and swap P_i and P_{i+2}.
Find a sequence of operations with the following property:
-
The number of Operations A is the minimum possible.
-
The total number of operations is not larger than 10^5.
Under the Constraints of this problem, we can prove that a solution always exists.
Constraints
- 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)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Let S be the number of operations in your answer. Print S+1 lines.
The first line should contain S.
The (s+1)-th (1 \leq s \leq S) line should contain the following:
-
A iif the s-th operation is Operation A, and the integer chosen in this operation is i. -
B iif the s-th operation is Operation B, and the integer chosen in this operation is i.
If there are multiple solutions satisfying the condition, printing any of them will be accepted.
Sample Input 1
4 3 2 4 1
Sample Output 1
4 A 3 B 1 B 2 B 2
In this Sample Output, P changes like this: (3,2,4,1) \rightarrow (3,2,1,4) \rightarrow (1,2,3,4) \rightarrow (1,4,3,2) \rightarrow (1,2,3,4).
Note that you don't have to minimize the total number of operations.
Sample Input 2
3 1 2 3
Sample Output 2
0
Sample Input 3
6 2 1 4 3 6 5
Sample Output 3
3 A 1 A 3 A 5