CODEWITHSUNDEEP
algorithmmodular-arithmetic
akacodes121
akacodes121

Reputation: 129

modular arithmetic puzzle codeforces

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.

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

Accepted solution link of red coder

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.

Upvotes: 0

Views: 172

Answers (1)

maraca
maraca

Reputation: 8773

Yes you are right, the answer should be 5.

The condition g * v > d doesn't make any sense. It just checks if you can pass the traffic light during the first green phase. Actually it should be ((d + v - 1) / v) % (g + r) < g. First we calculate on which second we pass the traffic light with (d + v - 1) / v (integer division) which is the same as ceil(d / v) if we are using floating point numbers. Then with the modulo we calculate where in the green red cycle we pass the traffic light. If the result is < g we passed it when it was green and the solution is (double)l / v.

You could use the same technique with the modulo as above to get the number of seconds we have to stop at the traffic light and then add the times from start to the traffic light (whole seconds) and the time from the traffic light to the destination. Or we can calculate the number of seconds we need until the end of the green red cycle when passing the traffic light. This is what you did, but you are missing braces, so for floating point numbers we could use your formula with additional braces:
ceil(d / v / (g + r)) * (g + r) + (l - d) / v.

Upvotes: 0

Related Questions