Connection Status:
Competition Arena > ThreeBuses

ThreeBuses

SRM 333 · 2007-01-04 · by misof

SRM 333 · 2007-01-04 · by misof · Geometry, Math
Class Name: ThreeBuses
Return Type: double
Method Name: getProbability
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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, 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.

1)
{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.

2)
{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.

3)
{100, 100, 70}
{1, 1, 1}
47
Returns: 0.020281904761904737

Johnny must be really lucky to make it.

4)
{4,10,7}
{1,1,1}
1
Returns: 0.0

Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ThreeBuses with a public method double getProbability(vector<int> wait, vector<int> travel, int timeLeft) · 97 test cases · 2 s / 256 MB per case

Submitting as anonymous