Парковка около Великой Стены состоит из длинного ряда парковочных мест, полностью
заполненного машинами. Один из краёв считается левым, а другой - правым. Каждая из машин имеет
свой тип. Типы перенумерованы натуральными числами и несколько машин могут иметь один и тот же тип.
Рабочие решили упорядочить машины в парковочном ряду так, чтобы их типы возрастали слева направо.
Упорядочение состоит из нескольких этапов. В начале каждого этапа рабочие одновременно выводят
машины с их мест, и затем ставят машины на свободные места, образовавшиеся в результате выезда
машин на данном этапе, т.е. меняют их местами. Каждый рабочий перемещает только одну машину за
этап, и некоторые рабочие могут не участвовать в перемещении машин на этапе. Эффективность
процесса упорядочивания машин определяется количеством этапов.
Предположим, что на парковке находится N машин и W рабочих. Требуется написать программу, которая
находит такое упорядочивание, при котором количество этапов не превосходит значения N/(W-1),
округлённого в большую сторону, т.е. [N/(W-1)]. Известно, что минимальное число этапов не
превосходит [N/(W-1)].
Рассмотрим следующий пример. На парковке находятся 10 машин типов 1, 2, 3, 4 и четверо рабочих.
Начальное положение машин слева направо, заданное их типами - 2 3 3 4 4 2 1 1 3 1.
Минимальное количество этапов - 3, и они могут быть выполнены так, что расположение машин по типам
после каждого из этапов следующее:
2 1 1 4 4 2 3 3 3 1 - после первого этапа,
2 1 1 2 4 3 3 3 4 1 - после второго этапа,
1 1 1 2 2 3 3 3 4 4 - после третьего этапа.
Входной файл имеет имя CAR.IN. Первая строка входного файла состоит их трёх чисел.
Первое - количество машин N, 2<=N<=20000. Второе - количество типов машин M, 2<=M<=50, причём тип
машины является натуральным числом от 1 до M. На парковке есть хотя бы одна машина каждого типа.
Третье - количество рабочих W, 2<=W<=M. Вторая строка содержит N целых чисел, где i-ое число
является типом i-ой машины в парковочном ряду, считая слева направо.
Выходной файл имеет имя CAR.OUT. Первая строка выходного файла содержит число R -
количество этапов. Далее следует R строк, где i+1 строка выходного файла описывает i-ый этап.
Формат строки, описывающей этап, следующий. Первое число - количество машин C, перемещаемых на
данном этапе. Далее следует C пар чисел, определяющих перемещения машин на данном этапе. Первое
число пары - позиция, с которой машина перемещается, второе число пары - позиция, на которую машина
перемещается. Позиция машины является целым числом от 1 до N и отсчитывается с левого конца ряда.
В случае, если существует несколько оптимальных решений, выдайте только одно из них.
Предположим, что количество этапов, выданных вашей программой - R, а [N/(W+1)] = Q. Если какой-то из R
этапов выдан некорректно, или после выполнения всех этапов типы машин не выстраиваются в
возрастающем порядке, вы набираете 0 очков за тест. В противном случае, ваши очки будут начислены
в соответствии со следующими правилами:
R<=Q 100% очков
R<=Q+1 50% очков
R<=Q+2 20% очков
R>=Q+3 0% очков
