Statistics

Problem Statement for "HighwayJam"

Problem Statement

It's only 9 AM, and already your day has been horrible. You overslept your alarm, your oatmeal got cold as you listened to the traffic report, and the water in your shower was frigid. To make matters worse, as you got onto the highway you saw a horrible traffic jam. To try to make your day better, you have to figure out the fastest way to get to your exit.

You have been given lanes, a int[] listing the speed (in feet per second) of cars traveling in each lane on the highway. You begin in lane 0, and your exit (located dist feet away) is also in lane 0. You are allowed to move into an adjacent lane only if you have been in your current lane for at least laneChange seconds; otherwise, you won't have sufficient time to make sure there's no accident! This also includes exiting; if you change lanes during your trip, you must return in lane 0 for at least laneChange seconds in order to safely exit the highway. If you do not change lanes during your trip, then you may exit the highway as soon as you reach your exit.

With this information, return the least amount of time required for you to reach your exit. See the examples for further clarification.

Definition

Class:
HighwayJam
Method:
minTime
Parameters:
int[], int, int
Returns:
double
Method signature:
double minTime(int[] lanes, int laneChange, int dist)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • lanes will contain between 1 and 50 elements, inclusive.
  • Each element of lanes will be between 0 and 528000, inclusive.
  • Element 0 of lanes will not be 0.
  • laneChange will be between 0 and 60, inclusive.
  • dist will be between 0 and 1000000000 (109), inclusive.

