Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Медленная сортировка

Задачу добавил: 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

Сдать задачу

Задать вопрос жюри по этой задаче