Statistics

Problem Statement for "CakesEqualization"

Problem Statement

You are organizing a party and have bought several pieces of cake for it. The weights of these pieces are given in the int[] weights, where each element corresponds to the weight of a single piece.

After looking at the pieces more carefully, you became worried that they have different weights and decided to make these differences smaller. In order to do this, you can make at most maxCuts cuts. With each cut you can choose one of the pieces you currently have and divide it into two distinct pieces. Note that each of these two pieces can be chosen again when making subsequent cuts.

Your goal is to produce cuts in such way that the difference between the maximal and the minimal pieces' weights becomes as small as possible. Find the best way of making cuts and return the optimal difference.

Definition

Class:
CakesEqualization
Method:
fairDivision
Parameters:
int[], int
Returns:
double
Method signature:
double fairDivision(int[] weights, int maxCuts)
(be sure your method is public)

Notes

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

Constraints

  • weights will contain between 1 and 50 elements, inclusive.
  • Each element of weights will be between 1 and 1,000,000,000, inclusive.
  • maxCuts will be between 1 and 100,000, inclusive.

Examples

  1. {1, 3}

    2

    Returns: 0.0

    First, choose the piece with weight 3 and cut it into pieces with weights 1 and 2. Then, choose the piece with weight 2 and cut it into two pieces with weight 1. Now all pieces have the same weight, so the answer is 0.

  2. {1, 1, 1, 1, 1}

    4

    Returns: 0.0

    Even though you are allowed to make 4 cuts, there is no sense in making any of them.

  3. {1, 3}

    1

    Returns: 0.5

    The same case as in example 0, but now you are allowed to make only one cut. The best thing to do is to cut the piece with weight 3 into two pieces with weights 1.5.

  4. {7, 11, 13}

    10

    Returns: 0.3999999999999999

  5. {13, 69, 41, 37, 80}

    27

    Returns: 1.4666666666666668

  6. {414019321,30667337,2402966,173333436,979544501,879112468,105872869,264147125,163480207,247568752,268968791,360757816,20516599,238075182,516626934,952201900,493717434,255734317,87546725,552635279,491216890,285590872,248633409,721570995,499355008,463260539,462203095,407868086,458998576,591393203,992393673,182025394,809006700,166115526,492696203,934322316,803425590,986506035,535167763,68449307,926215028,665840054,100505101,451543041,747225566,634409905,129470459,349974178,658301459,33478869}

    1

    Returns: 9.84103069E8

  7. {642668141,717461656,15737233,767809368,185221781,571465275,198758191,946131071,964265411,13898438,616247271,807418634,601295590,54020075,82809572,312695993,63217549,838147636,940294000,88884004,116653155,226594969,278190951,521869603,268363164,850029844,248575478,366373230,289070732,957936064,576905336,553490131,331333714,251716781,922864511,276384786,965951921,363284034,735791604,662343000,95036414,895918671,454213206,717848406,380734261,689218479,878007294,554481959,470629699,265096410}

    10

    Returns: 7.93520196E8

  8. {772129825,384695033,109856625,376252680,738642705,856403622,683133038,14418426,959992718,706707680,96026709,149711909,938916325,506333239,984232204,24597788,781398092,323783759,772810878,797054540,320854585,93013200,805828476,117834376,734656926,857974137,248180712,875377657,619606089,936361677,9681141,974828938,233855617,298087020,265944465,401060849,862890588,786194717,698113322,712462470,784267587,707755211,463606237,181277470,225966270,754647608,566670743,404958756,469727906,55556849}

    100

    Returns: 2.0481239325E8

  9. {602379653,153925919,714496011,784820375,601277492,846700869,253903885,655166961,52914354,969629416,667358261,965676065,257525280,802802103,538997221,268401907,334230444,995677618,580998921,51303493,12221508,167471855,323835605,994033418,169546542,652386403,971282850,663661854,958095569,323440190,425871391,645874256,773163041,647133203,627962096,430776062,130364192,715094288,715560130,856832523,84551658,632928653,583102554,492707655,535804343,607717899,795374944,511134748,546226574,555698439}

    1000

    Returns: 1.4701995875E7

  10. {661589242,947320907,472387331,736402063,622284001,257692065,760270912,622106412,830028132,896740590,502349994,344203862,523553138,972126878,613681383,690417797,599523051,905353449,246900517,438896592,761471398,449113424,579583069,992131214,661546153,776823227,466744227,810124843,112552539,871900940,246772812,992911774,173873146,882731104,587636778,202352975,469324845,865826610,205294255,357549158,913439733,526853624,418993199,887014661,6254084,452572222,157718728,562909555,114652505,271689106}

    10000

    Returns: 34517.92156862747

  11. {279026531,698011995,637438385,109845286,855414280,712375195,46223461,442120726,508833248,859978909,765234617,990663809,501967870,65333683,385646033,244424271,1779244,220239614,355283735,673796739,421144819,719168009,474628227,347109781,85619284,969474426,327132143,703721465,159356383,934126845,260021909,178067042,934219365,933843938,464388909,748059167,954677034,415604578,666111597,960962172,790530522,767929491,242551486,633122563,626676596,396717498,933086007,214754581,802145165,672874597}

    100000

    Returns: 710.7880937401787

  12. {1}

    100000

    Returns: 0.0

  13. {1000000000}

    1

    Returns: 0.0

  14. {1,1000000000,1000000000}

    1

    Returns: 9.99999999E8

    max answer

  15. {50000,50001}

    100000

    Returns: 0.0

  16. {50001,50002}

    100000

    Returns: 3.9999181744576617E-10

    small non-zero answer

  17. {1000000000,1}

    1

    Returns: 4.99999999E8

  18. {1000000000,1}

    100000

    Returns: 9998.90000099999

  19. {25001,25002}

    50000

    Returns: 1.5999359614937703E-9

  20. {922180093,922180107,922180155,922180104,922180113,922180261,922180115,922180124,922180230,922180165,922180229,922180276,922180204,922180251,922180217,922180089,922180210,922180122,922180079,922180260,922180153,922180141,922180157,922180283,922180113,922180084,922180240,922180200,922180197,922180304,922180259,922180089,922180194,922180203,922180164,922180099,922180101,922180285,922180148,922180197,922180177,922180268,922180222,922180190,922180179}

    58

    Returns: 112.5

  21. {496135,496135,496135,496135,496135,496136,496136,496135,496136,496135,496136,496136,496136,496135,496136,496135,496136,496135,496135,496135,496135}

    100000

    Returns: 2.099958000769675E-4

  22. {568,579,540,537,515,546,548,546,501,535,512,537,537,519,557,511,534,515,539,565,556,571,562,552,519,497,498,543,552,499,567,567,541,521,566,519,540,557,523,512,518,517}

    100000

    Returns: 0.0

  23. {162589667,365085897,458525206,504490984,486917250,142011733,848646326,44221742,654158730,769623179,283564081,624911215}

    100000

    Returns: 4.400881698602461

  24. {47479,453994,373064,43085,80481,686215,437649,711626,125334,278731,438485,111259,626515,600930,404385,16181,151180,359698,825461}

    100000

    Returns: 0.024235744544938598

  25. {9735397,9735389,9735405,9735435,9735441,9735393}

    950

    Returns: 0.32704402515810216

  26. {79485,79444,79455,79413,79362,79373,79381,79518,79434,79414,79432,79369,79396,79499,79476,79536,79409,79451,79400,79365,79507,79483,79460,79337,79423,79348,79453,79344,79527,79452,79348,79426,79534,79391,79534,79356,79466,79459,79438,79444,79458,79525,79383,79538,79417,79459,79483,79341,79429}

    317

    Returns: 28.714285714286234

  27. {509576654,509602640,509621703,509592052,509588845,509616957,509599279,509598126,509608549,509621319,509616236,509569457,509576522,509590809,509567704,509580399,509584127,509596967,509598749,509562082,509577635,509591503,509562372,509588340,509596479,509577331,509590101,509580356,509603410,509603841,509581167,509575931,509579489,509565399}

    711

    Returns: 2839.0952380932868

  28. {91,282,184,87,182,300,133,202,242,186,151,181,246,161}

    52

    Returns: 8.700000000000003

  29. {883,616,1067,264,321,943,673,940}

    9

    Returns: 177.5

  30. {21064,21073,21069,21069,21050,21076,21072,21066,21054,21073,21069,21057,21062,21079,21069,21063,21051,21069,21075}

    68

    Returns: 7.25

  31. {26656725,396508525,412120998,465487500}

    99380

    Returns: 0.04594895564514445

  32. {31577,53637,77182,12453,333684,46728,295227,320941,311724,29075,112479,43525,334024,291029,57697,81660,233517,162834,229640,211977,306414,170329,159425,11438,209478,70701,68216,158861,333876,237744,265208,172610,159220,270547,8337,334979,144120,147014,151099,255670}

    100000

    Returns: 0.10802571111044301

  33. {2108612,2108608,2108633,2108541,2108519,2108641,2108355,2108387,2108548,2108574,2108607,2108348,2108529,2108347,2108347,2108589,2108333,2108576,2108363,2108575,2108481,2108346,2108673,2108347,2108418,2108599,2108333,2108600,2108405,2108449,2108504,2108675,2108515,2108524,2108588,2108465}

    490

    Returns: 24.428571428579744

  34. {9571482,9571475,9571486,9571473,9571478,9571471,9571467,9571479,9571484,9571492,9571485,9571486,9571467,9571469,9571490,9571478,9571472,9571485,9571485,9571486,9571471,9571474,9571483,9571486,9571483}

    34

    Returns: 12.5

  35. {530,1045,955,897,570,725,664,479,520,576,646,941,452,704,818,687,703,589,588,504,900,690,448,573,736,819,514,478,964,1049,795,699,980,735,391,885,347,989,828,829,578,412,389,745,563,650,676}

    171

    Returns: 43.83333333333334

  36. {93422,93514,93724,93579,93464,93465,93371,93733,93631,93355,93582,93352,93370,93366,93248,93655,93568,93724,93622,93723,93420,93722,93341,93268,93631,93308,93730,93384,93316,93582,93630,93416,93735,93306,93674,93672,93609}

    100000

    Returns: 0.010883133543558188

  37. {133688388,208814873,139173046,138368101,116850455,58279275,71581508,187642593,71880890,45627151,81008835,226887172}

    5

    Returns: 8.8061237E7

  38. {893545,390327,386079,260319,700159,808438,853745,754193,710564,725067,233345,173424,187678,630818,688470,850363,688048,615756,199894,488677,157828,848050,746965,876043,96610,284191,388038,204733,187052,677082,130643,387830,516838,525205,698211,532109,853128,283604,819173,266934,611856,348489,739188,535786}

    6640

    Returns: 44.4750402576492

  39. {52440,52439,52439,52439,52441,52442,52439,52439,52442,52439,52442}

    16

    Returns: 1.5

  40. {9675116,9678709,2972531,8466812,7677997,4796386,5159827,5621682,8264418,5302557,3695413,3092194,4552568,4517286,6102018,6461121,5683354,3084725,7796480,3467560,7504406,5678211,3500005,8566644,6691536,9301093}

    8

    Returns: 4531875.0

  41. {640637081,640637082}

    397

    Returns: 0.005025125574320555

  42. {1634891,1258083,691268,2106779,949933,588833,2758815,1176411,905057,379153,2519527,2907031,2004454,1132105,824007,469408,839389,613862,1086752,1486577,1074765,224681,365663,1362101,1781851,1352091,2599815,1681120,2355910,2914604,1340636,2640115,1083205,659738,1038414,1152505,124350,1182579,2786615,1106470,2156154}

    100000

    Returns: 0.40577247389899185

  43. {5577,5591,5596,5583,5595,5591,5599,5579,5591}

    8

    Returns: 22.0

  44. {9,7,9,10,8,10,10,7,10,10,9,8,10,7,8,7,9,7,9,7,7,9,10,8,9,8,8,7,9,7,7,7,9}

    11

    Returns: 3.0

  45. {10,12,12,10,10,9,10,10,11,10,10,10,12,11}

    652

    Returns: 0.0

  46. {58343,312,56576,5851,16338,58039,43842,3469,24531,11711,54878,19340,41125,57069,2608,38983,49844,18497,61355,53568,47256,1034,56554,13908,31792,22017,49621,59416,42071,35698,9068,44639,45638,46229,8371}

    15

    Returns: 43530.0

  47. {10,11,6,3,8,2,11,7,7,8,3,5,9,2,4,4,7,6,11,10,11,5,11,3,3,9,6}

    4588

    Returns: 0.0

  48. {74374,74378,74375,74375,74378,74377,74377,74376,74376,74374,74376,74374,74375,74374,74377,74374,74374,74377,74375,74376,74377,74375,74378,74374,74375,74378,74377,74378,74377,74376,74375,74376,74378,74378,74376,74374,74376,74374,74378,74376,74374,74378,74374,74377,74378}

    30

    Returns: 4.0

  49. {5360950,5283427,5302194}

    5

    Returns: 38761.5

  50. {382467279,188433726,103322671,247885910,200967605}

    2

    Returns: 9.7644934E7

  51. {324258,328359,193963,331300,342894,38357,34372,414304,308476,177702,78075,285812,163612,371025,218540,15307,15145,200103,318176,242599,262796,235903,152100,91055,156568,260111,89994,410305,346620,179402,194679,94639,213055,186971,34894,153027,412038,293111,374137,297558,30589,275627,314497,232093,21270,216936,170748,51590}

    1205

    Returns: 1378.4571428571435

  52. {8506852,8506852,8506855,8506854,8506855,8506855,8506854,8506856,8506853,8506855,8506855,8506852,8506853,8506852,8506856,8506852,8506855,8506852,8506855,8506856,8506853,8506855,8506856,8506853,8506852,8506853,8506856,8506855,8506856,8506853,8506854,8506854,8506856,8506856,8506856,8506852,8506855,8506856,8506855,8506854,8506853,8506856,8506855,8506853,8506852}

    73301

    Returns: 0.0024554941683163634

  53. {2372,3533,2224,6182,4906,5175,1824,3761,1886,5041,1549,2094,3329,4818,1236,2480,4588,3668,5007,4074,5554,2255,6130,5612,2194,4084,4780,1927,3640,3370,2298,3970,1049,3141,1221,2738,3075,5628,1323,3494,3201,5083,1239}

    7

    Returns: 3992.0

  54. {2397491,5461562,26639409,52480204,3616992,16806675,47905668,24896680,44912601,1394807,35634828,27609509,2617074,46735137,125958,17674320,1329260,21712283,10301691,4732401,25893563,13152217,31259691,9785882,5854989,52891586,37616234,42987805,25175878,23127985,19539963,38430469,46213225,6238879,43356366,746394,31416949,46679474,14262989,28420975,24212391,18140057,38802732,19548496,50817512,26568403,38943067}

    11

    Returns: 3.8676774E7

  55. {410039,410045,410034,410032,410045,410041,410030,410036,410032,410032,410040,410033,410028,410033,410035,410044,410039,410034,410032,410038,410037,410038,410037,410033,410037,410034,410041,410029,410030,410031}

    100000

    Returns: 0.00509898020396804

  56. {81903519,81936146,81944126,81920211,81890132,81938123,81922241,81887076,81892478,81945207,81891680,81908686,81926952,81917855,81884110,81918738,81921518,81899810,81944393,81918200,81918566,81912805,81913194,81936174,81886919,81945644,81893128,81917413,81914983,81926898,81890943,81924744,81933168,81898122,81936214,81890597,81893055,81902149,81904807,81920914,81936682}

    532

    Returns: 4733.384615384974

  57. {928143320,747497605,65274849,595601562,788812503,124704964,637427825,4963931,135628265,815452656,513471785,935585367,813703268,337631346,922923758,534193530,949144149,775176253,506323223}

    25898

    Returns: 1095.0821316614165

  58. {45691,5436,89948,30021,14787,33748,21145,89097,35587,71868,87375,40159,93079}

    1

    Returns: 84512.0

  59. {87,87,89,87,90,88,87,89,90,87,90,88,87,88,89,88,88,90,88,88,90,89,90,90,90,88,89,87,89,90,88,89,89,88,90}

    9

    Returns: 3.0

  60. {3422592,3174777,3543766,3132815,3517087,3283732,3177866,3132594,3341501,3328550,3516815,3539516,3254481,3170259,3559819,3190716,3182996,3258023,3298400,3226312,3363435,3367518,3493532,3359127,3567048,3515697,3483112}

    4

    Returns: 434454.0

  61. {366383,528664,319183,544044,265961,328486,468721}

    7

    Returns: 106369.5

  62. {66057711,66056973,66056293,66056067,66056851,66055615,66056898,66056648,66057036,66056929,66058102,66058179,66056361,66057638,66055666,66058074,66055931,66056174,66056286,66057540,66056387,66057098,66056986,66055595,66057473,66056731,66056948,66058048,66056994,66056295,66056583,66056731}

    529

    Returns: 152.0

  63. {15,12,12,11,14,12,13,18,18,12,11,11,11,13,12,13,18,11,14,13,18,17,11,12,13,12,12,12,17,12,14,14,15,18,12,17}

    99

    Returns: 0.75

  64. {65184117,65184719,65181267,65183376,65177297,65178377,65181427,65176429,65182844}

    28

    Returns: 2072.5

  65. {86620453,86620429,86620477,86620452,86620457,86620487,86620453,86620428,86620479,86620495,86620475,86620426,86620458,86620460,86620464,86620498,86620434,86620494}

    100000

    Returns: 0.012958963283381308

  66. {61790,142925,115024,134617,111021,107809,101595,131778,120857,103023,108985,83307,139198,98887,114612,118099,103146,65641,107680,125540,69544,137936,143844,112534,143020,87270,140920,80061,133765,100665,135094,97260,94733,79988,102689,77032,72604,130925,115901,104344,70350,100088,115978,113267,70811,64328,123496,114270,108066}

    100000

    Returns: 0.022148722550305422

  67. {4082,8099,4288,2337,2411,6855,8199,5615,4150,599,487,974,1722}

    283

    Returns: 21.77000000000001

  68. {2032113,5112438,3715652,2975551,3453622,3844669,2051226,1983277,452968,4257740,1696706,5066009,4221857,505919,3846567,1697062,3222755,1826631,1656634,4602301,3699480,3023650,2176160,1993562,5336403,661743,4957928,3648699,5487555,485458,727981,4753185,5389926,2750656,5277295,2993856,1244043,3663053,1956197,955177,5162614,5203003}

    79

    Returns: 829221.0

  69. {738565,1284884,753878,793501,1118794,1274071,757984,889019,772949,1078995,867214,1033330,1036508,1283807,1295674,1129633,1149176,1258824,1023569,959144,1090502}

    100000

    Returns: 0.029908052340886115

  70. {41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464, 5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436, 32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895, 5447, 21726, 14771, 11538, 1869, 19912, 25667, 26299, 17035, 9894, 28703, 23811, 31322, 30333, 17673, 4664, 15141, 7711, 28253, 6868 }

    1337

    Returns: 528.4909090909091

  71. {804289384, 846930887, 681692778, 714636916, 957747794, 424238336, 719885387, 649760493, 596516650, 189641422, 25202363, 350490028, 783368691, 102520060, 44897764, 967513927, 365180541, 540383427, 304089173, 303455737, 35005212, 521595369, 294702568, 726956430, 336465783, 861021531, 278722863, 233665124, 145174068, 468703136, 101513930, 801979803, 315634023, 635723059, 369133070, 125898168, 59961394, 89018457, 628175012, 656478043, 131176230, 653377374, 859484422, 914544920, 608413785, 756898538, 734575199, 973594325, 149798316, 38664371 }

    100000

    Returns: 389.6466434101749

  72. {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, 1000000000, 1000000000, 1000000000, 1000000000 }

    100000

    Returns: 49996.50012499375

  73. {999999951, 999999952, 999999953, 999999954, 999999955, 999999956, 999999957, 999999958, 999999959, 999999960, 999999961, 999999962, 999999963, 999999964, 999999965, 999999966, 999999967, 999999968, 999999969, 999999970, 999999971, 999999972, 999999973, 999999974, 999999975, 999999976, 999999977, 999999978, 999999979, 999999980, 999999981, 999999982, 999999983, 999999984, 999999985, 999999986, 999999987, 999999988, 999999989, 999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998, 999999999, 1000000000 }

    100000

    Returns: 0.024487756134476513

  74. {2259002, 735898756, 551889953, 285382391, 654055418, 419843253, 534051754, 860486221, 548490232, 176291683, 658886606, 235306259, 407431435, 647121656, 66631921, 475324005, 222646685, 972843553, 948441627, 49073379, 891155670, 504342281, 286079947, 876628264, 1672327, 29675289, 967177097, 529152607, 353990488, 963411166, 446966056, 807619055, 369942420, 992995849, 176304538, 507544975, 685193583, 754141443, 574494894, 999323633, 305061612, 321542038, 110928411, 212707222, 973993924, 690742753, 530836999, 349157715, 733907062, 317820760 }

    98797

    Returns: 3654.083333333314

  75. {999999, 999997, 999996, 999995, 999993, 999991, 999981, 999982, 999983, 999984, 999985, 999986, 999987, 999988, 999989, 999971, 999973, 999975, 999977, 999979, 999961, 999963, 999965, 999967, 999969, 999951, 999953, 999955, 999957, 999959, 999941, 999943, 999945, 999947, 999949, 999931, 999933, 999935, 999937, 999939, 999921, 999923, 999925, 999927, 999929, 999911, 999913, 999915, 99991, 24647 }

    100000

    Returns: 0.06267605633809126

  76. {3527600, 77401585, 62824094, 47902791, 35015484, 68800909, 8029962, 86256195, 62517896, 67834857, 80171318, 36760831, 95337876, 90425861, 11915298, 49758331, 44289376, 88290529, 47418062, 75546039, 67274732, 26272125, 43201082, 75780531, 44964408, 69681625, 16175974, 61472111, 3003716, 86638325, 430162, 68141291, 60847632, 48521425, 28650750, 49606695, 35903132, 63719789, 29995114, 75811875, 93145576, 95405769, 2736534, 71520223, 56633844, 58258661, 83689602, 78442075, 75280064, 27576257 }

    100000

    Returns: 98.86311004374147

  77. {226539881, 983746533, 574839920, 844665771, 384990201, 384990201, 498590230, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    100000

    Returns: 127.96677899226779

  78. {1000000, 1000001, 1000002, 1000003, 1000004, 1000005, 1000006, 1000007, 1000008, 1000009, 1000010, 1000011, 1000012, 1000013, 1000014, 1000015, 1000016, 1000017, 1000018, 1000019, 1000020, 1000021, 1000022, 1234567, 1234568, 1234569, 1234570, 1234571, 1234572, 1234573, 1234574, 1234575, 1234576, 1234577, 1234578, 1234579, 1234580, 1234581, 1234582, 1234583, 1234584, 1234585, 1234586, 1234587, 1234588, 1234589, 1234590, 1234591, 1234592, 1234593 }

    100000

    Returns: 0.01336272780724812

  79. {999999950, 999999951, 999999952, 999999953, 999999954, 999999955, 999999956, 999999957, 999999958, 999999959, 999999960, 999999961, 999999962, 999999963, 999999964, 999999965, 999999966, 999999967, 999999968, 999999969, 999999970, 999999971, 999999972, 999999973, 999999974, 999999975, 999999976, 999999977, 999999978, 999999979, 999999980, 999999981, 999999982, 999999983, 999999984, 999999985, 999999986, 999999987, 999999988, 999999989, 999999990, 999999991, 999999992, 999999993, 999999994, 999999995, 999999996, 999999997, 999999998, 999999999 }

    100000

    Returns: 0.024487756134476513

  80. {539645949, 415791362, 736319818, 285134547, 773398106, 79803624, 855460762, 60348785, 917573515, 333984967, 406804997, 208837623, 256756413, 423094965, 565842274, 429009294, 790285335, 902813102, 218404105, 189691765, 63152157, 154859016, 749389956, 89388712, 870407009, 29642040, 39139927, 733767931, 632725283, 924721273, 958860174, 848413405, 708293017, 514857468, 504007296, 551372308, 913666878, 696937961, 202037981, 117528169, 213765002, 830555887, 468430117, 654331467, 38644959, 152524955, 242381649, 485918891, 992225055, 811111018 }

    100000

    Returns: 468.11680613667704

  81. {50, 500, 5000, 50000, 500000, 200, 20000, 20000, 12392013, 21391312, 12292, 1119948, 2999909, 2911, 1237, 1000000000, 123, 1, 1923, 4857, 222, 4882, 998872, 1472, 10018, 108, 177, 199999, 22777, 33213, 321321321, 4872, 289888, 336, 33990, 47671, 28571, 4008, 47171, 55554, 2717, 9271, 273654, 19972, 4517171, 9427, 10181, 28881, 194727 }

    5000

    Returns: 272850.2960436562

  82. {892753, 1000000000, 99998743, 987451123, 49753134, 984513, 938475913, 98345834, 349875, 95871, 93847589, 983745245, 983472345, 938475345, 983745335, 212364885, 234687234, 892753, 1000000000, 99998743, 987451123, 49753134, 984513, 938475913, 98345834, 349875, 95871, 93847589, 983745245, 983472345, 938475345, 983745335, 212364885, 234687234, 892753, 1000000000, 99998743, 987451123, 49753134, 984513, 938475913, 10, 349875, 95871, 93847589, 983745245, 983472345, 938475345, 983745335 }

    40000

    Returns: 556473.0272676683

  83. {262213616, 246598425, 252626246, 436614666, 235899997, 253126126, 346246166, 221612, 265126216, 896898989, 262213616, 246598425, 252626246, 436614666, 235899997, 253126126, 346246166, 221612, 265126216, 896898989, 262213616, 246598425, 252626246 }

    25216

    Returns: 61904.016883116856

  84. {1, 4, 10, 31, 43, 74, 101, 201, 231, 344, 387, 399, 400, 410, 420, 422, 434, 480, 500, 567, 594, 600, 623, 700, 800, 900, 999, 43, 74, 101, 201, 231, 344, 387, 399, 400, 410, 420, 422, 434, 480, 500, 567, 594, 600, 623, 700 }

    100000

    Returns: 0.0

  85. {1000000000, 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, 999999967, 999999966, 999999965, 999999964, 999999963, 999999962, 999999961, 999999960, 999999959, 999999958, 999999957, 999999956, 999999955, 999999954, 999999953, 999999952, 999999951 }

    100000

    Returns: 0.024487756134476513

  86. {13, 69, 41, 37, 80 }

    27

    Returns: 1.4666666666666668

  87. {1681, 41030089, 40119556, 2250000, 67450561, 47244176, 31744484, 61892164, 26949444, 98487296, 32547025, 92141025, 42004961, 83147929, 99221521, 241081, 8970025, 42611364, 23299929, 29550096, 49176881, 13276816, 15225604, 23409, 85264, 53313924, 3491241, 50288656, 88799524, 95811025, 29669809, 72019076, 18182441, 33125444, 3493161, 96487744, 58794889, 91637401, 90191225, 97891236, 23862209, 66963721, 81067684, 20090889, 12334929, 21752896, 29249881, 59459521, 98232009, 47169424 }

    100000

    Returns: 21233.90092378753

  88. {3112, 54325, 123, 435, 13532, 1345423, 31, 24, 56, 8734, 3112, 54325, 123, 435, 13532, 1345423, 31, 24, 56, 8734, 3112, 54325, 123, 435, 13532, 1345423, 31, 24, 56, 8734, 3112, 54325, 123, 435, 13532, 1345423, 31, 24, 56, 8734, 3112, 54325, 123, 435, 13532, 1345423, 31, 24, 56, 8734 }

    100000

    Returns: 47.269361161139955

  89. {10000, 10001 }

    1

    Returns: 1.0

  90. {157010962, 361129695, 461134522, 284482012, 288217717, 263153678, 358845672, 481164138, 377069527, 34718949, 533514739, 394911717, 52750836, 520129014, 49044456, 144655039, 507148491, 119400500, 262894679, 224551693, 642333, 511080310, 499630805, 147017224, 440927987, 363219192, 502635387, 105904526, 338613269, 116738521, 536669540, 290598562, 446492308, 125334942, 215632178, 535938023, 70675265, 204576941, 350287754, 307472425, 159602739, 53469907, 299343763, 96009429, 286419781, 11471295, 488308091, 463487100, 261456021, 3734405 }

    996

    Returns: 1.3159423615384616E7

  91. {1, 2, 2, 3, 4, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 }

    100000

    Returns: 0.0

  92. {1000000000, 999999999, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    100000

    Returns: 4.997501382604241E-4

  93. {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, 353, 36, 37, 38, 39, 40, 41, 423, 43, 44, 45, 46, 47, 48, 49, 50 }

    100000

    Returns: 0.0

  94. {289384, 930887, 692778, 636916, 747794, 238336, 885387, 760493, 516650, 641422, 202363, 490028, 368691, 520060, 897764, 513927, 180541, 383427, 89173, 455737, 5212, 595369, 702568, 956430, 465783, 21531, 722863, 665124, 174068, 703136, 513930, 979803, 634023, 723059, 133070, 898168, 961394, 18457, 175012, 478043, 176230, 377374, 484422, 544920, 413785, 898538, 575199, 594325, 798316, 664371 }

    100000

    Returns: 1.0284313725490506

  95. {1, 2, 23, 34, 545, 565655, 3434, 3434, 34343, 34343434, 3434343, 3434343, 3434343, 343434343, 3434343, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 50000, 50000, 50000, 50000, 90000, 90000, 90000, 90000, 125000, 125000, 125000, 450001, 450001, 450001, 1212, 1212, 1212, 8888, 8, 8, 8888, 565656, 5656565, 43343, 35656, 6783, 5656, 1567 }

    100000

    Returns: 73996.33609590055

  96. {648027539, 701334894, 747069242, 320405652, 114611276, 560152603, 689166560, 865680268, 775543705, 529131117, 871324535, 511202167, 909269196, 803775365, 158226781, 803564037, 604557856, 590715988, 452198626, 373256778, 679704855, 793960829, 803965770, 534058792, 897573514, 853845072, 975733440, 960640012, 918088315, 447467499, 756377625, 430890995, 531138863, 903916113, 184861505, 900460957, 783542205, 336874010, 208401143, 848536986, 298746951, 790473232, 451960008, 366444733, 738834819, 453377839, 193690532, 936430200, 522040292, 525232876 }

    100000

    Returns: 203.37923664122354

  97. {10, 29 }

    2

    Returns: 0.3333333333333339

  98. {999982981, 927863971, 92371723, 923964123, 237618623, 192786378, 396261371, 957637291, 938497263, 132461623, 125125431, 23423412, 3472837, 27381723, 7123, 781, 12387, 317238, 12378, 21387, 12378, 234870, 234780, 2378, 12738, 83745, 237804, 127830, 23578, 1234780 }

    99999

    Returns: 59026.37413424817

  99. {237530862, 242098763, 241358022, 249876541, 233456788, 258395059, 241975306, 247160492, 252098763, 250740738, 240617282, 238765430, 248765430, 243580245, 253456788, 251975306, 241604936, 239629627, 252716047, 238765430, 239012344, 247160492, 243456788, 248765430, 243086418, 252592590, 241851850, 255432096, 255679010, 238518516, 252222220, 251481479, 242469134, 249876541, 249259257, 248271603, 255802467, 249012343, 249629627, 252469134, 248765430, 255679010, 251604936, 242716047, 253580245, 233209874, 245925924, 251111109, 243333331, 249135800 }

    100000

    Returns: 5.093952786410227E-4

  100. {1000, 3000, 5000, 7000, 9000, 11000, 1300, 1700, 1900, 10000, 110, 130, 150, 170, 190, 1110, 1130, 1170, 1190, 100000, 210, 230, 250, 270, 290, 2110, 2130, 210, 2190, 100000, 310, 330, 350, 370, 390, 3110, 3130, 3170, 3190, 100000, 410, 100, 1000, 10000, 100000, 100000, 100000, 100000, 9999 }

    99999

    Returns: 9.999999999994458E-4

  101. {43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023, 43289023 }

    99999

    Returns: 0.0

  102. {1, 3, 5, 7, 9, 11, 13, 17, 19, 10000, 11, 13, 15, 17, 19, 111, 113, 117, 119, 10000, 21, 23, 25, 27, 29, 211, 213, 217, 219, 10000, 31, 33, 35, 37, 39, 311, 313, 317, 319, 10000, 41, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 999999999 }

    100000

    Returns: 10109.7122895708

  103. {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, 1000000000 }

    50000

    Returns: 19998.60000799984

  104. {12405160, 10000000, 46551765, 46501785, 12301584, 48114975, 24401105, 22513505, 41511165, 11411115, 23405165, 48005175, 30010545, 88080095, 30114065, 69080709, 90718979, 45878645, 12304156, 12341567, 12345607, 12345678, 30205011, 21011401, 43000201, 50430021, 65430021, 44014041, 11520061, 99999910, 88899988, 45600175, 10101025, 62010115, 12340155, 33301121, 45601789, 34560178, 78965546, 11451012, 10254135, 10110145, 10811495, 77777777, 67676767, 76767676, 12305281, 99779977, 12350107, 21541506 }

    100000

    Returns: 20.295032181249553

  105. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 999999999 }

    100000

    Returns: 4.997501382604241E-4

  106. {44227194, 700639607, 562310850, 399664033, 977341964, 574844297, 282528160, 86489368, 660423302, 831443987, 385582771, 654529074, 588898824, 566449165, 556086590, 477224841, 591067307, 844353688, 245081797, 881209601, 534013216, 296555642, 205606354, 126247407, 376344673, 409634692, 548420954, 155797104, 353497343, 87743607, 403134816, 30311014, 128553879, 393645460, 153444791, 124598800, 909413987, 178729919, 264754916, 7898181, 601278956, 822673999, 150493986, 515869261, 738357469, 474214261, 833146750, 757106524, 336478451, 519797521 }

    18981

    Returns: 17070.350383631652

  107. {1, 1000000000 }

    1

    Returns: 4.99999999E8

  108. {5, 5, 5, 5, 5, 6 }

    6

    Returns: 0.5

  109. {2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 18, 19, 23, 34, 35234, 3214432, 12345, 565467, 235523324, 235623 }

    100000

    Returns: 2393.7940329783232

  110. {4, 4, 5 }

    9

    Returns: 0.08333333333333326

  111. {1000000000, 999999999, 987654321, 123456789, 389783, 4475757, 3453345, 4535434, 13476, 45467, 213446 }

    79793

    Returns: 25675.201941899613

  112. {412, 1244, 12, 541, 25, 124, 12, 512, 5, 12, 512, 4, 321, 54, 125, 12, 412651, 2143215, 1, 143214, 512, 125, 21, 412, 512351, 215215, 12, 512, 512, 5213, 5164125, 215161, 1562151, 125, 21512, 51, 25, 125, 12, 5, 15, 12, 551, 125, 125, 12, 512, 5151, 51521, 1 }

    50000

    Returns: 208.0971817298348

  113. {45871346, 9998601, 58858165, 73585138, 56508640, 55705684, 5881471, 35488549, 86182778, 49611882, 71183869, 17369417, 83819071, 28946063, 14514027, 39962043, 885360, 46230713, 66392090, 8373405, 72977266, 6360518, 58445875, 15726513, 96264064, 67950472, 88437182, 29540500, 10667800, 95467359, 6942902, 93685852, 86985934, 84379298, 57517099, 93427814, 65106918, 36543286, 13912997, 37263266, 47282116, 71502052, 84745325, 16773628, 78095804, 72269694, 37773551, 74366541, 64720519, 51940156 }

    100000

    Returns: 52.51437553061987

  114. {1, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 100000 }

    100000

    Returns: 479845.4491362764

  115. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    100000

    Returns: 0.0

  116. {1, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    100000

    Returns: 489954.9039686428

  117. {1945984, 394237, 84623, 6653, 124667, 12338, 999999, 664, 2213, 12377, 1245, 67234, 8633, 122678, 12588, 23, 2333, 10058458, 584874, 1226, 1226, 1288, 121244, 99565, 35502, 6533, 23446, 766711, 4841, 2334, 6744, 9944, 34462, 34566, 3663, 1774, 6733, 32234, 85542, 98433, 95533, 3344, 1247, 88534, 1123, 7344, 954544, 346666, 8443, 266445 }

    99997

    Returns: 152.896369613878

  118. {1, 2, 2 }

    1

    Returns: 1.0

  119. {943351957, 968036878, 917603339, 944313882, 938102501, 962448755, 957313995, 902900862, 940092631, 962109168, 926332822, 912418653, 963999088, 934225048, 904810687, 969202642, 944404079, 991233810, 927566501, 985506568, 908372191, 972437876, 986009830, 967865555, 911015571, 940580598, 904770527, 968994308, 938734894, 916801099, 910222909, 999157963, 909823614, 902405506, 933091954, 907953093, 927122988, 960892101, 912329036, 972436367, 962415390, 958667875, 992444687, 952538371, 977243403, 987893981, 931485889, 999700085, 909842191, 919897606 }

    100000

    Returns: 204.3913794553373

  120. {398884122, 148899920, 790078480, 369899775, 391792263, 298552011, 68041389, 678845583, 972835167, 328443443, 895139446, 31040594, 467708059, 600294411, 640064573, 649495634, 95340448, 561454957, 698754639, 93834274, 245951243, 887998390, 962980176, 964500898, 156038634, 957449416, 895280903, 33530190, 827774058, 25108616, 41942771, 687619690, 126537481, 47487160, 46988613, 916497439, 830504385, 586242126, 884709487, 62475608, 366940337, 516680112, 451314094, 184797581, 30862200, 599367621, 178859982, 881778840, 289107794, 87096337 }

    100000

    Returns: 724.7278577995603

  121. {208095, 868273, 202641, 853349, 953685, 360412, 273754, 290142, 218713, 289585, 890795, 314265, 941709, 326072, 265570, 7837, 569352, 308013, 988422, 588349, 482307, 353466, 890971, 34463, 380780, 398743, 851269, 740013, 170719, 237060, 944121, 133785, 240622, 767587, 308678, 29075, 766765, 352465, 481074, 118196, 409007, 461882, 763008, 459020, 822921, 660723, 729975, 875149, 380712, 911504 }

    99999

    Returns: 0.5979601518026527

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: