---> 55 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Заданы годы существования цивилизаций. Необходимо найти пару цивилизаций, которые существовали одновременно наибольшее количество лет.

Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели $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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все 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 
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На числовой прямой окрасили $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.0 second;
ограничение по памяти на тест
64 megabytes
Даны N натуральных чисел. Найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза.
Ограничения: 1 <= N <= 10 000, значения исходных чисел от 1 до 1 000 000 000.
Ввод: В первой строке находится число N, в следующих N строках - по одному натуральному числу.
Вывод: Вывести одно число.
Примеры
Ввод 1    Ввод 2
4         4
1         1
1         2
1         4
5         8
Вывод 1   Вывод 2
4         16
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Для сортировки последовательности чисел широко используется быстрая сортировка - 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 

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест