0004. Обмены

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

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

Формат входного файла

Входной файл в первой строке содержит одно число N (1 ≤ N ≤ 1000). В следующей строке через пробел перечислены N целых чисел ai (-30000 ≤ ai ≤ 30000).

Формат выходного файла

В выходной файл требуется вывести последовательность обменов, которые приводят к упорядоченности, по одному в строке. Каждый обмен описывается двумя целыми числами: индексами элементов последовательности A (порядок индексов не важен). Количество обменов не должно превосходить 10 000 000. Если существует несколько способов получить упорядоченную по неубыванию последовательность, выведите любой из них.

Пример:

input.txtoutput.txt
6 3 6 1 3 8 -4 5 6 1 2 5 1 2 3

Пояснение:

Опишем процесс преобразования исходной последовательности в упорядоченную.

  1. 3 6 1 3 8 -4
  2. 3 6 1 3 -4 8 (меняем местами 5 и 6 элементы)
  3. 6 3 1 3 -4 8 (меняем местами 1 и 2 элементы)
  4. -4 3 1 3 6 8 (меняем местами 5 и 1 элементы)
  5. -4 1 3 3 6 8 (меняем местами 2 и 3 элементы)
В результате получили неубывающую последовательность.


Источник: Районная олимпиада РК по информатике, 2007.

Обсудить       Отправить решение