Statistics

Problem Statement for "Overhang"

Problem Statement

We want to construct a stationary crane and place it on a flat roof. We will make it by placing beams on top of each other and attaching a weightless cable to the end of one of the beams. All the beams have the same square cross-section but their lengths vary. Here is a picture of a crane (with its load attached to the cable) that could be constructed using 3 beams. 
                cccccccc
                   bbbbbbbbbbb
         aaaaaaaaaaaaaaaaa    |
======================        |
======================overhang|
==== building=========        |
======================        |
======================        |
======================      LOAD
======================
We have already determined the order of the beams: the first beam must be placed on the roof, the second beam on top of it, etc. During construction we can support the crane, but after construction is complete and the load is attached to the cable the resulting crane must not fall apart. Specifically, a topmost section of the crane will tip and fall if the horizontal position of it center of gravity is to the left or right of the beam (the roof for the entire crane) on which it rests.

We have chosen our units so that each beam's weight is the same as its length. Given a int[] beam (the weights or lengths of each beam in order) and LOAD, return the maximum overhang that we can achieve.

Definition

Class:
Overhang
Method:
hang
Parameters:
int[], int
Returns:
double
Method signature:
double hang(int[] beam, int LOAD)
(be sure your method is public)

Notes

  • The center of gravity of a mass is the average location of its weight. The center of gravity of a collection of masses can be computed as the weighted average of the centers of gravity of each mass.
  • A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

  • beam will contain between 1 and 50 elements, inclusive.
  • Each element of beam will be between 1 and 20,000, inclusive.
  • LOAD will be between 0 and 20,000, inclusive.

