PickupBed

TCCC06 Round 1A · 2006-08-22 · by dgoodman

TCCC06 Round 1A · 2006-08-22 · by dgoodman · Geometry

Show categories

Class Name: PickupBed

Return Type: double

Method Name: length

Arg Types: (vector<int>)

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.

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

{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.

{17}
Returns: 17.0

{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.

{10,2,2}
Returns: 10.97056274847714

{1,2,3,4,5,6,7,8}
Returns: 33.21320343559643

Submissions are judged against all 74 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PickupBed with a public method double length(vector<int> ht) · 74 test cases · 2 s / 256 MB per case