Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача B. Светофор (Школьный этап 2015 - 2016)

Задачу добавил: alef

Успешно сдано решений: 411

ограничение по времени на тест - 2 секунды
ограничение по памяти на тест - 256 мегабайт
ввод - стандартный ввод или input.txt
вывод -стандартный вывод или output.txt


Товарищ A шёл к месту встречи привычным маршрутом. Ему оставалось дойти до конца квартала и перейти дорогу. Зелёный свет для пешеходов на этом переходе включается только при нажатии специальной кнопки. Однако не нужно думать, что достаточно нажать кнопку, и зелёный свет мгновенно загорится. В светофоре установлено специальное реле, которое не позволяет включать зелёный сигнал слишком часто. Так, если для пешеходов включился красный свет, он будет гореть не менее r секунд.

Алгоритм работы светофора можно описать следующим образом.

  • Если нажать кнопку включения зелёного сигнала в тот момент, когда зелёный сигнал уже включен, нажатие кнопки будет проигнорировано;
  • Если нажать кнопку включения зелёного сигнала в тот момент, когда красный сигнал горит r или более секунд, то спустя d секунд включится зелёный сигнал;
  • Если нажать кнопку включения зелёного сигнала в тот момент, когда красный сигнал горит менее r секунд, то зелёный сигнал включится не ранее, чем пройдёт r секунд от момента включения красного сигнала, и не ранее, чем пройдёт d секунд после нажатия кнопки;
  • Повторное нажатие кнопки включения зелёного сигнала в тот момент, когда горит красный сигнал, будет проигнорировано.

Зелёный сигнал всегда горит ровно g секунд, после чего автоматически включается красный сигнал.

Известно, что в момент времени t0 = 0 на светофоре включился красный сигнал. Также известно, что кнопку включения зелёного сигнала нажимали n раз в моменты времени t1 < t2 < ... < tn. Ваша задача — определить, сколько раз на светофоре включался зелёный свет.

Заметим, что пример является неотъемлемой частью условия, в связи с чем настоятельно рекомендуем внимательно прочесть описание примера ниже.

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

В первой строке через пробел содержатся целые числа r, g, d (1 ≤ r, g, d ≤ 1000) — минимальное время, в течение которого горит красный сигнал; время, в течение которого горит зелёный сигнал, и время, которое требуется на переключение между красным и зелёным сигналом.

Во второй строке содержится единственное целое число n (1 ≤ n ≤ 1000).

В третьей строке через пробел содержатся числа t1, t2, ..., tn (0 ≤ t1 < t2 < ... < tn < 106) — моменты времени, в которые нажимали кнопку включения зелёного сигнала.

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

Выведите единственное целое число — количество раз, которые на светофоре включался зелёный свет.

Примеры тестов

Входные данные
60 30 10
9
100 110 135 145 190 285 310 320 325
Выходные данные
4
Примечание

Поясним приведённый пример.

В момент времени t0 = 0 включился красный сигнал светофора. Первое нажатие на кнопку включения зелёного сигнала произошло в t1 = 100. Поскольку к этому моменту красный сигнал горел уже 100 единиц времени, что больше r = 60, то спустя d = 10 единиц времени включился зелёный сигнал. После этого с момента 110 до момента 140 единиц времени горел зелёный сигнал светофора (и это было его первое включение). Поэтому нажатия на кнопку в момент 110 и в момент 135 были проигнорированы.

Далее, в момент 140 загорелся красный сигнал, а в момент 145 была нажата кнопка включения зелёного сигнала. К моменту нажатия на кнопку красный сигнал горел всего 5 единиц времени, а переключение на зелёный сигнал возможно не ранее, чем по истечении 60 единиц времени. Следовательно, зелёный сигнал не мог включиться ранее, чем в момент 200. Разумеется, зелёный сигнал также не мог включиться ранее, чем по истечении 10 единиц времени с момента нажатия кнопки, но к этому моменту (155) ещё не прошло достаточно времени для переключения с красного сигнала. Таким образом, второй раз зелёный сигнал горел с момента 200 по момент 230. Заметим, что нажатие кнопки в момент 190 является повторным нажатием при красном сигнале и потому игнорируется.

Следующее нажатие на кнопку происходит в момент времени 285. К этому моменту красный сигнал горел уже 55 единиц времени. Теоретически он мог бы включиться в момент времени 290, но после нажатия на кнопку должно пройти не менее 10 единиц времени — поэтому в третий раз зелёный свет загорелся в момент времени 295 и продолжал гореть до момента 325.

В момент 325 (когда зелёный сигнал сменялся красным) кнопку включения зелёного сигнала вновь нажали. Поэтому в момент 385 (спустя 60 единиц времени) зелёный сигнал включился ещё раз.

Сдать задачу

Задать вопрос жюри по этой задаче