Задача A. Безопасное пересечение дороги
Условие
Пешеход переходит дорогу, состоящую из
K полос автомобильного движения. Он заметил
N автомобилей, каждый из
которых движется по своей полосе движения
wi и пересечет место перехода дороги через
bi секунд.
Пешеход может останавливаться между полосами дороги, а так же в начале и в конце пути. При этом,
если он уже начал переходить полосу, то он не может остановиться и пересечение очередной
полосы движения займет у него время
t. В начальный момент времени пешеход находится на
краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны.
Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть он идет прямо и не
поворачивает. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее
полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной
i, если момент времени
bi он оказался на полосе
wi. Но если он в это время находился между полосами или в начале и в конце
пути, то машина его не задевает.
Формат входного файла
Во входном файле содержатся числа
K, N, t, за которыми следует
N пар чисел
wi и
bi
Формат выходного файла
В выходной файл выведите единственное число - минимальное время, за которое переход может перейти дорогу.
В приведенном ниже примере пешеход начинает переходить полосу 1 в начальный момент времени и заканчивает
ее переходить через 10 секунд, как раз, когда по этой полосе проезжает машина 2. После этого он ждет
5 секунд и переходит вторую полосу.
Ограничения
0 ≤ N ≤ 2*105,
1 ≤ K ≤ 2*105,
1 ≤ t ≤ 103,
0 ≤ bi ≤ 109
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2 3 10
2 15
1 10
2 30
|
25
|
Задача B. Небезопасное пересечение дороги
Условие
Пешеход переходит дорогу, состоящую из K полос автомобильного движения. Он заметил N автомобилей, каждый из
которых движется по своей полосе движения wi и пересечет место перехода дороги через bi секунд.
Пешеход НЕ может останавливаться между полосами дороги. Он может остановиться только у одного из краев
дороги. Если же он находится на разграничителе полос, то он обязан переходить одну из соседних полос,
то есть двигается вперед или назад.
При этом, если он уже начал переходить полосу, то он не может остановиться и пересечение очередной
полосы движения займет у него время t.
В начальный момент времени пешеход находится на
краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны.
Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть, он идет или ждет на
одном из краев дороги,
или идет прямо, или назад. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее
полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной i, если момент времени
bi он оказался на полосе wi. Но если он в это время находился между полосами или в начале и в конце
пути, то машина его не задевает.
Формат входного файла
Во входном файле содержатся числа
K,
N,
t, за которыми следует
N пар чисел
wi и
bi
Формат выходного файла
В выходной файл выведите единственное число - минимальное время, за которое переход может перейти дорогу.
В приведенном ниже примере пешеход ждет десять секунд, после чего переходит обе полосы не останавливаясь.
Ограничения
0 ≤ N ≤ 2*105,
1 ≤ K,t ≤ 100,
0 ≤ bi ≤ 104,
1 ≤ wi ≤ K
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2 3 10
2 15
1 10
2 30
|
30
|
Задача C. Третье место
Условие
В олимпиаде приняли участие
N школьников. Вам известно количество баллов, которое набрал
каждый из них. Сколько баллов получил участник, занявший третье c конца место? Если несколько участников
набрали одинаковое количество баллов, то они все равно некоторым образом распределены по местам,
то есть невозможно разделить место.
Формат входного файла
Во входном файле содержится число
N, за которым следует
N чисел
ai - баллы, набранные участниками.
Формат выходного файла
В выходной файл выведите единственное число - количество баллов, которое набрал участник, занявший
третье с конца место.
Ограничения
3 ≤ N ≤ 100000,
1 ≤ ai ≤ 30000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4
7 2 1 2
|
2
|
| 2 |
4
1 2 3 4
|
3
|
Задача D. Астероидное поле
Условие
В плоской галактике с недавнего времени образовалось слишком много астероидов
и они стали мешать транспортным кораблям передвигаться.
Их приходится облетать, а на изменение курса требуется очень много топлива.
Вам предлагается написать программу, которая по заданной плоской астронавигационной
карте с известными координатами астероидов и положением транспортного корабля
определит какой-либо прямой курс, на котором кораблю не встретится ни одного астероида
Каждый астероид имеет форму круга и задается координатами центра xi yi и радиусом ri.
Размерами транспортного корабля можно пренебречь, однако если на проложенном курсе
корабль коснется астероида — он разобьется.
Формат входного файла
Во входном файле сначала содержаться начальные координаты корабля
x0, y0,
затем число
N — количество астероидов.
Далее следуют
N троек чисел
xi, yi, ri — описание
i-го астероида.
В начальном положении корабль не соприкасается ни с одним из астероидов.
Формат выходного файла
В выходном файле должно содержаться два числа
x1, y1 — координаты точки,
на которую кораблю следует взять курс, чтобы не врезаться в астероид.
Гарантируется, что такая точка существует, если таких точек несколько,
выведите любую из них. Координаты
x1, y1 должны отличаться от
x0, y0.
Ответ выведите с точностью до пятого знака после десятичной точки.
Ограничения
0 ≤ N ≤ 100,
−10000 ≤ xi, yi, zi ≤ 10000,
1 ≤ ri ≤ 10000.
Все координаты — вещественные числа.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
0.0 0.0
2
1.0 1.0 1.0
1.0 -1.0 1.0
|
-1.0 0.0
|
