Подразделы

Другие разделы

Дата и время

13/03/2025 15:20:18

Авторизация

941. Самая умная сортировка

Ограничения: время – 5s/10s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример вывода 1

1 4
1 3
2 4

Пример ввода 2

2
1 2

Пример вывода 2

Пример ввода 3

Пример вывода 3

Источник: Турнир "Экспонента-2008"

03/07/2008	Лето 2008 дорешивание ( 2F)
04/07/2008	Лето 2008 - 2 (F)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

941. Самая умная сортировка

Самая умная сортировка