Connection Status:
Competition Arena > PillarsDivTwo

PillarsDivTwo

SRM 547 · 2011-11-22 · by sdya

SRM 547 · 2011-11-22 · by sdya · Dynamic Programming
Class Name: PillarsDivTwo
Return Type: double
Method Name: maximalLength
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

On a horizontal line, there are N uniformly spaced vertical pillars. The pillars are numbered 0 through N-1, in order. For each i, the distance between the bottoms of pillars i and i+1 is exactly w. For each i, the height of pillar i (0-based index) is an integer between 1 and heights[i], inclusive. We want to take a single piece of rope and use it to join the top ends of all pillars, in order. (Once in place, the rope will have the shape of a polyline consisting of N-1 segments.) What is the shortest length of rope that is guaranteed to be sufficient, regardless of the actual pillar heights?

You are given the int[] heights and the int w. Compute and return the answer to the above question. In other words, find a sequence of pillar heights (within the given constraints) for which the length of the rope we need is maximized, and return that maximum.

Notes

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

Constraints

  • heights will contain between 1 and 50 elements, inclusive.
  • Each element of heights will be between 1 and 100, inclusive.
  • w will be between 1 and 100, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{3,3,3}
2
Returns: 5.656854249492381
1)
{1,1,1,1}
100
Returns: 300.0
2)
{100,2,100,2,100}
4
Returns: 396.32310051270036

We will need the most rope if columns 0, 2, and 4 have height 100 each, and columns 1 and 3 have height 1 each.

3)
{2,1,1,2}
1
Returns: 3.82842712474619
4)
{5,6,7,8,9,10,11,12,13,14,15}
20
Returns: 221.02070848731498

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

Coding Area

Language: C++17 · define a public class PillarsDivTwo with a public method double maximalLength(vector<int> height, int w) · 123 test cases · 2 s / 256 MB per case

Submitting as anonymous