TopCoder problem "ThreeBuses" used in SRM 333 (Division I Level Three)

Problem Statement


Little Johnny woke up late. Now he only has timeLeft minutes to get to school.

Sadly, Johnny doesn't have a direct connection to school. He has to use three specific bus lines (one after another) to get there.

The buses in Johnny's town don't have a fixed schedule. Instead, each bus line is assigned some non-negative integer W. If you arrive at a bus stop of a bus line, you know that the time you will have to wait is a random variable drawn from the interval [0,W] with uniform probability. Note that from a passenger's point of view the number W corresponds to the maximum waiting time.

(You can imagine this in a real life setting as follows: If you stand on a bus stop of a line that has a positive W, precisely every W minutes a bus comes by, you just don't know the offset. If you stand on a bus stop of a line that has W=0, there is always a bus ready to take you.)

You are given two int[]s wait and travel, and an int timeLeft. The int[] wait specifies the value W (the maximum waiting time) for each of the bus lines Johnny has to take. The int[] travel specifies how long Johnny rides each of the three buses. Write a method that computes the probability that Johnny will arrive to school on time.



Parameters:int[], int[], int
Method signature:double getProbability(int[] wait, int[] travel, int timeLeft)
(be sure your method is public)


-Time is continuous, e.g., the bus can arrive 0.47 minutes after Johnny comes to a bus stop.
-Your return value must have an absolute or relative error less than 1e-9.


-wait will contain exactly 3 elements.
-Each element of wait will be between 0 and 100,000, inclusive.
-travel will contain exactly 3 elements.
-Each element of travel will be between 1 and 100,000, inclusive.
-timeLeft will be between 1 and 600,000, inclusive.


{0, 0, 0}
{10, 15, 10}
Returns: 1.0
Johnny won't have to wait for the buses. He can be sure his trip will take exactly 35 minutes, and 35 is not more than 47.
{0, 0, 0}
{10, 15, 10}
Returns: 1.0
The same setting as before. With 35 minutes left, Johnny will arrive exactly on time.
{1, 100, 1}
{10, 10, 10}
Returns: 0.21
This time Johnny may get into trouble. It all depends on whether the second bus arrives soon enough. A rough estimate: if the second bus arrives in less then 20 minutes, Johnny will surely make it. Thus the exact probability is slightly over 20/100.
{100, 100, 70}
{1, 1, 1}
Returns: 0.020281904761904737
Johnny must be really lucky to make it.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , Mike Mirzayanov

Problem categories:

Geometry, Math