ThreeBuses | Topcoder Archive

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.

Definition

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

Notes

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.

Constraints

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.

Examples

```
{0, 0, 0}
```
```
{10, 15, 10}
```
```
47
```
```
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}
```
```
35
```
```
Returns: 1.0
```
The same setting as before. With 35 minutes left, Johnny will arrive exactly on time.
```
{1, 100, 1}
```
```
{10, 10, 10}
```
```
52
```
```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.