410223: GYM103985 I Курьерский клуб

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Курьерский клубограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Петя и Вася устроились работать курьерами. В течение очередного рабочего дня им нужно доставить пакеты в n различных точек на прямой. Согласно внутренним правилам компании, доставка пакетов должна быть произведена строго в определённом порядке. Исходно Петя находится в точке с координатой s1, Вася находится в точке с координатой s2, а клиенты находятся в точках x1, x2, ..., xn в порядке требуемого посещения.

Ребята заранее договариваются, кто из них доставит пакет для какого из клиентов, после чего они действуют следующим образом. Когда пакет для i-го клиента доставлен, тот из ребят, кто доставляет пакет для (i + 1)-го клиента, отправляется в путь (это может быть как тот же из них, кто только что приехал в точку xi, так и другой). Тот из друзей, который не занят в доставке текущего пакета, стоит на месте.

Для связи друг с другом ребятам выдали рации. Рации довольно плохо работают на больших расстояниях, поэтому Петя и Вася хотят распределить заказы так, чтобы максимальное расстояние между ними в течение дня было как можно меньше. Помогите Пете и Васе минимизировать максимальное расстояние между ними, соблюдая все правила доставки.

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

В первой строке даны три целых числа n, s1, s2 (1 ≤ n ≤ 100 000, 0 ≤ s1, s2 ≤ 109) — количество точек доставки и начальные положения Пети и Васи.

Во второй строке расположены n целых чисел x1, x2, ..., xn — координаты клиентов (0 ≤ xi ≤ 109), указанные в том порядке, в котором следует выполнять доставку.

Гарантируется, что среди чисел s1, s2, x1, ..., xn нет двух одинаковых.

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

Выведите единственное целое число — минимальное возможное максимальное расстояние между ребятами в процессе доставки.

ПримерыВходные данные
2 0 10
5 6
Выходные данные
10
Входные данные
3 2 1
3 4 5
Выходные данные
1
Входные данные
1 4 5
2
Выходные данные
2
Примечание

В первом примере изначальное расстояние между курьерами равно 10. Эта величина и будет ответом, например, Петя может выполнить обе доставки, а Вася останется в начальной точке.

Во втором примере оптимально можно действовать, например, так: Петя доставляет пакет первому клиенту, Вася — второму и, наконец, Петя выполняет доставку пакета третьему клиенту. При таком порядке доставки расстояние между курьерами никогда не превзойдет 1.

В третьем примере есть только два возможных варианта: если доставку единственного пакета осуществляет Петя, то максимальное расстояние между ними будет 5 - 2 = 3. Если же пакет повезёт Вася, то максимальное расстояние составит 4 - 2 = 2. Последний способ является оптимальным.

加入题单

上一题 下一题 算法标签: