Задача B. Светофор (Школьный этап 2015 - 2016)
Задачу добавил: alef
Успешно сдано решений: 420
Товарищ 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 единиц времени) зелёный сигнал включился ещё раз.