Задача №113916. Быстрая сортировка
Новый процессор UL-2018, разработанный в научной лаборатории, предназначен для быстрой обработки массивов. Ключевой особенностью архитектуры нового процессора является операция расслоения отрезка массива.
Рассмотрим массив [ a 1 , a 2 , ..., a n ] . Операция расслоения характеризуется двумя целыми числами l и r — номером первого и последнего элемента отрезка массива, к которому она применяется. Обозначим операцию расслоения отрезка массива [ a l , a l + 1 , ..., a r ] как S ( l , r ) . После выполнения операции S ( l , r ) элементы массива на этом отрезке переупорядочиваются следующим образом. Сначала располагаются элементы отрезка с позиций a l + 1 , a l + 3 , ... , то есть элементы с позиций i , для которых значение i - l нечетно, их относительный порядок остаётся неизменным. Затем идут элементы отрезка a l , a l + 2 , ... , то есть элементы с позиций i , для которых значение i - l четно, они также сохраняют свой относительный порядок.
Например, рассмотрим массив [2, 4, 1, 5, 3, 6, 7, 8] . После выполнения операции расслоения S (2, 6) изменится порядок элементов на отрезке массива [4, 1, 5, 3, 6] . Новый порядок элементов на этом отрезке следующий: [1, 3, 4, 5, 6] , а весь массив после выполнения этой операции равен [2, 1, 3, 4, 5, 6, 7, 8] .
Для демонстрации возможностей нового процессора решено было использовать операцию расслоения для реализации алгоритма сортировки массива различных чисел. Задан массив, содержащий n элементов, 1 ≤ n ≤ 3000 . Элементы массива — различные целые числа от 1 до n . Необходимо отсортировать заданный массив по возрастанию, используя не более 15 000 операций расслоения отрезка массива.
Например, приведенный выше массив [2, 4, 1, 5, 3, 6, 7, 8] можно отсортировать, используя две операции расслоения. Сначала выполним продемонстрированную выше операцию S (2, 6) , после которой массив принимает вид [2, 1, 3, 4, 5, 6, 7, 8] , а затем операцию S (1, 2) , массив примет вид [1, 2, 3, 4, 5, 6, 7, 8] .
Требуется написать программу, которая по заданному массиву определит последовательность не более, чем из 15 000 операций расслоения, после выполнения которых заданный массив окажется отсортирован по возрастанию. Минимизировать количество выполненных операций расслоения не требуется, достаточно использовать не более 15 000 операций.
Первая строка входных данных содержит целое число n — количество элементов в заданном массиве ( 1 ≤ n ≤ 3000 ).
Вторая строка содержит n целых чисел a 1 , a 2 , ..., a n — элементы заданного массива ( 1 ≤ a i ≤ n , все a i различны).
В первой строке выходных данных необходимо вывести целое число k — количество выполненных операций расслоения ( 0 ≤ k ≤ 15 000 ).
В последующих k строках необходимо вывести описание самих операций, в порядке их выполнения. Каждая операция описывается двумя целыми числами l и r — номером первого и последнего элемента отрезка массива, к которому необходимо применить очередную операцию расслоения ( 1 ≤ l ≤ r ≤ n ).
Следует обратить внимание, что минимизировать число k не требуется. Из возможных последовательностей операций расслоения, содержащих не более 15 000 операций, после выполнения которых заданный массив будет отсортирован по возрастанию, можно вывести любую. Гарантируется, что хотя бы одна такая последовательность существует.
Второй тест из примера подробно разобран в условии задачи.
Для третьего теста из примера существует решение из одной операции расслоения, но поскольку минимизировать количество операций не требуется, приведенный в примере ответ также является правильным.
5 3 1 4 2 5
7 2 3 1 2 1 4 4 5 4 5 1 4 1 2
8 2 4 1 5 3 6 7 8
16 1 2 2 3 1 4 1 2 4 5 1 4 3 6 6 7 7 8 5 8 1 6 2 7 5 6 4 5 1 4 1 2
2 2 1
1 1 2