Examples

  1. {15}

    0

    Returns: 7.5

    This one-beam crane can't support anything, but at least it might provide some shade.

  2. {10}

    40

    Returns: 1.0

    Using a coordinate system in which the edge of the building is at x=0, the beam's center of gravity is at x=-4 and the load's center of gravity is at x=1 so their combined center of gravity is at x = 10*(-4) + 40*(1) = 0. The crane is balanced at the edge of the building.

  3. {10, 20, 10}

    10

    Returns: 11.0

    The best crane suspends the weight from the end of the middle beam in this case.

  4. {10, 20, 10, 1}

    10

    Returns: 11.224294595887136

  5. {750,295,200,100,1000}

    500

    Returns: 519.3321616871705

  6. {20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000}

    0

    Returns: 44992.053383294275

  7. {1}

    20000

    Returns: 2.499875006245489E-5

  8. {1,10}

    1

    Returns: 4.587121212121212

  9. {10,1}

    1

    Returns: 5.0

  10. {20,1,1,1,1,1}

    5

    Returns: 10.000000000000002

    Here your can attach the load to the long beam that is resting directly on the roof, and then counterbalance the load by stacking the short beams as far to the left as possible.

  11. {1,1,1,1,1,20}

    5

    Returns: 8.089514476583442

  12. {79}

    1010

    Returns: 2.8654729109274513

  13. {33,33}

    33

    Returns: 16.5

  14. {89,24}

    57

    Returns: 35.86176470588235

  15. {24,38}

    50

    Returns: 10.775974025974026

  16. {24,37}

    50

    Returns: 10.594594594594595

  17. {234,111,923,611,244,925,500}

    0

    Returns: 867.0497925733627

  18. {20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000,10000,20000,20000,20000,20000,20000,20000,20000,20000,20000,20000}

    20000

    Returns: 36549.29141830294

  19. {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    8674

    Returns: 18837.511754112482

  20. {10000,10000,15000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    8999

    Returns: 18857.894425290353

  21. {10000,10000,19000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    8999

    Returns: 18991.079371357213

  22. {16473, 12829, 10190, 19062, 10685, 10173, 9537, 9189, 5067, 19442, 10266, 17943, 17503, 1801, 19320, 7110, 6075, 19972, 19074, 15025, 14640, 13187, 1053, 8684, 8837, 2111, 11303, 824, 9735, 10575, 19347, 17262}

    13317

    Returns: 23298.611521770166

  23. {11009, 6228, 6695, 14964, 16889, 8274, 1859, 2784, 12100, 4702, 5627, 10775, 4072, 9715, 16478, 18854, 7742, 4448}

    10263

    Returns: 17497.21456087878

  24. {49, 3165, 10850, 15923}

    3239

    Returns: 8728.0077716901

  25. {10273, 6597, 9825, 12847, 7548, 13562, 426, 18038, 11165, 14375, 13502, 4791, 17282, 1843, 17370, 986, 11328, 4412, 2760, 15321, 3125, 4279, 13305, 16182, 19305, 12756, 16539, 18472, 16032, 16127, 12855, 11280, 8863, 2146, 18345, 8907, 3320, 1864, 17437, 18624, 19187, 6652, 16515}

    7999

    Returns: 28065.264792018414

  26. {17136, 15278, 17326, 7779, 2875, 11342, 15388, 18483, 18842, 6760, 3797, 9299, 2678, 18415, 4818, 11858, 4902, 7554, 19875, 3539, 5707}

    3347

    Returns: 23081.876381794984

  27. {3733, 6073, 6733, 15926, 7998, 5654, 9628, 9979, 11715, 19291, 3029, 16991, 5014, 4823}

    3251

    Returns: 18854.351795665476

  28. {16077, 12115, 2111, 7874, 9163}

    10668

    Returns: 10892.466823541581

  29. {5789, 5901, 12685, 12394, 3252, 1875}

    2506

    Returns: 10295.789104984044

  30. {2245, 6472, 8500, 14416, 9179, 8112, 14329, 5405, 5537, 10830, 6903, 3715, 11761, 12847, 5302, 3931, 4683, 6326, 17095, 2770, 10689, 2213, 10789, 5928, 9647, 11781, 471, 6787, 16936, 4082, 11090, 18673, 18699, 4613, 1083, 4120, 8021, 3903, 8713, 476, 10352, 17967, 8745, 7564, 8296, 6849, 8539, 17833, 5502}

    14010

    Returns: 21663.466351702824

  31. {13877, 7894, 8469, 15161, 12115, 11755, 9517, 10217, 16769, 11267, 7268, 9719, 11439, 11261, 9536, 4114, 10107, 10438, 8958, 15914, 3562, 3530, 9884, 8756}

    1281

    Returns: 21278.685743221697

  32. {17344, 15722, 5325, 12351, 4521, 2799, 6140, 19012, 15216, 11696, 19898, 19030, 9402, 17990, 17048, 18824, 16445, 11928, 19533, 10941, 12876, 19518, 10891, 12211, 9121, 8032, 1693, 3285, 13446, 6461, 14719, 19188, 17824, 13223, 3002, 15920, 6201, 18443, 1947, 18705, 7913, 18030}

    9923

    Returns: 28022.809573886305

  33. {6623, 4403, 16252, 10653, 7633, 17306, 8222, 8561, 3678, 16738, 19709, 735, 2076, 4655, 8424, 15669, 11556, 12743, 1329, 19217, 22, 17558, 12772, 11896, 12425, 4753, 293, 12127, 10451, 5367, 16005, 18821}

    14310

    Returns: 20976.83774570348

  34. {12737, 10404, 12181, 15295, 9719, 4508, 4586, 18723, 12005, 16688, 6500, 16699, 1184, 5548, 16200, 4822, 19310, 3395, 4756, 9979, 4544, 3576, 19757, 14790}

    6802

    Returns: 22366.7453394004

  35. {7524, 8879, 4691, 5651, 16165, 2860, 11834, 11873, 15067, 7661, 11467, 10499, 12419, 9573, 15159, 16424, 7755, 13416, 9560, 2080, 3175, 16464, 12073, 206, 14032, 4026, 1730, 117, 5849, 5229, 5518, 14640, 3760, 12186, 6026, 1982, 11276, 799, 17309, 5402, 8889, 11430, 3439, 1641, 6718, 18635}

    10847

    Returns: 21661.3886716988

  36. {13031, 12506, 7429, 19125, 4884, 1975, 11320, 6134, 13373, 2839, 5980, 3156, 7072, 18219, 11988, 13371, 10377, 11389}

    15414

    Returns: 17134.014125181006

  37. {8540, 6962, 13308, 14833, 18306, 7536, 4758, 7666, 2798, 17209, 11273, 4191, 1387, 15286, 14137, 13933, 2916, 4623, 1165, 6686, 17295, 2134, 10149, 10937, 503, 10275, 17335, 632, 4836, 346, 1193, 14816, 2185, 18377, 11469, 19820, 18282, 15597}

    7376

    Returns: 25096.539404150775

  38. {16424, 6165, 7056, 13575, 6763, 6718, 12235, 2414, 4235, 477, 16317, 17067, 1370, 2811, 8590, 19878, 19505, 6778, 15497, 9227, 7318, 10102, 13016, 15263, 1607, 15527}

    10713

    Returns: 21171.440911291502

  39. {13606, 5219, 18366, 6430, 3808, 3584, 9970, 7814, 15899, 11447, 8845, 11035, 6204, 1380, 1789, 929, 2835, 14890, 10285, 1, 4483, 16339, 12127, 7256, 6418, 15093, 4450, 6827, 14089, 17137, 10384, 3544, 5160, 9781, 7463, 7016, 9578, 12256, 16386, 5249, 10160, 14693, 6291}

    3308

    Returns: 23060.048318483947

  40. {11465, 15839, 19588, 16972, 7303, 11189, 11437, 5473, 6995, 16941, 19906, 14380, 18780, 15578, 298, 12868, 19402, 19083, 14995, 15462, 2278, 12323, 4903, 1145, 25, 15539, 15004, 9564, 909, 5425, 1290, 12079, 13615, 3512, 2967, 5563, 9014, 7515, 18446, 19903, 15102, 1927}

    7889

    Returns: 26818.74051326167

  41. {9837, 4692, 9728, 6827, 10679, 6407, 17344, 19186, 17180, 9031, 18236, 10914, 9038, 4890, 14843, 18837, 10129, 11036}

    16886

    Returns: 18741.827081850246

  42. {11483, 7868, 9247, 19347, 6940, 17298, 13577, 16656, 17815, 7488}

    14779

    Returns: 16239.608352420359

  43. {17773, 10533, 17295, 8244}

    11680

    Returns: 12194.542853872568

  44. {8004, 258, 10810, 8519, 1709, 3000, 3268, 13387, 577, 10254, 10198, 13480, 5530, 18716, 4977, 17342, 11648, 19848}

    9715

    Returns: 17872.070224869603

  45. {10273, 8137, 5570, 3630, 17309, 16278, 9921, 1792, 9117, 7696, 10427, 13522, 19011, 12041, 7619, 19094, 1917, 6160, 1406, 6907, 8851, 19451, 12097, 3335, 13632, 9455, 3060, 1748, 4862, 18862, 10456}

    6005

    Returns: 22724.584563071818

  46. {4989, 1796, 18948, 19206, 15025, 2443, 13945, 557, 16086, 15290, 13032, 8417, 18812, 12413, 4648, 15664, 11102, 15201, 7132, 4181, 10608, 1268, 4175, 11499}

    17948

    Returns: 19688.274370606785

  47. {4273, 13085, 825, 8823, 1608, 4280, 9633, 737, 19253}

    11332

    Returns: 9847.004150599772

  48. {14608, 15365, 19779, 15576, 2909, 2832, 16769, 77, 15627, 18353, 331, 15893, 15056, 5443, 12203, 257, 2869, 5524, 9310, 10832, 11475, 2248, 1472, 6621, 15101, 9357, 8832, 17993, 8988, 17654, 17139, 4960, 13301, 18871}

    14254

    Returns: 22331.327402603456

  49. {15143, 92, 3465, 7249, 913, 2726, 19889, 15626, 8240, 19171, 4345, 13986, 3014, 12169, 6045, 711, 3318, 9327, 1772, 2031, 13452, 18343, 2325, 40, 3258, 14268, 14270, 5085, 9980}

    6420

    Returns: 21191.695006475165

  50. {5026, 16189, 12482, 13595, 8701, 11315, 14491, 10150, 14897, 8133, 1106, 19650, 10824, 5837, 10018, 4909, 4316, 14456, 8184, 14213, 9378}

    16261

    Returns: 19335.420646371258

  51. {11835, 1235, 894, 16441, 15718, 8921, 6123, 5023, 4052, 1522, 18850, 15636, 10203, 6916, 19509, 2979, 1550, 15357, 10546, 18659, 8971, 9702, 13708, 2900, 1745, 3556, 7194, 17464, 12623, 298, 18073, 652, 16727, 15486, 8525}

    9813

    Returns: 23026.140053131956

  52. {16550, 12741, 3005, 19596, 4943, 13563, 6727, 11503, 6042, 283, 16978}

    455

    Returns: 19207.196340918985

  53. {6491, 13577, 7128, 1712, 19753, 9426, 17197, 11698, 11715, 11012, 18509, 6171, 1758, 17375, 5420, 13596, 16170, 3051, 4833, 2585, 13101, 15696, 17054, 15212, 5516, 15823, 17145, 595, 14377, 1469, 5097, 5239, 16741, 18490, 7565, 15386, 17990, 7281, 1862, 16732, 14132, 13102}

    4017

    Returns: 27267.573559928875

  54. {4542, 3958, 11294, 6882, 2170, 13704, 14619, 9351, 13993, 15119, 15182, 19071, 10872}

    8066

    Returns: 18314.85644359267

  55. {10915, 19971, 13751, 16995, 1421, 17172, 10472, 15789, 4120, 5769, 19332, 5310, 6452, 19988, 17035, 12120, 17896, 1659, 11048, 17105, 17092, 14528, 10285, 9891, 2179, 11131, 9131, 10752, 7289, 15684, 12654, 14914, 8831, 19181, 9460, 8289, 11192, 15083, 3208, 16253, 10270, 11125, 10815}

    11240

    Returns: 25347.88077654264

  56. {16740, 15950, 3821, 4877, 6171, 6790, 15018, 7029, 3073, 9934, 15997, 19585, 8521, 6299, 11065, 4593, 8371, 18221, 1609, 17369, 14091, 2441, 2661, 12652, 18190, 12527, 7073, 15041}

    13734

    Returns: 21179.055970847847

  57. {11136, 13791, 17227, 6061, 8103, 18475, 1056, 13958, 5836, 8426, 6144, 2590, 8204, 10965, 6550, 8208, 10171, 15609, 11369, 17553, 14167, 11623, 1313, 14633, 9142, 1247, 18115, 18767, 2781, 15859, 19575, 2816, 3570, 11099, 3883, 11419, 777}

    16134

    Returns: 23338.55512503784

  58. {6236, 15867, 10391, 17282, 467, 16181, 18355, 390, 16352, 10893, 5413, 13515, 13294, 17359, 2716, 8915, 17929, 9013, 10147, 17483, 16989, 1269, 13322, 6678, 4716, 16020, 16118, 8520, 8140, 7736}

    7237

    Returns: 23634.414339341216

  59. {7387, 18396, 17935, 2795, 18975, 14396, 14768, 19836, 4574, 15952, 19755, 1597}

    6212

    Returns: 21529.402792354776

  60. {15628, 4581, 7804, 5544, 7596, 13420, 5901, 7820, 16441, 5326, 7345, 12458}

    3005

    Returns: 16501.785134933605

  61. {4755, 13560, 5379, 17021, 7703, 3601, 3783, 10141, 1880, 16997, 4702, 6750, 18911, 6794, 12573}

    9002

    Returns: 17154.49557630323

  62. {13552, 8363, 9659, 1750, 5906, 6128, 11818, 17330, 8871, 8404, 2050, 18787, 13784, 11255, 13868, 5797, 15309, 18573, 1123, 3333, 13217, 6611, 16383, 10480, 5908, 19475, 13935, 19222, 16926, 11439, 16959, 17793, 9600, 1326, 19161, 16780, 4023, 1440, 8936, 13474, 10026, 6992}

    1952

    Returns: 28227.250494573487

  63. {17347, 6789, 12954, 7735, 14266, 5876, 1059, 11128, 10797, 2566, 147, 4444, 10572, 9314, 8915, 1048, 5648, 1111, 16343, 15593, 15788, 15207, 5764}

    17200

    Returns: 16198.498547975658

  64. {1267, 5675, 17520, 14745, 18207, 6227, 17083, 9262, 16066, 1461, 1787, 12869, 12781, 12513, 13540, 18619, 19573, 17310, 6672, 19282, 8383}

    19649

    Returns: 20760.146539285557

  65. {8197, 3239, 9679, 1902, 14390, 1100, 11518, 18554, 4835, 18619, 3639, 4623, 5527, 10103, 10519, 6314, 669, 12066, 2722, 38, 400, 19467, 14272, 13630, 6541, 19508, 9251, 8736, 14730, 9278, 7044, 4746, 4384, 10547, 15339, 901, 5475, 8048, 5452, 6650, 274, 3949, 6574, 11797, 18474, 6987}

    15138

    Returns: 21362.8217596072

  66. {11381, 19225, 4453, 10316, 5888, 7714, 18374, 2009, 202}

    17896

    Returns: 13745.599853448337

  67. {4128, 1144, 15987, 4409, 15139, 12837, 4465, 941, 18815, 1047, 6471, 8883, 13222, 12557, 16285, 7383, 980, 7508, 5711, 7818, 12528, 1113}

    7544

    Returns: 18536.85520181548

  68. {3297, 5048, 12582, 7798, 12010, 1171, 8208, 16780, 5732, 12127, 19027, 7633, 13750, 9016, 8978, 17372, 3251}

    19280

    Returns: 16772.22872436101

  69. {12021, 17745, 12246, 4222, 5780, 769, 9402, 17751, 11969, 16432, 18925}

    5958

    Returns: 17765.890808608143

  70. {1209, 18078, 11755, 18388, 12196, 6446, 14422, 15449, 16511, 9956, 1745, 5136, 13368, 10846, 13485, 19130, 11124, 13378, 2463, 5591, 16111, 15699, 18597, 4361, 17936, 3871, 15255, 19377, 392, 13077, 14892, 7766, 6056, 8916, 10598, 15620, 19932, 10846, 1083, 16976, 9831, 14763, 17856, 9082, 9564, 9882, 19028}

    4582

    Returns: 28499.626694336617

  71. {3298, 9927, 3742, 12405, 4871, 16773, 9915, 11126, 1641, 995, 3006, 13965, 4502, 14469, 1239, 257, 639, 1225, 17354, 14053, 8743, 6100, 19638, 1231, 6936, 5686, 10291, 17558, 13616, 6364, 14388, 18797, 12025, 7603, 204, 9878, 11831, 18740, 14766, 7045, 15002, 9584, 17516, 7154, 9747, 345}

    18553

    Returns: 22298.775875884512

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: