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.
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.
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)".
) solution, and all other limits in the input are met. Take care if these limits are critical for your algorithm.