Examples

  1. {1,2}

    2

    15

    Returns: 9.5

    In this case, you can stay in lane 0, which will take you 15/1 = 15 seconds. Alternatively, you can shift into lane 1 after 2 seconds, drive for 5.5 seconds, and then switch back to lane 0 for 2 more seconds. This covers 2(1) + 5.5(2) + 2(1) = 15 feet in only 9.5 seconds.

  2. {1, 2}

    2

    6

    Returns: 6.0

    Here, you do not have enough time to safely switch to the other lane and come back, so you must stay in lane 0 the whole time.

  3. {528000}

    10

    1

    Returns: 1.893939393939394E-6

  4. {1, 0, 10}

    4

    1000

    Returns: 115.2

    The middle lane is not moving at all, but you need to pass through it to get to the fastest lane.

  5. {12, 0, 18, 0, 0, 0, 0, 944, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 528000}

    15

    1500

    Returns: 123.33333333333334

  6. {1,0,0,0,0,1,0,0,0,0, 1,0,0,0,0,1,0,0,0,0, 1,0,0,0,0,1,0,0,0,0, 1,0,0,0,0,1,0,0,0,0, 1,0,0,0,0,1,0,0,0,528000}

    1

    1000000000

    Returns: 1991.939356060606

  7. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    1

    1000000000

    Returns: 1.0E9

  8. {18886,12777,220915,451793,254335,221386,288492,404649,57421,354362,394027,344690,56059,481763,185926,300540,207426,489172,351736,157211,459368,78567,396429,129782,381530,466862,289123,438067,367135,105929,443802,386022,11058,29069}

    28

    59961394

    Returns: 269.4115446675801

  9. {383011,142042,200229,209373,428421,16919,157784}

    38

    734575199

    Returns: 1852.806942236725

  10. {374315,56370,174413,3526,408091,252980,399956,9873,526862,231170,298996,329281,70305,404925,245084,456327,308336,166505,22846,45729,309313,405857,80124,401895,507582}

    46

    998898815

    Returns: 2338.663708902901

  11. {147434,406364,488043,521750,355087,26808,525276,235178,279788,289584,137403,278651,520754,436399,79932,63060,205676,217368}

    20

    984210013

    Returns: 1926.4904130330617

  12. {434586,452094,57539,204795,424570,459434,184378,297467,242601,214097,444902,13317,66492,438652,260756,93301,328280,388286,265441,89865,525689,436444,82619,326440,408729,38031,4117}

    58

    7905772

    Returns: 18.191501797112654

  13. {266675,248709,226927,216567,345856,123497,40353,422586,420965,175306,108683,230219,188624,67528,140871,341732,160829,361503,202019,426270,451368,199708,334715,426340,526149,107796,356723,422618,98245,170846,197451,364921}

    36

    231192380

    Returns: 756.8458896188008

  14. {129764,440228,93841,24350,333193,161500,133034,455764,350124,92914,488987,163856,253743,322491,258227,44365,245859,457936,271432,36551,348437,379228,393275,135407,477474,36121,332858,314395,348029,229237,260235,477793,33818,246428,502143,367011,407928,527529,294776}

    5

    939964444

    Returns: 1961.3526725544946

  15. {178613,238538,470606,436840,282904,80818,259128,446688,117369,499917,297917,402996,107324,139743}

    31

    359512184

    Returns: 832.9769828688967

  16. {151499,33772,78725,521644,67590,217505,388139,326954,517786,387669,514082,4542,372464,134197,75507,503355,76804,512348,150611,157622,135828,69299,167343,107746,259568,42340,107422,399311,373810,19605,217801,417661,473730,188878,411305,13320,298736,271444,232626,288522,23465}

    9

    552473417

    Returns: 1103.9909689366696

  17. {245258,260924,263637,322062,137624,306600,372036,273452,375899,11379,273550,107468,474071,380973,399131,319881,292930,88933,101894,238660,170163,513199,251981,468899,148996,376959,121773,64813,67668,307190,353095,312926,460466}

    45

    176911341

    Returns: 604.1829554557818

  18. {287684,371376,343542,27936,275107,509445,27756,221179,362418,426887,433412,127348,408172,427659,366009,50336,305210,510342,411587,454206,359301,425713,411372,319321,97255,128819,524599,29721,109904,523939,99811,289940,259667,335705,210228,427127,317150,237984,12658,43920,29224}

    23

    389867270

    Returns: 877.3860770053686

  19. {238081,429630,380084,15292,411972,263672,361850,135625,161385,245222,347299,258640,374042,343898,180713,376298,232190,280524,30590,384209,508581,240819,283336,297732,371155,295994,234004,400379,526769,405273,309776,236850,199255,161860,252142,503579,317884,85993,111205,371621,223567,458504,522613,489961,166754,175326,338259}

    5

    282828203

    Returns: 648.9275906886022

  20. {147506,328784,502021}

    43

    950390869

    Returns: 1983.5376229281246

  21. {91189,224872,109908,89958,522498,312036,326808,193753,366248,471303,169333,156133,449648,172890,527754,37567,523746,522368,527529,162500,62046,337788,453797,410249,70990,73303,211033,465363,396497}

    54

    671294893

    Returns: 1610.1380541169535

  22. {319125,177152,469996,205975,489188,161157,399729,327436,104460,461414,375921,446460,106304,268028,484027,102050,154748,483556,156902,216794,185697,82699,99043,149039,156002,202428,86403,24500,296681,153647,404538,508159,223151,346535,186134,184339,507692}

    16

    860516128

    Returns: 1810.3883496733363

  23. {411629,252049,422964,410285,412429}

    24

    472576336

    Returns: 1137.9794403306191

  24. {226900,141238,255971,304949,116289,247367,453988,272292,449795,432743,189144,110829,58390,65682,511340,281541,304569,61826,358232,284261,12042,234360,153117,316023,378761,48081,198309,263190}

    46

    500618997

    Returns: 1392.747572623065

  25. {438677,216234,450690,215626,332524,170057,141614,497168,512205,46358,158312,515386,525100,116346,498726,170994,420916,32552}

    19

    297893530

    Returns: 679.0725978339416

  26. {20290,222647,252970,399051,163080,343631,26593,374857,418627,221312,177886,527214,36355,393512,224090,206412,427479,85610,82969,366189,136274,70355,255641,252620,461433,318987,37888,386338,212566,527770,323284,232856,222417,468606,524260,277849,284237,443205,17059,67217,136518,194945,486783,172873,60458,182873,271637}

    10

    826620484

    Returns: 1688.476944845926

  27. {218478,404757,317314,366471,21729,143100,157459,59618}

    59

    899058026

    Returns: 2275.5355633132967

  28. {217074,495233,174157,157681,491493,344358,334270,406699,361417,293839,435569,28363,252622,500794,509173,327847,244431,361462,488682,491390,472292,257791,173057,203115,279521,316157,360574,231491,209947,94951,183231,427021,482537,249740,477054,446030,66098,283325,217081}

    17

    371653517

    Returns: 769.5588197878575

  29. {348231,194139,517796}

    5

    333582339

    Returns: 653.7604751678267

  30. {55218,375021,89970,419862,104812,155379,94977,276685,471536,347904,508176,153483,335207,55759,472857,289744,305499,421911,100127,263950,177236,209560,55818,11105,226563,404049,205244,108711,97805,511934,235291}

    16

    937558956

    Returns: 2014.3643698246276

  31. {357589,463768,372993,344918,104805,208882,164822,84982,254717,500030,33093,199574,154126,338593,93486}

    34

    909850544

    Returns: 1977.4342257335563

  32. {463814,22713,174179,162377,426762,271775,271088,416919,255710,398732,462294,507017,88346,184235,335137,353691,1153,439943,34573,58328,524925,289291,450710,30018,381217}

    37

    260596964

    Returns: 561.8566149361598

  33. {331090,227858,2130,266904,250571,68661}

    34

    483689686

    Returns: 1460.9009211996738

  34. {485073,458604,380851,355805,285250,359868,336503,469485,167006,162195,470639,78949,89120,967,496226,270763,451677,418596,123981,420865,151560,491036,223955,271770,385518,383211,522342,346532,69196,456379,51321,26270,386984,432172,274427,144234,264040,503283,506072,323398}

    11

    10901064

    Returns: 22.473038078804635

  35. {118950,342030,370573,389714,158059,153522,406047,50924,305082,261435,167232,469204,118954,22443,355898,465486,91640,284278,409159,10262,143262,205683,177041,179848,469723,152324,50272,265122,182154,391335,31821,193457,205365,294747,55171,255776,448269,461218,306701,117703,194653,473933,58907,205959,388728,414806,35797,372720}

    25

    279121309

    Returns: 759.533296212094

  36. {206698,14991,452376,278898,484715,497052,329171,114189,43559,192506,146010,237016,290224,333109,184539,18000,253378,10109,217053,371081,97114,55338,429989,195426,444067,209147,231223,288787,380231,40532,36122,479281,475875,380850,230179}

    51

    235202255

    Returns: 673.940883247564

  37. {439131}

    34

    503967858

    Returns: 1147.64810045294

  38. {415181,514081,282603,71720,424433,7982,502181,113487,271415,71296,168825,173404,266722,84892,382551,390297,266032,127134,323181,194506,78415,271057,467708,308595,67999,181962,232297,399483,467776,456154,348977,247309,334587,523932,211382,231021,424266,185563,236860,167682,149211,405685,341086,308285,382930}

    31

    10794584

    Returns: 25.999706152256486

  39. {107476,386116,207820,185892,21525,147528,386839,89525,329490,91136,381360,161618,439643,202337,408928}

    43

    164826622

    Returns: 488.94545162593624

  40. {261955,514888,170225,498815,154570,319437,268853,388008,99722,123783,368350}

    58

    610009098

    Returns: 1241.7250470005126

  41. {441126,237269,26071,462651,277149,412910,444528,78639,396398,297888,132610,200393,392577,433890,338976,483199,418552,72931,470087,60777,464099,96657,272566,204952,377017,264641,328735,217368}

    39

    396918185

    Returns: 899.7841546406243

  42. {232776,487805,191266,167428,236954,496528,504308,315593,257278,274197,340555,457672,138774,246445,161000,514325,136997,126283,456412,90127,62382,445421,362693,267334,294439,99334,488421,404159,418985,210957,41354,123761,170762,124972,183541,407716,513852,159850,87662,135482,326399,428217,65154,465173,39015,118506}

    52

    771476365

    Returns: 1635.8983220754194

  43. {272263,158491,307172,82037,413537,466859,268828,512871,427280,144987,403856,2590,186341,419970,173352,203665,75511,53069,189517,235361,33083,217351,454112,461300,282506,283638,392667,293364,99489,461032,10154,264104,511875,209679,346141,397412,148538,86969,274636,468170,231956}

    5

    67062761

    Returns: 162.36414420000352

  44. {462814}

    45

    451042660

    Returns: 974.5657218666678

  45. {40289,369844,125469,91238,473551,122976,77383,520019,431133,526343,467304,89956,349981,368475,129666,204011,148967,454912,122192,377729}

    43

    321756869

    Returns: 909.6172809264472

  46. {345002,35174,5207,105718,501216,269183,204377,225487,309472,466573,350957,293062,412125,473933,262797,296496,269418,261141,128153,251726,503474,388980,381393,179485,9948,308305,194030,280029,277559,366898,456160,94562}

    5

    482417720

    Returns: 992.6964622039201

  47. {267641,94902,297010,385480,296726,235583,100789,482140,119708,46723,216938,308557,208493,370431,436710,460220,345905,297690,313613,525391,307638,514270,191421,59667,263829,450671,408180,250743,217095,233899,451024}

    49

    254749155

    Returns: 787.1850186780118

  48. {6}

    20

    1000000000

    Returns: 1.6666666666666666E8

  49. {2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,528000}

    1

    987654321

    Returns: 1968.5573882575757

  50. {20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,100}

    60

    90000

    Returns: 4500.0

  51. {20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,100}

    60

    900000

    Returns: 14851.2

  52. {10,0,20}

    4

    241

    Returns: 24.05

  53. {10, 15}

    2

    45

    Returns: 4.5

  54. {25, 80}

    4

    238

    Returns: 9.52

  55. {23, 68, 100, 120, 140}

    2

    128

    Returns: 5.565217391304348

  56. {12, 0, 18, 0, 0, 0, 0, 944, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 528000 }

    15

    1500

    Returns: 123.33333333333334

  57. {528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000 }

    1

    1000000000

    Returns: 1893.939393939394

  58. {1, 0, 10000 }

    2

    8000

    Returns: 8000.0

  59. {100 }

    1

    0

    Returns: 0.0

  60. {4, 1, 1 }

    1

    19

    Returns: 4.75

  61. {8114, 4593, 26656, 10674, 47815, 40607, 7358, 9461, 45816, 22936, 26299, 22567, 31836, 25180, 40656, 13543, 49324, 3094, 26027, 26009, 43079, 10556, 43881, 21388, 5580, 15736, 48306, 14536, 7515, 44548, 31872, 7184, 4353, 13061, 10152, 38016, 13890, 4927, 20248, 620, 9872, 29388, 35584 }

    58

    4004207

    Returns: 326.9202806122449

  62. {24011, 38517, 44454, 9699, 22512, 2751, 46672, 13629, 39684, 911, 42948, 1269, 44524, 4641, 7794, 17141, 19325, 40548, 29889, 24960, 5561, 13508, 45456, 45575, 14448, 52504, 2178, 6996, 24773, 23547, 13097, 48990, 22648, 22462, 24460, 38682, 32801, 7304, 9242, 9244, 36298, 44185, 5622, 33457, 22261, 44, 21927, 35517, 21071 }

    47

    7524070

    Returns: 230.74574863047485

  63. {9, 6, 5, 7, 4, 8, 5, 5, 2, 8, 3, 5, 4, 3, 2, 6, 7, 6, 8, 2, 4, 3, 1, 5, 2, 9, 4, 5, 3, 5, 5, 4, 5, 4, 8, 1, 2, 7, 7, 1, 0, 1, 1, 5, 1, 7, 5, 0, 7, 4 }

    8

    89

    Returns: 9.88888888888889

  64. {1 }

    1

    1000000000

    Returns: 1.0E9

  65. {1 }

    0

    1000000000

    Returns: 1.0E9

  66. {1, 2 }

    2

    6

    Returns: 6.0

  67. {1, 527999, 1, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000, 528000 }

    1

    10000000

    Returns: 20.93942602164019

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: