Statistics

Problem Statement for "MarblePositioning"

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Everybody loves geometry, so here is a geometry problem. You have a few marbles of possibly different sizes. You are given a int[] radius that describes the marbles: each element of radius is the radius of one of your marbles.

You want to place all marbles onto a straight line that is drawn on the table. Clearly, this makes the problem two-dimensional: we can just view the marbles as circles that will all be touching the line from above. Of course, the marbles cannot overlap, so in our problem no two circles are allowed to overlap. Note that you may place the marbles onto the line in any order, you do not have to preserve the order in which they are given in radius.

Additionally, you want to pack the bottoms of the marbles as close together as possible. More precisely: For each marble consider the point where it touches the line. Compute and return the smallest possible distance between the farthest two of those points. (That is, if you imagine the line as going from the left to the right, your task is to minimize the distance between the leftmost and the rightmost of the points where the circles touch the line.)

Definition

Class:
MarblePositioning
Method:
totalWidth
Parameters:
int[]
Returns:
double
Method signature:
double totalWidth(int[] radius)
(be sure your method is public)

Notes

  • The returned values must have an absolute or relative error less than 1e-9.

Constraints

  • radius will contain between 2 and 8 elements, inclusive.
  • Each element of radius will be between 1 and 1000000000 (10^9), inclusive.

Examples

  1. {1, 2}

    Returns: 2.8284271247461903

    One of the best ways to place the marbles is the following one:

  2. {1,1000000000}

    Returns: 63245.553203367585

  3. {7,7,7}

    Returns: 28.0

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

    Returns: 50.58155219373389

  5. {1000000000,200000000,300000000,400000000,500000000,600000000,700000000,800000000}

    Returns: 6.53173138056799E9

  6. {10, 20, 30}

    Returns: 62.92528739883945

  7. {100, 100,11,11,25}

    Returns: 200.0

  8. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 1.4E10

  9. {1000000000,1000000000,250000000,1000000000,250000000,1000000000,250000000,99000000}

    Returns: 6.0E9

  10. {1,999950884,1}

    Returns: 63246.0

  11. {1, 100000000}

    Returns: 20000.0

  12. {1,94908557}

    Returns: 19484.20457704137

  13. {660005,344393,598163,715234,52464,87578}

    Returns: 3157014.540288346

  14. {911673,825708,535941,710852,549483,809046,604659}

    Returns: 8022165.982667927

  15. {732606,852428,207585}

    Returns: 1621255.145187647

  16. {381165,519721}

    Returns: 890167.2988039944

  17. {19611,674161,702765}

    Returns: 1376628.8608989716

  18. {147195,982716,939258,68116,52334}

    Returns: 1921482.6199869725

  19. {376180,475087,782672,278462,936408,291909,462114}

    Returns: 5118635.312564134

  20. {218307,818795,786032,98052}

    Returns: 1687785.9403042246

  21. {903214,252429,550970,58607,889016,695517}

    Returns: 4430821.778043712

  22. {668666,845064,224027,874690,394297,141381,530656,141738}

    Returns: 4926023.100913776

  23. {672956,37121,548896,138004,551719,185703,682747,298898}

    Returns: 4161722.740292447

  24. {699999,958267,190583,513298,447484,137280,291316,232286}

    Returns: 4532569.191109305

  25. {651330,514779,913115,336660,900413,655728,916170,671158}

    Returns: 8924151.169512404

  26. {162071,784129,457990,137767,35139,201263,585064,558197}

    Returns: 3670933.065883142

  27. {516745,53297,801112,959401,220075,571141,327418,494234}

    Returns: 5548350.130831172

  28. {514413,192326,689044,13515,460874,589670,136175,259540}

    Returns: 3847414.8676088667

  29. {894110,554627,619503,100922,367125,59370,940926,873953}

    Returns: 6360707.354945734

  30. {322163,459196,628399,411734,379755,611674,586285,728148}

    Returns: 6688266.533853211

  31. {307289,477567,10092,651049,280399,335056,944680,591716}

    Returns: 5195277.807116896

  32. {401622118,479481651,432779539,422969728,753730372,831790183,956345956,446596892}

    Returns: 7.373901090641952E9

  33. {257940314,193804283,28080954,323111452,746668911,801115143,325331971,301950763}

    Returns: 3.9969092289770412E9

  34. {185063802,304201708,432762862,737163305,141388679,521789659,767578225,423938433}

    Returns: 4.885495980795207E9

  35. {879958222,205740888,279137910,725660632,835761614,656087721,291115281,135266853}

    Returns: 5.319102386494895E9

  36. {24069029,627843741,389400354,941605915,28695821,754440438,501214494,294651927}

    Returns: 5.003215702425909E9

  37. {808573108,302775648,528765193,999782916,798312987,354151201,352702188,632735577}

    Returns: 7.18227862850116E9

  38. {906227351,124657065,994679128,857731976,396270710,998555420,618803501,360806911}

    Returns: 7.720539089780999E9

  39. {409972987,149093171,727064056,174544906,911281675,975101241,305698222,89406733}

    Returns: 4.510526391646409E9

  40. {435474466,156588523,973875344,395805100,21037622,854786896,386449832,924828031}

    Returns: 5.642087141976454E9

  41. {420367537,840457507,705696354,594891945,643497097,97025820,364107167,868772171}

    Returns: 6.900940200833332E9

  42. {83005151,957472525,717457809,55146061,205268979,926530186,866058779,316724802}

    Returns: 5.365080352452948E9

  43. {882692678,536432200,778376668,456602640,575121377,385565867,413574698,205272217}

    Returns: 6.3780904423917885E9

  44. {165690463,96189913,453777666,215483195,813968097,434956971,514404814,499427366}

    Returns: 4.421774435098757E9

  45. {62823017,323670170,647962839,530045917,31806911,764215698,632370896,446676061}

    Returns: 5.106558894464074E9

  46. {103431124,277249621,646082589,980605889,36533708,825863061,878239723,602692320}

    Returns: 6.163862591556757E9

  47. {505693082,447551533,523944842,577504008,382636724,793646419,497392982,343190688}

    Returns: 6.626965022831949E9

  48. {150365767,531068349,569778789,58490271,223883778,146535393,564709446,986074595}

    Returns: 3.930541025528035E9

  49. {513907719,172908168,129723465,297959468,135403233,897473306,557456238,82638968}

    Returns: 3.228472428521619E9

  50. {946935409,296003813,421660197,449961088,585164918,417598792,687880488,946411327}

    Returns: 7.181879597017124E9

  51. {902204985,414705410,698910380,699865314,966011557,98384542,780725147,60999703}

    Returns: 6.8692058853995285E9

  52. {2395,26850,6630,5447,8653,26000,3635,24269}

    Returns: 119329.2316821737

  53. {19996,5152,10227,13747,1,3189,11531,17553}

    Returns: 110827.33309213359

  54. {29885,28869,840,8650,1437,524,7979}

    Returns: 79104.12923590222

  55. {6327,23712,27299,2549,23843,2345,1,17185}

    Returns: 131741.69436835495

  56. {10206,873,19128,11383,4614,12913}

    Returns: 77800.1569488481

  57. {21907,9513,13400,25714,1950,26915,8451,26283}

    Returns: 191535.06961700282

  58. {8718,1022,22221,22735,12551,28409}

    Returns: 126496.68586144518

  59. {12099,8161,25733,23568,8356,4573,2859}

    Returns: 100935.16374007435

  60. {8713,19697,1,3517,21513,29693}

    Returns: 99539.97485694889

  61. {9206,1,1,18880,3893}

    Returns: 29119.539119220797

  62. {207589464,9344249,520021416,553942296,148327041,55456809,980628225}

    Returns: 2.6882331194535584E9

  63. {82336476,811736081,22694696,565011900,16063064,282776856}

    Returns: 1.757637546517231E9

  64. {65495649,260983025,174344616,118503996,476591561,967395609,435681129,65819769}

    Returns: 2.831023135375623E9

  65. {2603996,468158769,337639625,853573656,47264625}

    Returns: 1.8688435043133705E9

  66. {173158281,159465384,285744216,432763809,332915516,800889000,853807400}

    Returns: 3.8085333350698752E9

  67. {270930600,285710409,498270684,176241,79976249}

    Returns: 1.2912829057691617E9

  68. {418242401,663473564,190494204,50750376,319356}

    Returns: 1.275548677290183E9

  69. {282239000,587237289,710381409,860834600,871356,815044401,947407400}

    Returns: 6.229033415764902E9

  70. {621005400,668686881,186212316,2213144,639684264,76176984}

    Returns: 2.6464069513139515E9

  71. {24729729,348717276,248723441,580423464,47540025,95941025,6225}

    Returns: 1.369924352005999E9

  72. {20952,220347864,733869808,776150559,219255227,45656,746141643}

    Returns: 3.2425115287319627E9

  73. {8261,315820241,215999000,420875,122762473,1294029,385827352,531440000}

    Returns: 2.0043870261396475E9

  74. {136589875,523605616,264608288,111979168,291433247}

    Returns: 1.607813880684546E9

  75. {3175523,217080801,96070912,825292672,5450776}

    Returns: 8.519838456625227E8

  76. {656233909,304820217,846589536,3651264,901427696,88715536}

    Returns: 3.433597379975623E9

  77. {70443997,496792088,557440767,2862288,681471000,206424071,145530576,313432}

    Returns: 2.486513308192616E9

  78. {224754712,13143256,379502424,7999000,476378541,976190488,89914392}

    Returns: 2.3712970161967654E9

  79. {70443997,911673,3913,11088567,633838779}

    Returns: 4.226115807516858E8

  80. {1770561,50242409,788888024,3111136,442449728}

    Returns: 1.1815977177385838E9

  81. {54438939,403582419,176557481,530441,198154287,197136368,22424768,177503328}

    Returns: 1.6562157615584803E9

  82. {1678868,13845076,207359378,9440,116986051,59969089,157352699}

    Returns: 6.618964496410105E8

  83. {442050892,2313563,168895064,96060335,88528910,31640290,130561,104498}

    Returns: 8.348311239589365E8

  84. {37777,45211416,200533708,607573452,57290189}

    Returns: 6.981087514475664E8

  85. {22666667,454372826,671898153,6868,533794057,332151179,25411270,15753598}

    Returns: 2.7067609324709935E9

  86. {45212140,146410029,126248151,9150226,68575938,533794727,352276096,116986227}

    Returns: 1.5040345570018988E9

  87. {4878920,15753185,65609798,260144743,260143714,352274519,35154002}

    Returns: 1.125737056700802E9

  88. {12116514,50787,38142,9834696,200533215}

    Returns: 1.1065082969869405E8

  89. {25412309,519885626,312901479,228887026,84935426,442051055,607573148,454371633}

    Returns: 3.8376264520758686E9

  90. {15752388,68574856,74804426,246,221533598,614208,62741342,7312270}

    Returns: 5.102211623031318E8

  91. {924117,112550252,285610292,22667903,207359077}

    Returns: 6.641210475394449E8

  92. {6435791,184527459,6436783,992437313,599}

    Returns: 8.55878345525058E8

  93. {5154399,1,17210645,758776,1420281,656356796}

    Returns: 2.1256833074842942E8

  94. {4083256,508,459165056,28629558,714923923}

    Returns: 1.1458936829218228E9

  95. {380203681,20511753,992436098,184528518,248969}

    Returns: 1.3856289794545138E9

  96. {149,459164649,69344267,39134741,184527344,20511708}

    Returns: 5.985249181413195E8

  97. {1048840,5153715,20511449,4084205,503285186,371888,100132,312500824}

    Returns: 7.931633761892774E8

  98. {1049566,24299220,39134888,380204298,229345911}

    Returns: 5.905871691492306E8

  99. {874,777600943,254804958,52521073,229344719,24300527,1,17474}

    Returns: 1.3280830351604218E9

  100. {916133487,52522607,161318,503283574,147009296,312499632,550732580}

    Returns: 2.9763763108968954E9

  101. {39135296,205963424,164917207,7962452,14349228}

    Returns: 3.686022931574722E8

  102. {538278,161906,4084279,4085014,162004}

    Returns: 8169292.966935633

  103. {161413,538762,16460,2873,3200663,24299580,4083694,24300198}

    Returns: 4.859977799607072E7

  104. {32081,248439,408,17209667,161820,249431,536994,2475592}

    Returns: 1.3054365392138219E7

  105. {11881896,1231,1048505,1888988,4093}

    Returns: 9873928.159339808

  106. {28629424,4084542,2837,20511708,5152835}

    Returns: 5.136444205525604E7

  107. {3199346,1013,536904,371270,32467,20511984,20511570,32100}

    Returns: 4.1023553997911006E7

  108. {5153015,370952,1419147,28630047,1419604,20510626,349}

    Returns: 4.846525297073861E7

  109. {111,758570,1,24299232,4084772,594,7963148,17231}

    Returns: 3.13321459513885E7

  110. {5153729,1888638,14348327,1822,1420597,249821,3200693}

    Returns: 2.4710553599868882E7

  111. {3639,7961723,7961843,9765897,538259}

    Returns: 3.355913990691258E7

  112. {893871496,268436295,893872698,173,2096574}

    Returns: 1.9593783255820036E9

  113. {77514,893872603,278999,10000091,62748784,823393,823728}

    Returns: 4.7366409570143586E8

  114. {612220702,118,9999271,824247,1,1544,1,1}

    Returns: 1.5648336283590332E8

  115. {1,105414354,1,78347,612219260}

    Returns: 5.080814808640757E8

  116. {2097394,823133,268436161,62748814,268436324}

    Returns: 5.368724849999752E8

  117. {170859560,824133,4783605,9999182,77799,739,2097288,2096849}

    Returns: 8.26669422896461E7

  118. {823935,823289,9999135,612219347,10000781}

    Returns: 1.7648204143246377E8

  119. {280373,16153,62748377,410339643,170859189,62749313,410338688,268436372}

    Returns: 1.62166501445396E9

  120. {268435154,893871171,62749451,170858818,612219818,410338019}

    Returns: 2.7857234322210617E9

  121. {4783692,823220,612220447,16228,105413741,4782715}

    Returns: 5.0808049612226695E8

  122. {1,1952613,305,719,261171,1}

    Returns: 1428237.9211083846

  123. {10078380,1264,19197,1,134218114,1954087}

    Returns: 7.355817169493325E7

  124. {1509,1,40352631,20643,261517,1952425,19691}

    Returns: 1.7752237670803644E7

  125. {40352921,850,1097,1952528,387421248}

    Returns: 2.5006862269597447E8

  126. {1952709,1,1952278,262328,904,134218135}

    Returns: 3.6279737147391826E7

  127. {1953150,387420694,1953335,262126,262798}

    Returns: 5.8922509151717834E7

  128. {40353517,1953122,40353458,10077780,261486,387420320,262946}

    Returns: 3.3077696209532386E8

  129. {387420238,20279,134217538,262575,1953033,10078561}

    Returns: 4.5606398900037724E8

  130. {1953896,1131,10078479,10077001,1952535}

    Returns: 2.1653091112507835E7

  131. {1180,40354146,40354225,1,10077278,19253,261832}

    Returns: 8.070837099996133E7

  132. {1047946,1048289,1048436,543,1049538,1048630,1049381,575}

    Returns: 1.048551998589413E7

  133. {1049019,1047577,1049560,208,1,97,1048110}

    Returns: 6289951.797679972

  134. {1,1,1,1048410,992}

    Returns: 64498.76649983316

  135. {1,1048846,1048637,1048165,1048995}

    Returns: 6291444.772216631

  136. {457,1047646,797,1049095,1,1,447,1049360}

    Returns: 4193745.798843899

  137. {836,1,1,1048111,1049456,309,626,1049115}

    Returns: 4194792.328458842

  138. {1,1048003,1048741,1048460,1}

    Returns: 4193206.8203116325

  139. {1049413,1048202,630,1047712,674,1048051,15}

    Returns: 6289140.277294476

  140. {1,598,904,1047712,1047790,1,1}

    Returns: 2095501.998548319

  141. {1,1048068,1,1,1048154,1}

    Returns: 2096221.9982358739

  142. {1, 999950884, 1 }

    Returns: 63246.0

  143. {9123344, 24324455, 9898983, 40000077, 8989898, 92344323, 100000000, 90909898 }

    Returns: 4.3484743911406803E8

  144. {1000000000, 1, 1000000000, 2, 3, 4, 5, 6 }

    Returns: 2.0E9

  145. {99999999, 1, 2 }

    Returns: 28284.271106040545

  146. {100, 100, 11, 11, 25 }

    Returns: 200.0

  147. {998, 10074, 1, 1, 345473, 77973, 4273423, 51123423 }

    Returns: 2.9561597499927435E7

  148. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 10000000, 1 }

    Returns: 1.0E10

  149. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 1.4E10

  150. {1000000000, 1000000000, 1000000000, 1000000000, 999999999, 999999998, 1000000000, 1000000000 }

    Returns: 1.3999999994E10

  151. {50000, 50000, 2 }

    Returns: 100000.0

  152. {1000000000, 1, 1000000000 }

    Returns: 2.0E9

  153. {1, 2, 1000, 1, 1, 1, 1000 }

    Returns: 2000.0

  154. {2435345, 3456544, 645647, 456768, 7895678, 3423454, 456, 644563 }

    Returns: 2.142490044057381E7

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: