交通灯问题（模块化算术） [英] Traffic light problem (modular arithmatic)

问题描述

汽车以每秒v米的速度从A点移动到B点。动作发生在X轴上。距离A d米处有红绿灯。从时间0开始，对于第一个g秒，绿灯亮，然后在接下来的r秒内红灯亮，然后再次绿灯亮g秒，依此类推。

汽车可以立即从0加速到v，反之亦然，可以立即从v减速到0。考虑到它立即通过绿灯处的红绿灯。如果汽车在红灯刚刚开启时接近红绿灯，则没有时间通过​​。但是，如果它在绿灯刚刚打开的时刻接近红绿灯，它就会移动。当时汽车离开了A点。

汽车在没有违反交通规则的情况下从A点到B点的最短时间是多少？



输入



整数l，d，v，g，r（1≤l，d，v，g ，r≤1000，d


我尝试过：



解决方案

 if（g * v> d）
 ans = l / v //我得到了
其他
 ceil（d / v / g + r）*（g + r ）+（ld）/ v //我没有得到请帮助

示例 - >假设l = 5，d = 4，v = 1，g = 2，r = 1

在t = 0时，汽车从A开始
在t = 2时变亮红色，但车远离光线所以没有问题继续移动

在t = 3时，灯再次变为绿色，持续2秒（直到t = 5）

在t = 4光仍然是绿色和我们光线充足

注意 - >我们已经越过红绿灯了不用担心

在t = 5时我们到达B点

上面的方法被红色编码器使用，我也在下面包括他的解决方案链接。

请帮助我感到难过我想从中找到正确的逻辑3天。

这里你的人是我最后的希望。



问题链接 问题 - B - 代码强制 [ ^ ]





红色编码器解决方案（与上述相同）

https://codeforces.com/contest/29/submission/31114802



注意 - >以上接受的解决方案给出7作为输出但是我认为应该是5.因为代码强制接受它所以这不是错误。

解决方案

你无法区分在汽车到达之前交通信号灯再次变为红色和绿色的情况。如果在车辆到达时交通信号灯是绿色的，车辆可以全程全速行驶，即使在车辆仍在接近时间歇性地变红也是如此。



另外，我不确定您发布的表达式 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）：

<前一个=c ++> 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） / *  使用直接旅行时间* /  

步骤5：如果显示红色，确定汽车必须等待多长时间（直到循环结束）：

  else  {
 wait_time = lights_cycle_time  -  current_cycle_time; 
  / *  现在将此等待时间添加到直接旅行时间* /  
 } 

这可能不是达到解决方案的最短代码，但除非您参加短代码竞赛，否则这绝不应成为标准。 ; - ）

A car moves from point A to point B at speed v meters per second. The action takes place on the X-axis. At the distance d meters from A there are traffic lights. Starting from time 0, for the first g seconds the green light is on, then for the following r seconds the red light is on, then again the green light is on for the g seconds, and so on.
The car can be instantly accelerated from 0 to v and vice versa, can instantly slow down from the v to 0. Consider that it passes the traffic lights at the green light instantly. If the car approaches the traffic lights at the moment when the red light has just turned on, it doesn't have time to pass it. But if it approaches the traffic lights at the moment when the green light has just turned on, it can move. The car leaves point A at the time 0.
What is the minimum time for the car to get from point A to point B without breaking the traffic rules?

Input

integers l, d, v, g, r (1 ≤ l, d, v, g, r ≤ 1000, d < l) — the distance between A and B (in meters), the distance from A to the traffic lights, car's speed, the duration of green light and the duration of red light.

What I have tried:

solution

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

Example->suppose l=5 ,d=4,v=1,g=2 ,r=1
At t=0 car starts from A
At t=2 light become red but car is far away from light so no problem keep moving
At t=3 light becomes green again for 2 sec (till t=5)
At t=4 light is green still and we reach at light
Note-> we have cross the traffic light don't worry
At t=5 we reach at point B
But correct ans = 7 which is not minimum where I am doing wrong ?
Above approach was used by a red coder and I am including the his solution link below also.
Please help I am feeling sad I am trying to find the correct logic from 3 days.
Here you people are my last hope.

problem linkProblem - B - Codeforces[^]


red coder solution(same as above mentioned)
https://codeforces.com/contest/29/submission/31114802

Note-> the above accepted solution giving 7 as output But I think it should be 5.So this can't be wrong since codeforces accepted it.

解决方案

You fail to distinguish the cases where the traffic light has turned red and green again a few times before the car arrives. The car may travel at full speed the whole time if the traffic light is green at the time the car arrives, even if it has turned red intermittently while the car was still approaching.

Also, I'm not sure that the expression ceil(d/v/g+r) you posted evaluates in the way you expect: for one, I suspect you meant to divide by (g+r), not divide by g and then add r. Second, the order of evaluation of (d/v/g) is not obvious: it could be ((d/v)/g) or (d/(v/g)) - which did you intend?

I did not bother to check if either interpretation of your formula would give you the correct result. Instead I will point out how to write code that directly follows the description to the problem and is easy to read and understand:

Step 1: determine the time it takes the car to arrive at the traffic light:

time_to_traffic_light = d/v;

Step 2: determine the number of green-red cycles that have passed before then (the time for one cycle is g+r):

lights_cycle_time = g + r;
number_of_cycles = floor(time_to_traffic_light/lights_cycle_time);

Step 3: determine the time that has passed since the end of the last cycle:

current_cycle_time = time_to_traffic_light - number_of_cycles*lights_cycle_time;

Step 4: check whether the traffic light shows green:

if (current_cycle_time < g) /* use direct travel time */

Step 5: if showing red, determine for how long the car must wait (until the end of the cycle):

else {
wait_time = lights_cycle_time - current_cycle_time;
/* now add this waiting time to the direct travel time */
}

This may not be the shortest code to arrive at the solution, but unless you're participating in a short-code-contest this should never be a criterion. ;-)

这篇关于交通灯问题（模块化算术）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！