Сортировка массива
(Время: 1 сек. Память: 32 Мб Сложность: 26%)
Задан целочисленный массив A[1..N]. Элементы массива имеют различные значения от 1 до N. Требуется упорядочить элементы массива по возрастанию, используя последовательность обменов значений пары элементов. При этом разрешается проводить обмен только тех элементов, значения которых отличаются друг от друга на 1. Например, для элемента со значением 5 возможен обмен только с элементами со значением 4 или 6, а элемент со значением 1 можно менять только с элементом со значением 2.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 100) – количество элементов в массиве. Во второй строке заданы N разделенных пробелами различных чисел Ai (1 ≤ Ai ≤ N, 1 ≤ i ≤ N) – элементы массива.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите число k – количество ходов в возможной сортировке. На следующих k строках выведите последовательность ходов таким образом, чтобы на строчке с номером m было выведено два числа i и j, обозначающие позиции элементов массива, которые необходимо поменять на m-м шаге. Выведите любой вариант решения, количество операций в котором не превышает 50 000.
Если для заданного массива решения не существует, выведите «No solution» (без кавычек).
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
2 3 1 | 2
1 3
2 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
