Statistics

Problem Statement for "ThreeBuses"

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

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

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

  3. {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.

  4. {100, 100, 70}

    {1, 1, 1}

    47

    Returns: 0.020281904761904737

    Johnny must be really lucky to make it.

  5. {4,10,7}

    {1,1,1}

    1

    Returns: 0.0

  6. {4,10,7}

    {1,1,1}

    2

    Returns: 0.0

  7. {4,10,7}

    {1,1,1}

    3

    Returns: 0.0

  8. {4,10,7}

    {1,1,1}

    4

    Returns: 5.952380952380952E-4

  9. {4,10,7}

    {1,1,1}

    5

    Returns: 0.004761904761904762

  10. {4,10,7}

    {1,1,1}

    6

    Returns: 0.016071428571428573

  11. {4,10,7}

    {1,1,1}

    7

    Returns: 0.03809523809523809

  12. {4,10,7}

    {1,1,1}

    8

    Returns: 0.07380952380952381

  13. {4,10,7}

    {1,1,1}

    9

    Returns: 0.12380952380952379

  14. {4,10,7}

    {1,1,1}

    10

    Returns: 0.1880952380952381

  15. {4,10,7}

    {1,1,1}

    11

    Returns: 0.2660714285714286

  16. {4,10,7}

    {1,1,1}

    12

    Returns: 0.3547619047619048

  17. {4,10,7}

    {1,1,1}

    13

    Returns: 0.45059523809523816

  18. {4,10,7}

    {1,1,1}

    14

    Returns: 0.549404761904762

  19. {4,10,7}

    {1,1,1}

    15

    Returns: 0.6452380952380954

  20. {4,10,7}

    {1,1,1}

    16

    Returns: 0.7339285714285715

  21. {4,10,7}

    {1,1,1}

    17

    Returns: 0.8119047619047619

  22. {4,10,7}

    {1,1,1}

    18

    Returns: 0.8761904761904763

  23. {4,10,7}

    {1,1,1}

    19

    Returns: 0.9261904761904761

  24. {4,10,7}

    {1,1,1}

    20

    Returns: 0.9619047619047618

  25. {4,10,7}

    {1,1,1}

    21

    Returns: 0.9839285714285712

  26. {4,10,7}

    {1,1,1}

    22

    Returns: 0.995238095238095

  27. {4,10,7}

    {1,1,1}

    23

    Returns: 0.9994047619047619

  28. {4,10,7}

    {1,1,1}

    24

    Returns: 1.0

  29. {4,10,7}

    {1,1,1}

    25

    Returns: 1.0

  30. {97000,73000,84700}

    {31200,72500,4700}

    108400

    Returns: 0.0

  31. {97000,73000,84700}

    {31200,72500,4700}

    363100

    Returns: 1.0

  32. {97000,73000,84700}

    {31200,72500,4700}

    110000

    Returns: 1.138231742537708E-6

  33. {97000,73000,84700}

    {31200,72500,4700}

    108500

    Returns: 2.7788860901800697E-10

  34. {97000,73000,84700}

    {31200,72500,4700}

    363000

    Returns: 0.9999999997221184

  35. {97000,73000,84700}

    {31200,72500,4700}

    182000

    Returns: 0.11079086486748652

  36. {97000,73000,84700}

    {31200,72500,4700}

    194000

    Returns: 0.17374176928710658

  37. {97000,73000,84700}

    {31200,72500,4700}

    210000

    Returns: 0.2835726246037114

  38. {97000,73000,84700}

    {31200,72500,4700}

    240000

    Returns: 0.5372445474231571

  39. {97000,73000,84700}

    {31200,72500,4700}

    268000

    Returns: 0.7643041560848166

  40. {97000,73000,84700}

    {31200,72500,4700}

    278300

    Returns: 0.8310000530201489

  41. {97000,73000,84700}

    {31200,72500,4700}

    278400

    Returns: 0.8315873286341242

  42. {97000,73000,84700}

    {31200,72500,4700}

    278500

    Returns: 0.8321733873738844

  43. {97000,73000,84700}

    {31200,72500,4700}

    310000

    Returns: 0.9583941587027168

  44. {97000,73000,84700}

    {31200,72500,4700}

    108555

    Returns: 1.0348224439069298E-9

  45. {0,0,0}

    {3,4,5}

    11

    Returns: 0.0

  46. {1300,0,0}

    {2,2,2}

    576000

    Returns: 1.0

  47. {0,1470,0}

    {20000,2,2}

    47

    Returns: 0.0

  48. {0,0,1470}

    {2,2,2}

    47

    Returns: 0.027891156462585033

  49. {0,0,14700}

    {20000,20000,20000}

    74699

    Returns: 0.9999319727891156

  50. {1, 1, 1}

    {1, 1, 1}

    4

    Returns: 0.16666666666666666

  51. {2, 2, 2}

    {1, 1, 1}

    5

    Returns: 0.16666666666666669

  52. {4321,0,3173}

    {1,1,1}

    3

    Returns: 0.0

  53. {4321,0,3173}

    {1,1,1}

    7

    Returns: 5.834929976828763E-7

  54. {4321,0,3173}

    {1,1,1}

    2900

    Returns: 0.306064286486893

  55. {4321,0,3173}

    {1,1,1}

    3176

    Returns: 0.3671603795417727

  56. {4321,3173,0}

    {1,1,1}

    3420

    Returns: 0.4236287896320296

  57. {43210,31730,0}

    {1,1,1}

    43212

    Returns: 0.6328164776672066

  58. {43210,31730,0}

    {1,1,1}

    51500

    Returns: 0.7995795462510464

  59. {0,43210,31730}

    {1,1,1}

    74000

    Returns: 0.9996757058970647

  60. {100000,100000,100000}

    {100000,100000,100000}

    300000

    Returns: 0.0

  61. {89405,59302,77361}

    {56684,87363,21865}

    211599

    Returns: 0.038750155606863484

  62. {72753,34929,17514}

    {89822,66339,37000}

    278926

    Returns: 0.8101835174696417

  63. {61685,58761,90541}

    {24176,76041,89533}

    80845

    Returns: 0.0

  64. {46011,92612,31856}

    {14687,73451,29343}

    53508

    Returns: 0.0

  65. {20352,81660,95211}

    {37568,68773,74917}

    189893

    Returns: 6.781600141343863E-4

  66. {58482,24593,96845}

    {59046,59522,16704}

    181685

    Returns: 0.10720369834524436

  67. {28206,79169,47842}

    {17702,40276,40728}

    136611

    Returns: 0.08354008553831994

  68. {44128,58072,1558}

    {17950,78496,58879}

    181446

    Returns: 0.1253451454565586

  69. {79758,16033,47566}

    {27921,38,70588}

    75569

    Returns: 0.0

  70. {94277,47850,15363}

    {55104,254,14554}

    11603

    Returns: 0.0

  71. {59775,31257,93174}

    {15793,12772,68827}

    217980

    Returns: 0.7859939081949852

  72. {78513,37366,28649}

    {50452,95438,30206}

    316844

    Returns: 0.9998928982662924

  73. {76279,16897,28849}

    {58382,32929,76414}

    263751

    Returns: 0.9246077149484246

  74. {32967,74813,79603}

    {55055,50474,94965}

    34168

    Returns: 0.0

  75. {50728,37330,54464}

    {12848,68587,75449}

    205980

    Returns: 0.188604746510523

  76. {9170,46621,15412}

    {15494,83987,44060}

    2867

    Returns: 0.0

  77. {81770,2078,36692}

    {85860,18974,91007}

    260854

    Returns: 0.558004158004158

  78. {51902,69766,86167}

    {12680,46925,93581}

    198611

    Returns: 0.05006851005720723

  79. {97398,18704,8049}

    {75937,56033,62513}

    292407

    Returns: 0.8680603183574588

  80. {152,75399,858}

    {27984,78056,29360}

    158405

    Returns: 0.2984124457884057

  81. {365,46018,878}

    {30671,32862,85957}

    124207

    Returns: 0.0

  82. {132,78789,541}

    {86885,92271,67799}

    78593

    Returns: 0.0

  83. {473,80450,558}

    {47753,6213,18347}

    52038

    Returns: 0.0

  84. {244,61590,330}

    {68195,39335,93173}

    121734

    Returns: 0.0

  85. {184,24878,745}

    {64484,70895,49948}

    198154

    Returns: 0.49692499397057643

  86. {278,38250,761}

    {80038,44851,6985}

    30691

    Returns: 0.0

  87. {451,2596,855}

    {90288,83045,85253}

    39221

    Returns: 0.0

  88. {217,47850,629}

    {55104,254,14554}

    84319

    Returns: 0.2922466039707419

  89. {417,16897,533}

    {58382,32929,76414}

    176529

    Returns: 0.4929277386518317

  90. {98765, 87654, 76543 }

    {1, 1, 1 }

    200000

    Returns: 0.9372135273032745

  91. {500, 10000, 7000 }

    {10, 10, 10 }

    100

    Returns: 1.6333333333333301E-6

  92. {100000, 100000, 100000 }

    {59999, 65432, 39999 }

    379877

    Returns: 0.895635095766732

  93. {99999, 99999, 99999 }

    {99999, 99999, 99999 }

    99999

    Returns: 0.0

  94. {2, 100, 1 }

    {9, 10, 8 }

    50

    Returns: 0.215

  95. {0, 0, 2 }

    {1, 1, 1 }

    4

    Returns: 0.5

  96. {0, 200, 0 }

    {1, 1, 1 }

    100

    Returns: 0.485

  97. {345, 265, 456 }

    {100, 100, 100 }

    756

    Returns: 0.34574130042999895

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.
This problem was used for: