Олимпиадная информатика - 2010

Задача «ОБРАТНАЯ ПЕРЕСТАНОВКА»

По заданной перестановке требуется определить обратную.

Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно PN =N!

Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить а[i] элемент множества, где а[i] — i-тый элемент перестановки.

Обратной перестановкой к перестановке ? называется такая перестановка ? , что последовательное их применение даёт е, где е — тождественная перестановка, т.е. опять упорядоченная последовательность от 1 до N.

Входные данные

В первой строке входного файла INPUT.TXT записано число 0<N <= 20000 - порядок перестановки. Во второй строке записана сама перестановка. Выходные данные В выходной файл OUTPUT.TXT выведите обратную перестановку.

INPUT.TXT

3 2 3 1

OUTPUT.TXT

3 1 2

program w2;
var a:array[0..20001]of integer;i,j,n:integer;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
read(n); {Ввод порядка перестановки}
for i:=1 to n do
begin
read(j); {Ввод очередного элемента данной перестановки}
a[j]:=i; {Присваивание значения элементу новой перестановки}
end;
for i:=1 to n do
write(a[i],' '); {Вывод результата}
close(input);close(output);
end.




close
 

Разбор задачи №6 "Обратная перестановка"

В условии, хотя и довольно запутанно, объясняется, что такое обратная перестановка. Перефразируем немного условие задачи. Дан массив из N первых натуральных чисел.

Нужно получить из этих же чисел другой массив, в котором на k-том месте стоит число, которое указывает, на каком месте в первом массиве находится число k. Отсюда решение: в цикле от 1 до N запрашиваем число I-й элемент первого массива – число J и J-ному элементу второго массива присваиваем значение I.

При этом запоминать сам первый массив необязательно. Осталось вывести полученный массив в порядке возрастания индексов. Листинг получается самый короткий. Возможно, поэтому задача оценена только в 20 баллов.

Но всё-таки на мой взгляд эту задачу нельзя назвать утешительной для районного тура.