kavinderrana121 Ответов: 1

Проблема светофора (модульная арифметика)


Автомобиль движется из точки А в Точку Б со скоростью v метров в секунду. Действие происходит на оси X. На расстоянии d метров от А находятся светофоры. Начиная с момента времени 0, в течение первых g секунд горит зеленый свет, затем в течение следующих r секунд горит красный свет, затем снова горит зеленый свет в течение g секунд и так далее.
Автомобиль может мгновенно ускоряться от 0 до v и наоборот, может мгновенно замедляться от v до 0. Считайте, что он проходит светофор на зеленый свет мгновенно. Если автомобиль приближается к светофору в тот момент, когда только что включился красный свет, он не успевает его проехать. Но если он приближается к светофору в тот момент, когда только что зажегся зеленый свет, он может двигаться. Автомобиль покидает точку а в момент времени 0.
Каково минимальное время для того, чтобы автомобиль добрался из пункта А в пункт Б, не нарушив правил дорожного движения?

Ввод

целые числа l, d, v, g, r (1 ≤ l, d, v, g, r ≤ 1000, d < l) — расстояние между А и в (в метрах), расстояние от А до светофора, скорость автомобиля, продолжительность зеленого света и продолжительность красного света.

Что я уже пробовал:

решение
if(g*v>d)
 ans = l/v   // i got it
else
 ceil(d/v/g+r)*(g+r)+(l-d)/v  // i am not getting Please help



Пример->предположим, что l=5 ,d=4,v=1,g=2 ,r=1
При t=0 автомобиль стартует с а
При t=2 свет становится красным, но автомобиль находится далеко от света, так что нет проблем продолжать движение
При t=3 свет снова становится зеленым в течение 2 секунд (до t=5)
При t=4 свет все еще зеленый, и мы достигаем света
Примечание-> Мы должны пересечь светофор, не волнуйтесь
При t=5 мы достигаем точки B
Но исправьте ans = 7, который не является минимальным, где я делаю неправильно ?
Вышеописанный подход был использован красным кодером, и я также включаю ссылку на его решение ниже.
Пожалуйста, помогите мне грустно, я пытаюсь найти правильную логику с 3-х дней.
Здесь вы-моя последняя надежда.

проблемная ссылкаПроблема - B - Codeforces[^]


решение red coder(такое же, как и выше упомянутое)
https://codeforces.com/contest/29/submission/31114802

Примечание-> выше принятое решение дает 7 в качестве вывода, но я думаю, что это должно быть 5.So это не может быть ошибкой, так как codeforces принял его.

Richard MacCutchan

На самом деле это не проблема программирования, а скорее вопрос математики.

kavinderrana121

Сэр пожалуйста помогите я прошу

Richard MacCutchan

Помочь в чем? Это математика, а не Программирование.

Christian Graus

Скажи своему учителю, что ты заблудился, чтобы он знал

1 Ответов

Рейтинг:
2

Stefan_Lang

Вы не можете различить случаи, когда светофор снова стал красным и зеленым несколько раз, прежде чем автомобиль прибыл. Автомобиль может двигаться на полной скорости все время, если светофор горит зеленым в момент прибытия автомобиля, даже если он периодически становился красным, когда автомобиль все еще приближался.

Кроме того, я не уверен, что выражение ceil(d/v/g+r) вы разместили оценки так, как вы ожидаете: во-первых, я подозреваю, что вы хотели разделить на (g+r), не делить на g а потом добавить r Во-вторых, порядок оценки (d/v/g) это не очевидно: это может быть ((d/v)/g) или (d/(v/g)) - а что вы имели в виду?

Я не потрудился проверить, даст ли любая из интерпретаций вашей формулы правильный результат. Вместо этого я укажу, как написать код, который непосредственно следует описанию проблемы и легко читается и понимается:

Шаг 1: Определите время, необходимое автомобилю, чтобы прибыть на светофор:

time_to_traffic_light = d/v;


Шаг 2: Определите количество зелено-красных циклов, прошедших до этого (время для одного цикла равно g+r):
lights_cycle_time = g + r;
number_of_cycles = floor(time_to_traffic_light/lights_cycle_time);


Шаг 3: Определите время, прошедшее с момента окончания последнего цикла:
current_cycle_time = time_to_traffic_light - number_of_cycles*lights_cycle_time;


Шаг 4: Проверьте, показывает ли светофор зеленый цвет:
if (current_cycle_time < g) /* use direct travel time */


Шаг 5: если отображается красный цвет, определите, как долго автомобиль должен ждать (до конца цикла):
else {
wait_time = lights_cycle_time - current_cycle_time;
/* now add this waiting time to the direct travel time */
}

Это может быть не самый короткий код, чтобы прийти к решению, но если вы не участвуете в конкурсе коротких кодов, это никогда не должно быть критерием. ;-)