Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
fonari
Бизнесмен А создал для своей жены-лыжницы и соседей по коттеджному посёлку лыжню. Проложена она по дорожкам лесопарка и представляет собой N-звенную замкнутую ломаную без самопересечений. Ежедневно специально нанятый сотрудник прокатывает трассу снегоходом и нарезает лыжни.
Живущий в том же посёлке бизнесмен В тоже решил вложиться в лыжную трассу: сделать её освещённой. Выбрал надёжные и экономичные фонари, которые светят на R метров. Лыжня проходит по густому еловому лесу, поэтому фонарь освещает только ту лыжню, на которой стоит: не более R метров в каждую сторону. Если же фонарь стоит на повороте трассы, он освещает по R метров каждой из двух лыжней.
Разработайте программу, определяющую минимальное количество фонарей, необходимое для полного освещения трассы.
Входные данные. В первой строке - разделённые пробелом натуральные числа N и R. N не меньше 3 и не больше 100. В следующих N строках - длины звеньев ломаной в порядке их расположения на трассе, натуральные числа разумной величины.
Выходные данные. Натуральное число - минимальное количество необходимых фонарей.
Для отправки решений необходимо выполнить вход.
|