e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Məsələlər

Анти-QuickSort

Анти-QuickSort

Для сортировки последовательности чисел широко используется быстрая сортировка – QSort. Ниже приведена программа, которая сортирует массив a, используя данный алгоритм.

var a : array [1..N] of integer;

procedure QSort(left, right : integer);

var m, i, j, t : integer;

begin

m := a[(left+right) div 2];

i := left; j := right;

repeat

while a[i] < m do inc(i); {первый while}

while a[j] > m do dec(j); {второй while}

if i <= j then

begin

t := a[i]; a[i] := a[j]; a[j] := t;

inc(i); dec(j);

end;

until i > j;

if j > left then QSort(left, j);

if i < right then QSort(i, right);

end;

begin

...

QSort(1, N);

end.

Хотя QSort является самой быстрой сортировкий в среднем, существуют тесты, на которых она работает очень долго. Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.

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

В первой строке находится единственное число N (1N70000).

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

Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
1
Çıxış verilənləri #1
X