OJ Board

the example:
1000 3
250 20 20
500 40 40
750 19 19
0 0

I don't understand why the answer is 998.03?
(v + 1/v - 0.1)*(1000/v) = 998.03
mean
v = 13.69455

then when the driver arrive the first light, he spent 18.255 sec.
(250/13.69455 = 18.255)
he should be stoped by the red light.

Isn't it?

I get the answer should be v=12.5, and the total fuel=998.40.

Der-Johng..

you're wrong. the driver can change the speed during his trip. that's why the output is correct.

BTW, can he change his speed while inside some segment (I mean not the whole path, but inter-light interval)?

I am not sure that v(t)=C is the best function for each case of length/time. I mean, are there cases when distribution of speed values through some lane is not uniform in optimal case?

I think it is allowed that he changes speed whenever he wants. However, due to the kind of cost function given in the problem, it only makes sense to change speed at certain positions. I don't exactly understand your second question, but I guess you think that allowing speed changes at every possible moment gives better results for some cases? I am quite sure it doesn't give better results.

Ok. For some segment of length S and travel time T (no lights inside) we have to find velocity function V(t), such that:

Integral(V(t)*dt, t=0..T) = S
Integral((V(t)+1/V(t)-0.1)*dt, t=0..T) -> min

Since fuel consumption depends only on velocity, we may think about distribution values of V(t) within time interval 0..T disregarding actual places of high and low speed, so we may assume that V(t) is monotonous function for simplicity.

For example, driving at speed of 3 during the whole interval will comsume some P units of fuel. But driving at speed 2 during most of the interval might be better if we meet desired time by accelerating to 5 velocity units at its end and still consume less than P units of fuel overally. Generally, this function will be continuous, but why only constant?

I don't claim that it is not a constant, but this fact is not quit obvious to me. Neither I am sure that judge's solution considers that if the answer is NO.

(in case you got e-mail notification; my thoughts weren't complete on what I wrote here)

Actually input data contains cases when r+g<30 || r+g>90 (tested with abort). Does r+g ought to be complete light cycle? Anyway this is not critical to my (still WA ) solution, and all other limits in the input are met. Take care if these limits are critical for your algorithm.

Ok, finally AC. Thanks to Adrian!

Some important things about this problem:

1) Output floor(v*100 + 0.5) / 100. I.e. perform manual rounding. "%.2lf" on itself doesn't work for some reason (that was my WA...). I don't know why. After 1100 solved problems only here, this is the first time I faced trouble with "%.Xlf" rounding of positive values. "-0.00" is famous problem, but there also seems to be some issue with positive values. Perhaps it's gcc-only issue (I code in VC6.0). I dunno...

2) Solution expects that the speed is constant between start, each traffic light and end-point. This is important because cases like these

1 0
2 0
3 0
...
19 0
0 0

Might have better answers then with any constant speed (see the integrals above). In these cases travel time is less then 1.0 and this does the damage.

Also, should there be some traffic lights in between for these cases, it will be really hard to consider them, since (S;T) will be some curve, and what's worse, we'll know only distribution, so it will be a family of curves.

Just assume that problem statement additionally says "speed is constant between any two adjacent points given in the input (0, d1, d2, .... dN, L)".

Hmm... still WA

Can somebody give me a critical test case,
or an output for the following (randomly generated) test case?

5531 23
156 45 6
835 29 22
864 11 38
1045 75 3
1105 16 29
1124 30 5
1126 64 16
1157 4 70
1560 2 82
1830 73 2
2163 13 76
2735 13 68
2743 55 17
2761 15 38
2774 50 1
2975 55 27
3842 36 20
4185 12 50
4276 52 4
4490 29 15
4565 19 30
4821 33 45
4954 65 12
0 0

My output is:
5581.46

ihi,

Try to find some easy to calculate lower and upper bounds for result and check if your real algorithm's result fits into this range.