#2158. 「POI2011 R1」移方块 Shift

内存限制:256 MiB 时间限制:400 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: ceba_robot

题目描述

译自 POI 2011 Round 1. D「Shift

Byteasar bought his son Bytie a set of blocks numbered from 1 1 to n n and arranged them in a row in a certain order. Bytie's goal is to rearrange the blocks so that they are ordered naturally, from the smallest number to the largest. However, the only moves Bytie is allowed to make are:

  • putting the last block at the very beginning (move a), and
  • putting the third block at the very beginning (move b).

Help Bytie by writing a program that tells whether a given arrangement of blocks can be properly reordered, and tells the right sequence of moves if it is.

Byteasar 给他的儿子 Bytie 买了一盒共 n n 块积木,他将这些积木从 1 1 n n 编号,并按照一定的顺序摆成一排。Bytie 要将这些积木按照编号从小到大的顺序重新排列,但他只能做下面两种操作:

  • 操作 a:将最后一个积木移到最前面。
  • 操作 b:把第三个积木移到最前面。

我们将连续进行 k k 次同一个操作称为“一块操作”,表示为 ka k a kb k b
你需要帮助 Bytie 写一个程序,告诉他有没有一个操作序列能够使积木按照编号从小到大的顺序重新排列,并告诉他操作序列。

输入格式

In the first line of the standard input there is a single integer n n , 1n2000 1 \le n \le 2000 . In the second line there are n n integers from the range to 1 1 , n n separated by single spaces. No number appears twice, and thus they represent the initial arrangement of the blocks.

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

输出格式

If there is no sequence of moves leading to an arrangement with increasing blocks' numbers, your program should print out "NIE DA SIE" (there is no way in Polish), without the quotation marks.

Otherwise there should be a single integer m m (mn2 m \le n^2 ), denoting the number of operations, in the first line. An operation is a k k -fold execution of either a or b move.

If m>0 m \gt 0 , then there should be a sequence of m m integers with either a or b appended in the second line. Thus kak a(for 0<k<n 0 \lt k \lt n ) denotes the k k -fold execution of the move a. Analogously, kb k b (for 0<k<n 0 \lt k \lt n ) denotes the k k -fold execution of the move b.

Furthermore, the characters appended to the numbers in the second line have to alternate.

Should there be more than one solution, your program is free to pick one arbitrarily.

如果没有一种方案能将积木按照编号从小到大的顺序重新排列,你应当输出NIE DA SIE(波兰语中的There is no way)。

否则,第一行你应当输出一个整数 m m ,表示操作的块数m m 必须满足 m<n2 m \lt n^2
第二行表示这 m m 块操作,每块操作之间用空格隔开。
每一块包含操作数 k k 和操作方式,中间没有空格,如3a3 3 次 a 操作)。
需要满足相邻两块操作的种类不同,每块操作中进行的次数 0<k<n 0 \lt k \lt n

样例

For the input data:输入样例1

4
1 3 2 4

the correct result is:输出样例1

4
3a 2b 2a 2b

whereas for the input data: 输入样例2

7
1 3 2 4 5 6 7

the correct output is: 输出样例2

NIE DA SIE

and for the input data: 输入样例3

3
1 2 3

the correct output is: 输出样例3

0

数据范围与提示

对于 100% 100\% 的数据,1n2000 1 \le n \le 2000

Task authors: Krzysztof Diks & Wojciech Rytter.
翻译和 SPJ: ceba.