ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Теннисная ракетка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
После завершения Сталинградской битвы было решено отправить переоснащённые дивизии Красной армии, участвовавшие в операции «Кольцо», на другие участки фронта по железной дороге.
Когда первый поезд с войсками и бронетехникой был сформирован, выяснилось, что железнодорожники не подумали о порядке вагонов. Для сортировки состава решили использовать железнодорожный тупик около химкомбината «Лазурь». Из-за своей формы и, возможно, из-за десятков немецких атак, отбитых на этом участке в ноябре 1942 года, тупик получил у пилотов немецких пикировщиков прозвище «теннисная ракетка».
Problem illustration
Состав сортируется следующим образом. Сперва он подгоняется хвостом к развилке, после чего последний вагон отцепляется и заводится в тупик. Все остальные вагоны по очереди отцепляют и заводят в тупик по одному из двух путей, присоединяя его либо к голове, либо к хвосту формируемого в тупике состава. Когда все вагоны заведены в «ракетку», сформированный состав целиком выводят оттуда головой вперёд.
Железнодорожники повторяют эту операцию до тех пор, пока состав не будет отсортирован. Помогите им выполнить эту работу как можно быстрее.

Исходные данные

В первой строке записано целое число n — количество вагонов в составе (2 ≤ n ≤ 10000). В следующей строке записана перестановка чисел от 1 до n — первоначальный порядок вагонов в составе, от головы к хвосту. В результате сортировки вагоны должны быть выстроены по порядку, начиная с первого.

Результат

В первой строке выведите целое число k — минимальное количество раз, которое необходимо завести состав в тупик для его сортировки. В каждой из следующих k строк должны быть записаны n чисел — порядок вагонов в составе после очередной операции. Если существуют несколько правильных ответов, выведите любой из них.

Пример

исходные данныерезультат
6
2 5 3 1 6 4
3
5 1 6 4 3 2 
1 2 3 4 6 5 
1 2 3 4 5 6 
Автор задачи: Даниил Айзенштейн
Источник задачи: XV Открытый чемпионат Урала по спортивному программированию (апрель, 2011)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1834. Теннисная ракетка