<ПРЕД Задача:
СЛЕД>
Задачу решили 126 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Корень из перестановки

Time limit = 2 секунд(ы)

Дана перестановка A первых N натуральных чисел. Найдите такую перестановку X, применение которой дважды дает перестановку A. То есть решите уравнение

X * X = A,

где X и A перестановки. Если решений несколько, то выведите одно и них.

Перестановка "2 3 4 1" означает, что 2-ой элемент переместился на первое место, 3-й — на второе, 4-й — на третье, и 1-й — на четвертое место.

Вход В первой строчке указано число N (0 < N < 10001), а во второй дана перестановка A первых N натуральных чисел.

Выход Если решений нет, выведите число 0. Иначе, выведите одно из решений.

Вход#1
4
2 3 4 1
Выход#1
0

Вход#2
4
3 4 1 2
Выход#2
2 3 4 1


Автор:
Ворожцов Артем, Физтех олимпиада 3 октября 2004 при поддержке компании NIX.
3 октября 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 100.24.209.47