0
$\begingroup$

I was unable to solve this problem from a past programming contest I did. Since this is more of a math question than programming, I thought it best to ask it here instead of over at stackoverflow.

In the explanation on the samples (see Note at the bottom of that link), I do not know how they are getting 510.5 for the time that the second trolleybus catches up with the first.

I do not have any physics background, but the physics formulas I know so far are:

dist = initialVelocity * tm + .5 * acceleration * (tm*tm) time = sqrt(dist / (.5 * acceleration)) vel = initialVelocity + tm * acceleration 

So for the first example, trolley 1's maximum speed is 10. Max acceleration for all trolleys is 10. But I don't know how to figure out when trolley 1 and trolley 2 meet.

The problem analyses for this problem is here. (see 167A at that link). But I do not understand how they are coming up with those formulas.

Thanks for any help.

2 Answers 2

1

You don't need to find where two bus meet, try to find each bus arrival time $a_i$ if each bus can ride in his own track, then the arrival time in the complete problem is \max_{j<=i} a_j.

For finding the arrival bus in the simpler problem, you need to consider two subcase: the bus keep accellerating for the whole time or not?

  • 0
    The first thing to note is that you must always go at maximum velocity OR maximum accelleration. You go at max accelleration until max_a * t = max_v (look at your third formula), and after that time you go at costant speed. So the first bus for the first second(10*x=10 -> x=1) he increase speed, and in this time he travel 0.5*10*1*1=5 meters (using your first formula). The second part he travel at costant speed 10, but he have already done 5 meters, so (10000-5)/10=999.5 seconds. Plus 1s for the accelleration part = 1000.5.2012-04-19
1

carlop has shown that you don't need to calculate when two buses meet, but you can if you want. Your equation for dist is not correct: initialVelocity is specified as 0, so you can delete that term, and once the bus hits maximum speed it stops accelerating. tm has to be counted from the departure time. $dist=\begin {cases} \frac 12 a\cdot tm^2 & tm \lt maxV/a \\ \frac 12 a (maxV/a)^2 + maxV(tm-maxV/a) & else \end {cases}$

Then you can solve for when the dist of one bus equal that of the previous one. If it is not in the range of the length of the run, they don't meet.

I used a for acceleration and maxV for maxVelocity to make the equation narrower

  • 0
    @dcp: maxV/a is the time to accelerate to maxV. That is the (maxV/a)^2 part of the first term, so the time at maxV is after that.2012-04-19