PillarsDivTwo
SRM 547 · 2011-11-22 · by sdya
SRM 547 · 2011-11-22 · by sdya · Dynamic Programming
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
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
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