PillarsDivTwo | Topcoder Archive

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.

Definition

Class:: PillarsDivTwo
Method:: maximalLength
Parameters:: int[], int
Returns:: double
Method signature:: double maximalLength(int[] height, int w)
(be sure your method is public)

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.

Examples

```
{3,3,3}
```
```
2
```
```
Returns: 5.656854249492381
```
```
{1,1,1,1}
```
```
100
```
```
Returns: 300.0
```
```
{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.
```
{2,1,1,2}
```
```
1
```
```
Returns: 3.82842712474619
```

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.