ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Профессор Иванов рассказал профессору Петрову, что придумал новый способ сортировки. В его основе лежит следующая функция change.
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) меняет местами элементы массива pi и pj.
Профессор Иванов утверждает, что любой массив p0, …, pn − 1, являющийся перестановкой целых чисел 1, ..., n, можно упорядочить по возрастанию, несколько раз вызвав функцию change. Нужно только правильно подобрать для каждого вызова функции в качестве её аргумента a целое число в пределах от 1 до n.
Профессор Петров верит коллеге, но он не очень хорошо понял, как работает алгоритм. Поэтому он предложил перестановку p0, …, pn − 1 и попросил профессора Иванова отсортировать её по возрастанию с помощью функции change.

Исходные данные

В первой строке записано целое число n (1 ≤ n ≤ 500). Во второй строке записаны целые числа p0, …, pn − 1 в пределах от 1 до n — перестановка, предложенная профессором Петровым.

Результат

Если профессор Иванов не сможет с помощью функции change отсортировать массив p0, …, pn − 1 по возрастанию, выведите «Impossible». В противном случае выведите в первой строке число m — количество вызовов функции (0 ≤ m ≤ 106). В следующих m строках выведите аргументы, которые нужно подавать на вход функции change. Гарантируется, что если массив можно отсортировать по возрастанию, то это можно сделать не более чем за 106 вызовов функции.

Пример

исходные данныерезультат
5
1 3 5 2 4
3
4
3
3
Автор задачи: Ольга Соболева (подготовка — Денис Дублённых)
Источник задачи: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1958. Алгоритм профессора Иванова