[URAL 1568]火车车厢排序

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file traincarsorting.in Output file traincarsorting.out

【题目描述】

在叶卡捷琳堡,有一些塔在同时被建造。建筑需要许多高质量的五金件和材料,它们中的大部分通过铁路运来。铁路运输并不总像承包商希望的那样快。火车在中间站停了太久,它们在那里被排好序并且定向到通向不同地区的铁轨。

正如你所知,货运列车车厢以如下方式被排序:火车被开到一个双向岔道,在那里每一节车厢都可以走左边或右边的岔道。之后,这些车厢重新连接起来。例如,如果车厢的顺序是“1 2 3 4 5 6 7”,它们可以被分成两部分:“1 3 5”(左岔道)和“2 4 6 7”(右岔道),然后重新连接:“1 3 5 2 4 6 7”。

请你帮助铁路工人加速车厢的排序过程。写一个程序来将重新排列给定顺序的车厢,要求将两个岔道中的车厢重新连接的次数最小。

【输入格式】

输入文件的第一行有一个正整数N——车厢的数量(1<=N<=10000)。第二行有N个整数,即最初的车厢排列顺序。每个车厢都有一个1~N之间独特的编号。这些车厢必须被重新排列使得编号递增,从1开始。

【输出格式】

输出文件的第一行有一个正整数K,即重新连接操作的最小次数。接下来的K+1行每行有N个正整数。在第一行输出车厢最初的顺序,接下来的每一行都输出一次重新连接后车厢的顺序。

【样例输入】

sample 1:


5

5 1 3 2 4



sample 2:


6

6 5 2 4 1 3


【样例输出】

sample 1:


2

5 1 3 2 4

1 2 5 3 4

1 2 3 4 5


sample 2:


3

6 5 2 4 1 3

6 4 1 5 2 3

6 1 2 3 4 5

1 2 3 4 5 6


【提示】

对于40%的数据,1<=N<=10

对于60%的数据,1<=N<=1000

对于100%的数据,1<=N<=10000

【来源】

Problem Author: Sergey Pupyrev

Problem Source: The XIIth USU Programing Championship, October 6, 2007

URAL 1568