201471: [AtCoder]ARC147 B - Swap to Sort

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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 i if the $s$-th operation is Operation $A$, and the integer chosen in this operation is $i$.

  • B i if 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

Input

题意翻译

## 题目描述 现有一个$1$到$N$的排列$ P=(P_1,P_2,\ldots,P_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$ 在题目条件的约束下，我们可以证明合法的解总是存在的 ## 输入格式 标准输入格式如下 #### $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ ## 输出格式 设你的答案中的操作次数为$S$。输出有$S+1$行。 第一行包含整数$S$ 第$(s+1)(1≤s≤S)$行中应包含以下内容。 - 如果第$s$个操作为$A$,输出`A i`，$i$为此次操作选择的整数 - 如果第$s$个操作为$B$,输出`B i`，$i$为此次操作选择的整数 如果有多个合法解，输出一个即可。 ## 样例 #1 ### 样例输入 #1 ``` 4 3 2 4 1 ``` ### 样例输出 #1 ``` 4 A 3 B 1 B 2 B 2 ``` ## 样例 #2 ### 样例输入 #2 ``` 3 1 2 3 ``` ### 样例输出 #2 ``` 0 ``` ## 样例 #3 ### 样例输入 #3 ``` 6 2 1 4 3 6 5 ``` ### 样例输出 #3 ``` 3 A 1 A 3 A 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) $ - 输入均为正数

Source/Category

加入题单

算法标签：