pillars
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
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 vector 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.
Input
The first line is an integer n indicating the vector\'s size.then contains n integers.
netx line is w.
Output
For each test case, please print the answer maximum, The number must be written with exactly 6 digits after a decimal point
Sample Input
3 3 3 3 2 4 1 1 1 1 100
Sample Output
5.656854 300.000000