Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Бинарный поиск

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

04/07/2011 | Лето 2011 - дорешивание (13H) |

20/07/2011 | Лето 2011 - 13 (H) |

*Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

A long straight road connects two villages. Along the road, `N` messengers are stationed and, when
needed, they exchange messages using mostly their legs, but also their vocal cords and ears.
The first messenger (the closest to the first village) has a radio-receiver which he uses to keep track of
current ongoings in the country. When he finds out who has been evicted from whichever reality show
is currently popular, he starts running as fast as he can to share the unfortunate (or fortunate) news
with everyone else. While running, he shouts the name of the evicted person so that any fellow
messengers that are close enough can hear him. Meanwhile, the remaining messengers do not merely sit
and wait, but also run themselves, all with the selfless goal of sharing the news with everyone as fast as
possible.

The running and shouting proceeds as follows:

1. Each of the messengers may run **whenever, in either direction**, at a speed of **at most 1 unit
per second**, or may decide not to run at all and stand still.

2. All messengers that know the news shout it at all times. One messenger **can hear** another
messenger shouting (and learn the news) if the **distance** between them is **at most `K` units**.

Write a program that, given the initial locations of the messengers, determines the **least amount of
time** (in seconds) needed for **all messengers** to learn the news. The location of every messenger is
given with a positive real number – the distance from the first village. As mentioned above, initially
only the first messenger knows the news.

The first line contains the real number `K` (`0\ ≤\ K\ ≤\ 1000000`), the largest distance at which two messengers
can hear each other. The second line contains the integer `N` (`1\ ≤\ N\ ≤\ 100000`), the number of messengers.
Each of the following `N` lines contains one real number `D` (`0\ ≤\ D\ ≤\ 1000000000`), the distance of one messenger
from the first village. The distances will be sorted **in ascending order**. It is possible for multiple
messengers to be at the same location.

Output a real number, the least time for all messengers to learn the news. Your output will be accepted
if it differs from the official output by no more than `±0.001`.

Sample Input 1

3.000 2 0.000 6.000

Sample Output 1

1.500

Sample Input 2

2.000 4 0.000 4.000 4.000 8.000

Sample Output 2

1.000