Statistics

Problem Statement for "PickupBed"

Problem Statement

We have a number of 4-foot long pipes that have regular octagonal cross-sections of various sizes. We want to place them in a pickup truck which is 4 feet wide, with the length of each pipe extending across the width of the truck. Each pipe must rest with one of its 8 sides flat on the truck's bed. The front and back sides of the truck are higher than the pipes, so each pipe must fit entirely inside the truck. How long will the truck have to be to hold them all? 

  |                                    |
  |                                    | 
  |                   x x x x          |             
  |                 x         x        |         
  |               x             x      |          
  |     x x x   x                 x    |        
  |   x       x x                 x    |   
  | x           x                 x    | 
  | x           x                 x x  |
  | x           x x             x     x| 
  |   x       x     x         x x     x|   
  |     x x x         x x x x     x x  |     
  |-------------------------------------
        <--- length of truck --->

Create a class PickupBed that contains a method length that is given a int[] ht and returns the minimum length of truck that can hold all the pipes. The i-th element of ht gives the height of a pipe when it is resting on one of its sides.

Definition

Class:
PickupBed
Method:
length
Parameters:
int[]
Returns:
double
Method signature:
double length(int[] ht)
(be sure your method is public)

Notes

  • A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

  • ht contains between 1 and 8 elements, inclusive.
  • Each element of ht is between 1 and 1000, inclusive.

