Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
941. Самая умная сортировка
Полный переборОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 2F) |
| 04/07/2008 | Лето 2008 - 2 (F) |
Ограничения: время – 5s/10s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Парламент уже давно вынашивал планы по созданию и законодательному закреплению "умной сортировки", ограничивающей ненужные перестановки в стране. Нашему корреспонденту удалось увидеть часть наброска к законопроекту:
Есть массив из `N` чисел – `1,\ 2,\ 3,\ …,\ N`. Потом некоторые его элементы переставляются. Нужно найти последовательность перестановок, которая все элементы вернет на место. Причем, делать перестановку `A_i\ ↔\ A_j` можно только один раз.
Перестановки `A_i\ ↔\ A_j` и `A_j\ ↔\ A_i` являются одной и той же перестановкой, так что если использована перестановка `A_i\ ↔\ A_j`, то
`A_j\ ↔\ A_i` использовать уже нельзя.
Что ж. Похоже, о целесообразности подобных изысканий остается только догадываться. Ну а проверку разумности и возможности осуществления таких сортировочных действий мы оставляем читателю.
Ввод
Первая строка – число `N` (количество чисел в массиве), где `N\ ≤\ 6`.
Последующие строки до конца файла – пары позиций `(i,\ j)` в массиве, элементы в которых переставляются (происходит обмен `A_i\ ↔\ A_j`).
Вывод
Последовательность пар позиций `(i,\ j)`, которая вернет все на место. Каждая пара должна быть использована не больше одного раза, и те пары, которые были во входном файле, использовать нельзя. Если такой последовательности не существует, то вывести одно число 0. Если таких последовательностей несколько, то вывести любую из них.
Пример ввода 1
4 1 2 3 4 2 3
Пример вывода 1
1 4 1 3 2 4
Пример ввода 2
2 1 2
Пример вывода 2
0
Пример ввода 3
6 1 6 2 5 3 4
Пример вывода 3
1 2 1 3 1 4 2 3 2 4 5 6 1 5 2 6 3 5 4 5 4 6
