网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[URAL 1568]火车车厢排序
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | traincarsorting.in | 输出文件 | 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