Examples

  1. {5,5,5}

    Returns: 15.0

    The pipes will lie with their perpendicular sides against each other. Each one will require the full 5 units of the truck's length.

  2. {17}

    Returns: 17.0

  3. {10,1,1}

    Returns: 10.0

    We can put the big one between the 2 little ones. The little ones can fit entirely in the area under the slanted sides of the big one.

  4. {10,2,2}

    Returns: 10.97056274847714

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

    Returns: 33.21320343559643

  6. {1,1,1,1,800,300,45,1}

    Returns: 1077.8174593052022

  7. {1,1000,1000}

    Returns: 2000.0

  8. {500,500,121}

    Returns: 1000.0

  9. {500,500,122}

    Returns: 1001.6408357960651

  10. {500,500,122,500,121}

    Returns: 1501.640835796065

  11. {1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 8000.0

  12. {45,455,92,645,11,903,423}

    Returns: 2426.0

  13. {45,455,92,645,210,903,423}

    Returns: 2479.5861453751254

  14. {455,455,92,645,210,903,423,501}

    Returns: 3435.5861453751254

  15. {300,122}

    Returns: 420.3990616607231

  16. {500,300,572,222,606,345,444,333}

    Returns: 3290.92719908458

  17. {685, 875, 642, 959, 253, 824, 87, 475}

    Returns: 4533.629867976521

  18. {323, 497, 566, 368, 146, 231}

    Returns: 2023.6937931134503

  19. {191, 401}

    Returns: 592.0

  20. {470, 732, 241, 331, 945, 973, 535, 144}

    Returns: 3955.123517514972

  21. {918, 233, 839, 344, 227, 633}

    Returns: 2873.1547930004085

  22. {531, 649, 690, 920, 849, 910, 192, 383}

    Returns: 4932.0

  23. {807}

    Returns: 807.0

  24. {105}

    Returns: 105.0

  25. {37, 595, 716, 68, 406, 992, 772, 238}

    Returns: 3535.45446995666

  26. {165}

    Returns: 165.0

  27. {179, 688, 475, 378}

    Returns: 1632.5094141847387

  28. {610}

    Returns: 610.0

  29. {346, 508, 837}

    Returns: 1690.5073221436858

  30. {471, 772, 197, 964, 800, 258, 440}

    Returns: 3553.203461105328

  31. {6, 769, 231, 892, 532, 858}

    Returns: 3096.120199984643

  32. {470, 255}

    Returns: 725.0

  33. {689, 454, 107, 375, 4}

    Returns: 1518.0

  34. {249, 969, 381, 832, 901}

    Returns: 3122.023012451584

  35. {551, 877, 990, 521}

    Returns: 2939.0

  36. {500, 146, 793}

    Returns: 1293.0

  37. {849, 866, 73, 155, 59, 657}

    Returns: 2372.0

  38. {394, 410, 948, 247, 132}

    Returns: 1895.9926035179242

  39. {546, 203, 587, 317, 134, 14, 842, 663}

    Returns: 2981.817818242701

  40. {243, 480, 571, 940, 507}

    Returns: 2637.5073221436855

  41. {256, 437, 467, 455, 249, 512, 687, 453}

    Returns: 3470.6536418495225

  42. {686, 145, 630, 66, 343, 587, 30}

    Returns: 2246.0

  43. {983, 690, 228, 122, 235}

    Returns: 1852.8571029548511

  44. {552, 775, 337}

    Returns: 1664.0

  45. {78, 458, 208, 826}

    Returns: 1397.1484117468901

  46. {353, 64, 52, 947, 96, 680, 32, 368}

    Returns: 2303.084232802822

  47. {20, 1, 20 }

    Returns: 40.0

  48. {1000, 1, 1000 }

    Returns: 2000.0

  49. {4, 150, 100, 200, 14, 500, 300, 1000 }

    Returns: 1818.8077169749342

  50. {50, 5, 5, 1000, 200, 10, 1, 1000 }

    Returns: 2000.0

  51. {1, 950, 207, 150, 207, 100, 300 }

    Returns: 1534.279579551077

  52. {1000, 1, 1, 1, 1, 1000, 1, 1 }

    Returns: 2000.0

  53. {10, 2, 2, 9, 4, 6 }

    Returns: 29.14213562373095

  54. {15, 107, 877, 58, 220, 525, 447, 682 }

    Returns: 2605.5064555919084

  55. {100, 1, 99, 2, 88, 3, 40 }

    Returns: 325.28279195104676

  56. {100, 1, 99, 2, 88, 3, 40, 33 }

    Returns: 347.37824638055173

  57. {10, 1000, 900, 40, 70, 20, 300, 7 }

    Returns: 2067.766952966369

  58. {1, 1, 1, 1, 1000, 32, 32 }

    Returns: 1000.0

  59. {1, 10, 100, 101, 102, 999, 234, 1000 }

    Returns: 1999.0

  60. {862, 152, 212, 312, 15, 71, 5, 45 }

    Returns: 1290.4389591175113

  61. {100, 1, 1, 10, 1, 1 }

    Returns: 100.0

  62. {999, 333, 333, 333, 333, 333, 333, 333 }

    Returns: 3215.7324650809624

  63. {1000, 1, 2, 1, 998 }

    Returns: 1998.0

  64. {1000, 1000, 200, 200, 199, 200, 196, 200 }

    Returns: 2585.5770157894954

  65. {100, 300, 1000, 200, 200, 300, 100 }

    Returns: 1755.6349186104044

  66. {1, 1, 2, 10, 10, 10, 3, 10 }

    Returns: 41.384776310850235

  67. {999, 998, 123, 653, 324, 321, 346, 432 }

    Returns: 3830.908580975821

  68. {999, 997, 537, 15, 258, 456, 47, 129 }

    Returns: 3027.252234340607

  69. {2, 991, 998, 497, 10, 9, 1, 3 }

    Returns: 2486.0

  70. {74, 404, 11, 205, 3, 469, 100, 999 }

    Returns: 1922.4273785533296

  71. {1000, 999, 1, 2, 3, 400, 500, 600 }

    Returns: 3479.1918805411465

  72. {1, 100, 200, 2, 6, 500, 4, 8 }

    Returns: 719.2388155425118

  73. {998, 634, 221, 192, 764, 365, 423, 523 }

    Returns: 3724.4633457351506

  74. {10, 1, 1 }

    Returns: 10.0

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: