Медленная сортировка
Задачу добавил: 42
Успешно сдано решений: 8
Существует алгоритм очень быстрой сортировки. Он берет произвольную последовательность чисел и упорядочивает их по возрастанию. Он работает быстрее в среднем, но существуют такие ряды чисел, где алгоритм выдает максимальное время выполнения. Наш знакомый Билли, увидев этот алгоритм стал кусать себе локти, после чего он понял, что не может так просто смотреть, как быстро сортируются последовательности чисел. На этот момент он поставил себе цель: написать такие тесты для этой программы, которые будут выполняться дольше всего.
Алгоритм:
procedure Sort(left,right:integer);
var
i,j:integer;
key:integer;
buf:integer;
begin
key:=a[(left+right)div 2]; {A - собственно, массив}
i:=left;
j:=right;
repeat
while a[i]<key do {первый while}
inc(i);
while key<a[j] do {второй while}
dec(j);
if i<=j then
begin
buf:=a[i];
a[i]:=a[j];
a[j]:=buf;
inc(i);
dec(j);
end;
until i>j;
if left<j then Sort(left,j);
if i<right then Sort(i,right)
end;
Итак, необходимо составить программу, создающую такую последовательность чисел, которая будет дольше всего обрабатываться данным алгоритмом. В данном случае это будет последовательных целых чисел от 1 до N. Время работы будем оценивать как количество операций сравнения элементов массива A (в первом и втором while).
Примечание. Если вариантов ответа несколько, вывести любой.
Формат входного файла input.txt
Единственное число - N (1<=N<=70000).
Формат выходного файла output.txt
Последовательность чисел (от 1 до N) при которых QuickSort будет работать дольше всего (без пробела на конце).
Пример входного файла
3
Пример выходного файла
1 3 2