Statistics

Problem Statement for "SnakeTurbo"

Problem Statement

Already a master of the classical Snake games, you are looking for a new challenge. This time, you are controlling a snake that can move left or right, on a single axis. Your goal is to move it from startLocation to endLocation in a minimum amount of time. When you start the game, the snake has a speed of one unit of space per one unit of time. But whenever it encounters a magic orb, its speed doubles.

You are given a int[] orbs, where each element denotes the location of an orb. The orbs are always placed at integer coordinates, and can be treated as points. An orb can only be used once; it loses its magical powers after being used. You can assume the snake movement is continuous, which means that it cannot skip any intermediate points on the axis. Determine the minimum time needed to reach endLocation.

Definition

Class:
SnakeTurbo
Method:
finishTime
Parameters:
int, int, int[]
Returns:
double
Method signature:
double finishTime(int startLocation, int endLocation, int[] orbs)
(be sure your method is public)

Notes

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

Constraints

  • orbs will contain between 0 and 50 elements, inclusive.
  • startLocation and endLocation will each be between 0 and 1000000000, inclusive.
  • Each element in orbs will be between 0 and 1000000000, inclusive.
  • All elements in orbs will be distinct, and also different from startLocation and endLocation .

Examples

  1. 10

    20

    {2, 18, 8}

    Returns: 7.5

    The best solution is to move left to the orb at location 8 and then turn right, use the orb at location 18, and finish at location 20. The time needed is: |10 - 8| * 1 + |8 - 18| * 0.5 + |20 - 18| * 0.25 = 2 + 5 + 0.5 = 7.5. Note that '|' denotes absolute value. Moving directly from location 10 to location 20 has a time cost of 9, while moving from location 10 to location 2 and then to location 20 has a time cost of 9.25.

  2. 10

    0

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

    Returns: 1.998046875

  3. 77

    77

    {27, 127}

    Returns: 0.0

  4. 0

    100000000

    {99999999}

    Returns: 9.99999995E7

  5. 100

    200

    {99, 102, 96, 108, 84, 132, 36}

    Returns: 8.375

  6. 1000

    10000

    {999, 1005, 966}

    Returns: 1143.0

  7. 10

    100

    {11, 0}

    Returns: 31.5

  8. 1000

    1000000000

    {999, 998, 997, 996, 995, 994, 993, 992, 991, 990, 989, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1001, 1002, 1003, 1004, 1005, 1007, 1009, 1010, 1020, 10001, 100002, 100004, 987654321, 987654322, 989898989, 999999997, 999999998, 999999999}

    Returns: 2.0081691057391424

  9. 40

    30

    {20, 39, 45, 47, 49, 1000000000}

    Returns: 5.5

  10. 7777

    5555

    {}

    Returns: 2222.0

  11. 0

    1024

    {1, 2, 4, 8, 16, 32, 64, 128, 256, 512}

    Returns: 6.0

  12. 4256

    9999

    {212, 3214, 544, 8912, 4892, 128, 8492, 8948, 1824, 48, 9003, 9994, 99, 119, 4177, 756, 5487, 4756, 888, 908, 1098, 81, 7605, 7128, 7599, 7336, 1, 2, 3, 9092, 4568, 4389, 1299, 3789, 2890, 1289, 8429, 474, 4419, 213, 5598, 4829, 8859, 8593, 9299, 1290, 84, 46, 2229, 3393}

    Returns: 232.18855934188664

  13. 3

    0

    {4, 5, 6, 8, 10, 13, 16, 21, 27, 35, 45, 58, 74, 95, 122, 157, 202, 260, 334, 429, 551, 708, 910, 1070, 1404}

    Returns: 2.370961904525757

  14. 0

    1000000000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 42, 45}}

    Returns: 2.0009095253999476

  15. 0

    1000000000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}

    Returns: 2.0000008881783735

  16. 1000000000

    0

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}

    Returns: 9.99999951E8

  17. 1000

    20000

    {999, 997, 994, 990, 985, 979, 972, 956, 931, 889, 842, 775, 1002, 1005, 1010, 1020, 1040, 1080, 1120, 1200, 1300, 1500, 1900, 1901, 1999, 20001}

    Returns: 4.163080960512161

  18. 500000000

    0

    {499999999, 500000003, 499999991, 500000027, 499999919, 500000243, 499999271, 500002187, 499993439, 500019683, 499940951, 500177147, 499468559, 501594323, 495217031, 514348907, 456953279, 629140163, 112579511}

    Returns: 5681.183437347412

  19. 500000000

    100000000

    {499999999, 500000002, 499999996, 500000008, 499999984, 500000032, 499999936, 500000128, 499999744, 500000512, 499998976, 500002048, 499995904, 500008192, 499983616, 500032768, 499934464, 500131072, 499737856, 500524288, 498951424, 502097152, 495805696, 508388608, 483222784, 533554432, 432891136, 634217728, 231564544}

    Returns: 35.990116119384766

  20. 500000000

    0

    {499999999, 500000003, 499999992, 500000020, 499999950, 500000125, 499999687, 500000783, 499998042, 500004895, 499987762, 500030595, 499923512, 500191220, 499521950, 501195125, 497012187, 507469533, 481326167, 546684583, 383288542, 791778645}

    Returns: 928.4932708740234

  21. 500000000

    0

    {499999999, 500000002, 499999997, 500000005, 499999993, 500000010, 499999986, 500000019, 499999974, 500000035, 499999953, 500000063, 499999915, 500000114, 499999847, 500000205, 499999726, 500000366, 499999511, 500000653, 499999129, 500001162, 499998450, 500002067, 499997243, 500003677, 499995097, 500006538, 499991282, 500011625, 499984499, 500020669, 499972441, 500036746, 499951005, 500065327, 499912897, 500116138, 499845149, 500206469, 499724707, 500367058, 499510589, 500652549, 499129934, 501160089, 498453214, 502062382, 497250157, 600000000}

    Returns: 4.899532506911905

  22. 14739012

    449842127

    {102457899, 258019305, 288238212, 7750000, 60777956, 353932032, 62186736, 73853675, 16107360}

    Returns: 2.3713853255859375E7

  23. 18102175

    96325767

    {271309830, 119599740, 336657582, 483936544, 34218779, 200552625, 36369170, 47651910, 76043364, 25724952, 53895026, 1680104, 225343272, 18171944, 105967610, 12726000, 170581671, 64280880, 72495960, 121216992, 28344134, 30732894, 363726291, 73841318, 5180944, 33572, 2260080, 16124498, 296600460, 21402121, 34137594}

    Returns: 3289959.757537842

  24. 42516705

    74086

    {68210232, 8032200, 652459, 200376815, 84524468, 41811636, 34145064, 7892695, 4668742, 395089464, 122017015, 149752320, 128982672, 38778985, 43398450, 151743079, 144576104, 90344737, 1629105, 22038710, 110196980, 123180642, 25968174, 171256368, 86140172, 29486592, 136488992, 71261450, 49862983, 138761980, 113452560, 40527808, 104468838, 139755720, 454990210, 89584962, 300409758, 3431918, 15279039, 1251068}

    Returns: 2778424.9805145264

  25. 336481488

    101405782

    {74208645, 31419312, 467224914, 9423700, 72842832, 34089484, 4511312, 66487365, 390025128, 39215358, 398789664, 275014528, 332516802, 309216231, 117598740, 313463520, 77894420, 138902208, 132163274, 5005476, 175528446}

    Returns: 2.64731471953125E7

  26. 3447324

    12511620

    {83505558, 156804360, 105226128, 485121455, 1278926, 6866510, 313370316, 310316844, 57106428, 179607220, 128145995, 169508256, 4408614, 47561085, 267400984, 393037662, 7704141, 5085080, 326467055, 7941531, 314809250, 55314630, 11765698, 160983658, 5794390, 3190, 78491430, 118992960, 77449119, 29887922, 58081906, 39452184, 9021705, 115159650, 43197624, 10088595, 90669277, 17601748, 99037048, 684912, 39830562, 239721695, 102408612}

    Returns: 1703856.734375

  27. 159898426

    7375280

    {47085631, 58098550, 14073015, 64968046, 210155428, 184937994, 491655120, 208072620, 126699870, 36161839, 42911031, 288129598, 39724568, 225334818, 5257216, 131215860, 142352840, 9367990, 257030680, 33388740, 158435816, 41060565, 151535530, 92701896, 62711656, 9083620, 44548860, 59894475, 18761734}

    Returns: 1.0423707127847672E7

  28. 110829319

    307556224

    {70737548, 82485655, 242481893}

    Returns: 8.5288095125E7

  29. 24119221

    271300220

    {38547858, 51001137, 138658404}

    Returns: 5.914982025E7

  30. 77881418

    59620320

    {25291308}

    Returns: 1.8261098E7

  31. 96407906

    3660612

    {69611136, 257607261, 35099568, 114494000, 46330492, 28362000, 104969000, 210622078, 41587068, 2948372, 34472158, 3664656, 27935202, 20851248, 158788374, 409306168, 2584288, 289291722, 50973850, 203308926, 2444288, 59739826, 21360218, 20598735, 38775568, 29164100, 3812692, 258535953, 1428301}

    Returns: 2.658964597695923E7

  32. 14962592

    12757075

    {29234445, 2694795, 237428119, 155981705, 250320, 3832598, 23793, 26865904, 56339504, 11077920, 258290640, 148359862, 151309136, 60770718, 228203481, 109996544, 133541100, 149993178, 14684971, 60095100, 90292700, 28244153, 15264350, 200882064, 149503406, 130460736, 5759737, 220742722, 204353758, 30265573, 161455487, 200941140}

    Returns: 1073421.5

  33. 6050246

    115154295

    {27055833, 86311186, 330783750, 17098125, 16867116, 384999426, 334460904, 530227808, 120012724, 10831324, 23994548, 92273425, 169518978, 5432830, 139525293, 382840136, 79443196, 113262705, 55538504, 155610716, 3452438, 8081744, 13721138, 31619862, 30861207, 37624745, 23132200, 76183236, 83469855, 100864764, 327779998, 4567725, 60434360, 77299200, 3764700, 13432036, 95994650, 13203968, 102335638, 249240030, 14913280, 87083724, 2812980, 23123880, 112450800, 79781592, 168540510, 28618704, 77068725, 159649875}

    Returns: 1560349.5916371953

  34. 155908207

    60998658

    {30029454, 67450896, 38958780, 59272020, 38515113, 445022112, 233424768, 64507608, 80285120, 363702352, 76617576, 93143232, 17825448}

    Returns: 7.15503621875E7

  35. 306046167

    3637404

    {19170333, 298509506, 368924271, 324336792, 12176880, 15478753}

    Returns: 7.578375259375E7

  36. 6046035

    13533828

    {96480385, 180461984, 137962748, 262221520, 12206961, 291807628}

    Returns: 6824359.5

  37. 17428366

    2027970

    {128333790, 170722720, 86023420, 103163040, 249940048, 38420626, 33806182, 123927110, 99262527, 25621652, 1767052, 37682625, 174984452, 8798484, 573129117, 120336, 109983099, 409082560, 131794356, 24822029, 12921990, 36622608, 306117696, 51573600, 151957, 134954520, 120728396}

    Returns: 8260757.5

  38. 27350310

    59092446

    {99855885, 67533048, 71215140, 15565386, 36944955, 23579437, 13957680, 28530876, 261798128, 98111208, 672846, 51760170, 138509959, 13647774, 7851844, 419803351, 108671868, 12302556, 9911356, 135921024, 9550008}

    Returns: 6027455.231933594

  39. 53680549

    105618528

    {64201380, 33935360, 1029300, 13204908, 2017569, 222854868, 64790544, 264029464, 49609635, 41893632, 64101264, 48445026, 9899304, 17556038, 363939072, 194036202, 251593342, 25024850, 5726292, 244191410, 157573206, 56562295, 151096682, 84382809, 16969338, 41283675, 513263779, 95681925, 44089116, 5468946, 6612224, 35713282, 20753258, 428535248}

    Returns: 6353127.135960996

  40. 74906559

    468977220

    {279827310, 162534975, 339093160, 8688141, 610869573, 32200272, 364458, 89125754, 77141582, 146228085, 36135127, 67178844, 106462976}

    Returns: 1.9083517229492188E7

  41. 23670945

    259403904

    {1576058, 3765160, 49148475, 2388852, 181708970, 15508080, 40541688, 96351402, 255794790, 129401909, 188863812, 50905645, 320011536, 27001185, 3666108, 3361525, 113067556, 3819798, 7309412, 10507275, 33950300, 20680779, 16604926, 1271484, 21099864, 32474114, 5659352, 22524480, 65162675, 9526014, 77940605}

    Returns: 2741364.374576805

  42. 98992956

    12936900

    {82407052, 31359380, 119044407, 15506932, 176025058, 70925106, 2239208, 526683936, 24809855, 6065376, 2676180, 28807500, 24575320, 525826845, 104197463, 66964508, 263532217, 30912356, 21945924, 219279057, 52439154, 5240238, 452710880, 296839517, 82266129, 1550718, 17224235, 7394400, 367816344, 677625, 135555164, 39775890, 336363516, 54010498, 146911788, 104992368}

    Returns: 1.2381892720108032E7

  43. 91400400

    7254824

    {87126686, 6130527, 50036976, 21669870}

    Returns: 3.171222625E7

  44. 15392280

    38839975

    {121491156, 377972616, 62483740, 38296104, 2348850, 120235962, 95047500, 23881718, 3876534, 404573494, 119676180, 37807779, 10417960, 41836002, 19300950, 39107124}

    Returns: 9775601.8125

  45. 22931300

    5981535

    {98363978, 287939925, 49401300, 380740145, 266035260, 335940960, 545258940, 62543687, 47291554, 4155975, 27691455, 364230098, 206515388, 26720820, 18397189, 3362528, 10329166}

    Returns: 7878633.8125

  46. 75679314

    8243613

    {69648425, 9381869, 140403540, 263288570, 8339703, 106508129, 2974752, 10945125, 202811700, 86092592, 787280, 22486728, 136457550, 10638615, 56656314, 63650448, 4719176, 117818624, 60062376, 331054548, 80863520, 61724347, 74842880, 139427142, 113648612, 47349045, 12338040, 202709340, 348935553, 65847722, 37715515, 43555158, 17766736, 144465300, 23871798, 279087060, 140411745, 4032196, 39305462, 3798124, 122338188}

    Returns: 4989486.1291770935

  47. 64276564

    42323888

    {1955165, 56931342, 498900060, 50879328, 32338957, 284546272, 11063070, 94505615, 122723858, 28441101, 1854815, 62644580, 27482668, 18677001, 356459055, 181268416, 151759952, 117375178, 94320930, 328249532, 198308871, 213459036, 415044, 32205102, 459939650, 164161305, 22581405, 30017466, 105916725, 184620800, 16800075, 1637100, 8873676, 24585600, 68376000}

    Returns: 7071036.5

  48. 57200

    36364458

    {42635583, 27927456, 55610520, 81978930, 48564160, 636840, 114848671, 109489341, 213468762, 71266447, 77924288, 223392994, 93874133, 23518236, 17024130, 128013936, 20798136, 6431440, 189421344, 9927330, 126651206, 19297237, 116712800, 140882160, 32931976, 118235096, 61320955, 91629627, 1704381, 338217876, 134588864, 7098300, 209669176, 12564300}

    Returns: 2743959.0122070312

  49. 19271207

    119532179

    {21050490, 7461922, 6803225, 6955984, 464018560, 17243330, 3185725, 573433056, 19819008, 34179959, 45563811, 217253913, 113677758, 12591425, 56626716, 319505609, 157284888, 12792312, 218896178, 23528752, 28555712, 7952896, 221823667, 80428418, 12055120, 3415498, 17856930, 552603}

    Returns: 2345304.880651951

  50. 52658275

    83738670

    {67776200, 13912236, 290708170, 261540879, 128268444, 34206289, 526149, 212040, 9508104, 394009, 195531400, 42742140, 111770529, 49442970, 175690938, 72678600, 19665600, 15380382, 87155797, 4107808, 1178212, 153317080, 122302593, 33941835, 54974304, 303407974, 90275616, 38652680, 436798525, 253899507, 6759164, 28682438, 8846848, 122948536, 328801590, 11022774}

    Returns: 7730857.664008141

  51. 21463000

    173937600

    {485397894, 55719975, 291212952, 98696490, 16839900, 366716231, 231831990}

    Returns: 4.4212405E7

  52. 19996164

    2316600

    {23166075, 13778953, 200404692, 19318068, 235476, 301621998, 132608412, 130587314, 151602858, 38697400, 175808204, 2103360, 76634576, 278852190, 392912030, 8327914, 100157778, 206054016, 16715864, 11327176, 6338100, 160882980, 19301496, 53867688, 250876224, 200833344, 10225432, 280905144, 275779896, 58773332}

    Returns: 1948472.5625

  53. 6470940

    21228584

    {340454492, 74214045, 28405456, 161074026, 101599525, 30090553, 137035409, 1686456, 158737536, 59367204, 40871735, 30740160, 76095890, 363447040, 243111680, 105883470, 530624835, 384804069, 165916250, 59814624, 45577675, 8348470, 184110667, 311026038, 316198680, 267991416, 301378588, 780255}

    Returns: 7991128.375

  54. 8564181

    83330286

    {185704272, 183344490, 39117100, 87832500, 34282208, 61263996, 45289047, 25785936, 93786870, 17186013, 9094922, 64545663, 6828523, 24364366, 51156070, 163516730, 77637102, 244032120, 109142600, 69168528, 16756480, 5784450, 232668189, 3917823, 137555670, 400440168, 551146046, 283014252, 346085784, 49389610, 27809958, 56730366, 123109920, 350222410, 1867096, 30315488, 265469015, 346910508, 5107752, 349032884, 4515955, 15338610, 13803048, 56168147, 30288812, 346085608, 33214599, 145650658, 246896544, 355466760}

    Returns: 2204044.640555948

  55. 568192896

    212193150

    {394438715, 6427975, 331167998}

    Returns: 2.351332515E8

  56. 231705188

    80204748

    {107610885, 74321496, 11944982, 33041100, 19352034, 10388994, 4774527, 7901585, 126243925, 34555528, 106821936, 2362272, 357737843, 65081178, 234496755, 47721920, 63174870, 143544485, 2375275, 134370264, 207709326, 101803380, 213224576, 64920768, 581782826, 39484800, 191420625, 7421223, 37914522, 30796024, 7108920, 63317709, 201341816, 4028835, 49941444, 143134462, 32698356, 13050620, 67741336, 432694438, 40146741, 33337728, 39944304, 144648294, 23450175, 158223840, 100869828}

    Returns: 1.7517869260253906E7

  57. 76663140

    110308920

    {18283572, 37684, 78957424, 201205015, 80447496, 7351300, 7777324, 19272600, 27712160, 296872139, 22678590, 33235000, 97703368, 285949180, 192238512, 16436160, 216315825, 136494075, 2501368, 60856096, 159812352, 93620123, 426802185, 5165800, 121921235, 96623835, 380217879, 89568696, 273850852, 892588, 425230248, 119213752, 51095253, 146601300}

    Returns: 6244477.53125

  58. 192493290

    104104200

    {2508055, 161595995, 561349832, 78688680, 8378970, 134223568, 142070337, 15791856, 57666940, 127898427, 7360640, 36191508, 35398090, 179632922, 381858940, 43995014, 7179271, 112459764, 178707760, 132085140, 34205446, 126039484, 29714028, 45746018, 325356946, 2884878, 44896936, 17394102, 49643003, 41791024, 42536160, 46851192, 40766971, 315918450, 56794290, 36927332, 97743300, 64318968, 93483576, 12904990, 119322390, 311575558, 11743584}

    Returns: 2.0726588765625E7

  59. 760

    389

    {939, 593, 721, 400, 994, 450, 974, 70, 828, 586, 186, 548, 990, 485, 394, 616, 151, 503, 906, 638, 909, 761, 304, 547, 405, 779, 889, 317, 81, 299, 688, 121, 295, 853, 156, 996, 655, 603, 498, 894, 885, 414, 443, 636, 681, 726, 280, 102, 379, 678}

    Returns: 24.97099858522415

  60. 706

    872

    {588, 998, 52, 150, 752, 178, 383, 548, 930, 561, 323, 27, 473, 741, 358, 285, 593, 830, 889, 208, 365, 805, 907, 942, 662, 870}

    Returns: 59.4375

  61. 343

    273

    {870, 491, 171, 704, 160, 610}

    Returns: 70.0

  62. 293

    155

    {365, 638, 269, 655, 212}

    Returns: 66.75

  63. 191

    782

    {892, 316, 389, 96}

    Returns: 259.75

  64. 701

    421

    {983, 881, 870, 805, 198, 812, 684, 490, 107, 87, 146, 54, 846, 711, 562, 85, 800, 582, 47, 420, 315, 408, 426, 748, 290, 608, 148, 447, 818, 660, 196, 379, 2, 678, 993, 157, 151, 893, 579, 831, 675, 84, 205, 141, 342}

    Returns: 27.25537109375

  65. 289

    877

    {415, 185, 437, 278, 813, 132, 493, 50, 534, 113, 684, 14, 211, 773, 629, 681, 428, 787, 647, 203, 617, 955, 509, 225, 373, 274, 772, 958, 562, 962, 500, 948, 191, 696, 749, 995, 577, 588, 41, 937, 184, 846, 566, 595, 420}

    Returns: 28.336292687063178

  66. 129140163

    1000000000

    {129140164, 129140160, 129140172, 129140136, 129140244, 129139920, 129140892, 129137976, 129146724, 129120480, 129199212, 128963016, 129671604, 127545840, 133923132, 114791256, 172186884, 0, 999999999, 999999998, 999999997, 999999996, 999999995, 999999994, 999999993, 999999992, 999999991, 999999990, 999999989, 999999988, 999999987, 999999986, 999999985, 999999984, 999999983, 999999982, 999999981, 999999980, 999999979, 999999978, 999999977, 999999976, 999999975, 999999974, 999999973, 999999972, 999999971, 999999970, 999999969, 999999968}

    Returns: 7752.742160797119

  67. 34

    0

    {33, 39}

    Returns: 13.75

  68. 5

    39

    {0, 6}

    Returns: 13.75

  69. 100

    200

    {99, 102, 96, 108, 84, 132, 36 }

    Returns: 8.375

  70. 50

    1000000000

    {49, 48, 47, 46, 45, 44, 43, 42, 1, 40, 39, 38, 37, 35, 36, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 41, 0 }

    Returns: 2.000000888178418

  71. 0

    100

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 2.0000000000000426

  72. 10

    200

    {1, 2, 3, 11 }

    Returns: 17.8125

  73. 999

    10000000

    {0, 1, 2, 3, 4, 5, 1000, 1001, 1002, 1003 }

    Returns: 9829.935546875

  74. 10

    100

    {1, 11 }

    Returns: 30.75

  75. 0

    1000000000

    {100000000, 200000000, 300000000, 400000000, 500000000, 600000000, 700000000, 800000000, 900000000, 100004000, 200004000, 300004000, 400004000, 500004000, 600004000, 700004000, 800004000, 900004000, 100300000, 200300000, 300300000, 400300000, 500300000, 600300000, 700300000, 800300000, 900300000, 100000200, 200000200, 300000200, 400000200, 500000200, 600000200, 700000200, 800000200, 900000200, 100001000, 200001000, 300001000, 400001000, 500001000, 600001000, 700001000, 800001000, 900001000 }

    Returns: 1.0323592258064504E8

  76. 500

    1000000000

    {501, 504, 492, 519, 477, 5992, 8, 50, 1300, 2443, 200000, 1 }

    Returns: 244221.9169921875

  77. 10000

    1000000000

    {10001, 1 }

    Returns: 2.5000500075E8

  78. 100

    500000000

    {3443, 46757, 79889, 9090, 23299, 102, 96, 108, 84, 132, 36, 234234, 43564356, 43564353, 2342, 2458909, 2349284, 1237656, 73845387, 329485943, 495438543, 394834, 34535, 3567567, 6578768, 678678, 898898, 234243, 54654564, 65465456, 32131321, 2131564, 464654, 327498, 234685, 3246874 }

    Returns: 155.74492426183133

  79. 1000000000

    50

    {49, 48, 47, 460, 45, 44, 43, 42, 1, 40, 39, 38, 37, 35, 36, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 41, 0 }

    Returns: 9.99999745E8

  80. 0

    1000000000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 2.0000008881783735

  81. 1000

    10000

    {1001, 990, 1100, 500 }

    Returns: 702.75

  82. 0

    1000000000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 }

    Returns: 2.1164153177523986

  83. 100

    100000

    {1, 2, 3, 4, 101 }

    Returns: 3174.90625

  84. 500000000

    1000000000

    {500000001, 499999997, 500000009, 499999271, 500006561, 500059049, 500531441, 500478269 }

    Returns: 1960208.90234375

  85. 500000000

    1000000000

    {250000000, 300000000, 200000000, 190000000, 189000000, 188900000, 188890000, 188889000, 188888900, 188888890, 188888889, 750000000 }

    Returns: 2.3915080466455078E8

  86. 250000000

    750000000

    {148193122, 615983917, 789376168, 674673414, 178929786, 480757868, 734355081, 312582500, 84061266, 777025060, 374443668, 622594029, 707287944, 486228446, 460903623, 745815341, 863796931, 560992082, 714570893, 12068110, 732244380, 583389641, 680994804, 261298817, 427015462, 930187866, 586360304, 855879995, 808763876, 81361265, 260319004, 804270544, 952346234, 203692574, 676100602, 195343775, 682548786, 522954717, 149608075, 512234949, 870766380, 7951954, 307469476, 869054875, 199255720, 101762192, 617817291, 794944714, 363372909, 896675393 }

    Returns: 2.7284325044738688E7

  87. 1000000

    0

    {1000001, 1000002, 1000003, 1000004, 1000005, 1000006, 1000007, 1000008, 1000009, 1000010 }

    Returns: 978.5703125

  88. 10

    800

    {4, 12 }

    Returns: 205.0

  89. 500000000

    0

    {500000100, 499999300, 600000100, 100000100 }

    Returns: 9.375070625E7

  90. 500000

    1000000000

    {0, 500001, 500002 }

    Returns: 1.25125002E8

  91. 105

    0

    {100, 104, 106, 126 }

    Returns: 14.125

  92. 15

    51

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 1.9999999999708962

  93. 25

    999999975

    {0, 1000000000, 1, 999999999, 2, 999999998, 3, 999999997, 4, 999999996, 5, 999999995, 6, 999999994, 7, 999999993, 8, 999999992, 9, 999999991, 10, 999999990, 11, 999999989, 12, 999999988, 13, 999999987, 14, 999999986, 15, 999999985, 16, 999999984, 17, 999999983, 18, 999999982, 19, 999999981, 20, 999999980, 21, 999999979, 22, 999999978, 23, 999999977, 24, 999999976 }

    Returns: 31.802321583032608

  94. 500000000

    0

    {999999999, 999999998, 999999997, 999999996, 999999995, 999999994, 999999993, 999999992, 999999991, 999999990, 999999989, 999999988, 999999987, 999999986, 999999985, 999999984, 999999983, 999999982, 999999981, 999999980, 999999979, 999999978, 999999977, 999999976, 999999975, 999999974, 999999973, 999999972, 999999971, 30, 29, 28, 27, 999999906, 25, 24, 23, 22, 21, 20, 99999999, 9999998, 999997, 99996, 995, 94, 999599993, 999992992, 919999991, 909999990 }

    Returns: 4.349495501176441E8

  95. 4

    1

    {2 }

    Returns: 2.5

  96. 500000000

    0

    {500000002, 500000001, 499999992, 500000027, 499999936, 500000125, 499999784, 500000343, 499999488, 500000729, 499999000, 500001331, 499998272, 500002197, 499997256, 500003375, 499995904, 500004913, 499994168, 500006859, 499992000, 500009261, 499989352, 500012167, 499986176, 500015625, 499982424, 500019683, 499978048, 500024389, 499973000, 500029791, 499967232, 500035937, 499960696, 500042875, 499953344, 500050653, 499945128, 500059319, 499936000, 500068921, 499925912, 500079507, 499914816, 500091125, 499902664, 500103823, 499889408, 500117649 }

    Returns: 30.89261965379289

  97. 13

    1000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 14, 16, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 39, 40, 43, 44, 45, 46, 47, 48, 49, 52, 53, 54, 55 }

    Returns: 2.003021526903467

  98. 100

    0

    {80 }

    Returns: 60.0

  99. 100

    1000000000

    {0, 101, 102 }

    Returns: 1.25000027E8

  100. 77

    77

    {27, 127 }

    Returns: 0.0

  101. 1000

    3000

    {0, 1001, 1, 2 }

    Returns: 688.375

  102. 10000

    1000000000

    {9000, 10001 }

    Returns: 2.499982515E8

  103. 100

    20

    {50 }

    Returns: 65.0

  104. 0

    10

    { }

    Returns: 10.0

  105. 50

    200

    {51, 46, 66, 18 }

    Returns: 24.875

  106. 500000000

    0

    {499999999, 500000002, 499999993, 500000020, 499999939, 500000182, 499999453, 500001640, 499995079, 500014762, 499955713, 500132860, 499601419, 501195742, 496412773, 510761680, 467714959, 596855122 }

    Returns: 5230.605361938477

  107. 123456

    12345644

    {12, 4, 1234, 1233, 123450, 123400, 12345645, 12345670, 123545, 654444, 354, 1534599, 12345643, 12345642, 12345640, 1230000, 12300054 }

    Returns: 24634.76107788086

  108. 0

    60

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 2.000000000000007

  109. 2

    1000

    {0, 3, 5 }

    Returns: 128.125

  110. 100

    90

    {99 }

    Returns: 5.5

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: