← 返回题目

题库练习「POI2011 R1」移方块 Shift

← 上一题下一题 →

A6324 | $「POI2011 R1」移方块 Shift$

时间限制400ms

内存限制256MB

通过 / 提交0/0

题目描述

**译自 POI 2011 Round 1. D「[Shift](https://szkopul.edu.pl/problemset/problem/n6S4y9QrbGqYUz64e2O-OV7D/site/?key=statement)」** Byteasar 给他的儿子 Bytie 买了一盒共 $ n $ 块积木，他将这些积木从 $ 1 $ 到 $ n $ 编号，并按照一定的顺序摆成一排。Bytie 要将这些积木按照编号从小到大的顺序重新排列，但他只能做下面两种操作： * 操作 a：将最后一个积木移到最前面。 * 操作 b：把第三个积木移到最前面。 我们将连续进行 $ k $ 次同一个操作称为「一块操作」，表示为 $ k a $ 或 $ k b $。 你需要帮助 Bytie 写一个程序，告诉他有没有一个操作序列能够使积木按照编号从小到大的顺序重新排列，并告诉他操作序列。

输入格式

输入的第一行包含一个整数 $ n $，表示积木的个数。 第二行包含 $ n $ 个整数，表示积木初始的排列顺序，没有重复的数字。

输出格式

如果没有一种方案能将积木按照编号从小到大的顺序重新排列，你应当输出 NIE DA SIE（波兰语中的 There is no way）。 否则，第一行你应当输出一个整数 $ m $，表示操作的**块数**，$ m $ 必须满足 $ m \le n^2 $。 第二行表示这 $ m $ 块操作，每块操作之间用空格隔开。 每一块包含操作数 $ k $ 和操作方式，中间**没有**空格，如 3a（$ 3 $ 次 a 操作）。 需要满足相邻两块操作的种类不同，每块操作中进行的次数 $ 0 \lt k \lt n $。

输入输出样例

输入 #1

4
1 3 2 4

输出 #1

4
3a 2b 2a 2b

输入 #2

7
1 3 2 4 5 6 7

输出 #2

NIE DA SIE

输入 #3

3
1 2 3

输出 #3

C++ 编辑器

输入

输出