Страница: 1 Отображать по:
#37
\"Сортировка\" с конфеткой
  

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные

Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

Выходные данные

Требуется вывести массив после сортировки.

Примеры
Входные данные
4
1 4 2 3
2
4 3
1 2
Выходные данные
1 2 4 3
#543
Военная сортировка
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача H ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Требуется упорядочить числа от 1 до N. Разрешается менять только соседние числа и нельзя переставлять число, которое уже стоит на своем месте.

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из \(N\) чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до \(N\), и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число \(i\)).

В связи с повышенными требованиями к надежности комплекса в процессе сортировки разрешается выполнять единственную операцию - менять местами два соседних элемента массива. Кроме того, в связи с необходимостью соответствия уставу, не разрешается изменять положение числа, которое уже находится на своем месте.

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

Вам дан входной массив и поставлено важное задание. Найти последовательность обменов (не обязательно кратчайшую), сортирующую массив и удовлетворяющую приведенным условиям.

Подсказка

Найти такую последовательность обменов всегда возможно.

Входные данные

В первой строке вводится целое число \(N\) - размер входного массива (1 <= \(N\) <= 100). Вторая строка содержит \(N\) целых чисел - исходную перестановку чисел от 1 до \(N\) в массиве. Изначально ни одно число не стоит на своем месте.

Выходные данные

Выведите \(K\) строк, где \(K\) - количество обменов в Вашей сортировке. На каждой строке выведите по два числа \(x_i\) и \(y_i\), разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |\(x_i\) - \(y_i\)| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

Пояснение к примеру

В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

Примеры
Входные данные
6
2 3 1 6 4 5
Выходные данные
2 3
1 2
4 5
5 6
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест