eolymp
bolt
Try our new interface for solving problems
Məsələlər

Алгоритм профессора Иванова

Алгоритм профессора Иванова

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Профессор Иванов рассказал профессору Петрову, что придумал новый способ сортировки. В его основе лежит следующая функция change.

function change(a: integer);

begin

for j := 0 to n - 1 do

begin

if p[j] = a then

k := j

end

swap(k, (k + p[k]) mod n);

end;

Функция swap(i, j) меняет местами элементы массива p_i и p_j.

Профессор Иванов утверждает, что любой массив p_0, …, p_{n−1}, являющийся перестановкой целых чисел 1, ..., n, можно упорядочить по возрастанию, несколько раз вызвав функцию change. Нужно только правильно подобрать для каждого вызова функции в качестве её аргумента a целое число в пределах от 1 до n.

Профессор Петров верит коллеге, но он не очень хорошо понял, как работает алгоритм. Поэтому он предложил перестановку p_0, …, p_{n−1} и попросил профессора Иванова отсортировать её по возрастанию с помощью функции change.

Giriş verilənləri

В первой строке записано целое число n (1 n 500). Во второй строке записаны целые числа p_0, …, p_{n−1} в пределах от 1 до n - перестановка, предложенная профессором Петровым.

Çıxış verilənləri

Если профессор Иванов не сможет с помощью функции change отсортировать массив p_0, …, p_{n−1} по возрастанию, выведите "Impossible". В противном случае выведите в первой строке число m — количество вызовов функции (0 m 10^6). В следующих m строках выведите аргументы, которые нужно подавать на вход функции change. Гарантируется, что если массив можно отсортировать по возрастанию, то это можно сделать не более чем за 10^6 вызовов функции.

Nümunə

Giriş verilənləri #1
5
1 3 5 2 4
Çıxış verilənləri #1
37
1
1
2
1
1
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
Müəllif О.Соболева, Д.Дублённых
Mənbə 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача H