--->
55 задач
<---
Источники
Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели \(N\) различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.
Петя предположил, что между цивилизациями \(A\) и \(B\) происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.
Теперь для выполнения своих исследований Петя хочет найти такую пару цивилизаций, культурный обмен между которыми имел место на протяжении наименьшего ненулевого промежутка времени. Помогите ему!
В первой строке вводится число \(N\) – количество цивилизаций, культура которых интересует Петю (1\( \le\)N\( \le\)100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа \(S_i\) и \(E_i\) – год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят \(10^9\) по абсолютной величине, \(S_i\) < \(E_i\).
Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.
3 -600 -400 -450 -300 -400 -50
1 2
2 10 20 15 21
1 2
1 77777 77778
0
Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.
Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.
В первой строке вводится число n - количество селений (1 <= \(n\) <= 100000). Вторая строка содержит n различных целых чисел, \(i\)-е из этих чисел задает расстояние от начала дороги до \(i\)-го селения. В третьей строке входных данных задается число \(m\) - количество бомбоубежищ (1 <= \(m\) <= 100000). Четвертая строка содержит \(m\) различных целых чисел, \(i\)-е из этих чисел задает расстояние от начала дороги до \(i\)-го бомбоубежища. Все расстояния положительны и не превышают \(10^9\). Селение и убежище могут располагаться в одной точке.
Выведите \(n\) чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до \(m\) в том порядке, в котором они заданы во входных данных.
4 1 2 6 10 2 7 3
2 2 1 1
На числовой прямой окрасили \(N\) отрезков. Известны координаты левого и правого концов каждого отрезка (\(L_i\) и \(R_i\)). Найти длину окрашенной части числовой прямой.
В первой строке находится число \(N\), в следующих \(N\) строках - пары \(L_i\) и \(R_i\). \(L_i\) и \(R_i\) - целые, -1 000 000 000 <= \(L_i\) <= \(R_i\) <= 1 000 000 000, 1 <= \(N\) <= 15 000
Вывести одно число - длину окрашенной части прямой.
1 10 20
10
1 10 10
0
2 10 20 20 40
30
Ввод 1 Ввод 2 4 4 1 1 1 2 1 4 5 8 Вывод 1 Вывод 2 4 16
Для сортировки последовательности чисел широко используется быстрая сортировка - QuickSort. Далее приведена программа, которая сортирует массив a, используя этот алгоритм.
var
a : array [1..N] of integer;
procedure QSort(left, right : integer);
var
i, j : integer;
key : integer;
buf : integer;
begin
key := a[(left + right) div 2];
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
QSort(left, j);
if i < right then
QSort(i, right);
end;
begin
...
QSort(1, N);
end.
Хотя QuickSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Оценивать время работы алгоритма будем количеством сравнений с элементами массива (то есть суммарным количеством сравнений в первом и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.
В первой строке находится единственное число N.
Ограничения: 1 <= N <= 70 000.
Вывести перестановку чисел от 1 до N, на которой быстрая сортировка выполнит максимальное число сравнений. Если таких перестановок несколько, вывести любую из них.
1
1
3
1 3 2