Problem G
Olympus Måns
Languages
da
en
Your Swedish friend Måns loves to take pictures of himself with mountaintops (or at least hilltops) in the background. Måns owns a tripod on which he can mount the camera at a height of up to $4$ feet. He wants to include the highest mountaintop in the picture. How far away from the start of the mountain does he have to stand?
Input
On the first line, the number $n \geq 2$ of heights in the mountain’s height profile. The second line consists of $n$ integers $h_1, \ldots , h_ n$, which describe the mountain’s height profile from Måns’ initial position at the start of the mountain. There is $1$ foot horizonatally between each point in the profile, and we assume that these points are connected by straight lines.
The mountain is guaranteed to have a unique top, i.e., the maximal number among $h_1$, $\ldots $, $h_ n$ occurs only once. Moreover, we have $h_ i\geq 0$ for all $i$.
Initially, Måns is standing at the first point, i.e., at height $h_1$, and must move away from the mountain until it is possible to take a picture in which the mountaintop is visible. The surroundings of the mountain are flat, so that the tripod will be placed at height $h_1$. Do not take the curvature of the planet into account.
The tripod can have any length between (and including) $0$ and $4$ feet.
Output
Print a single integer: the smallest number $l\geq 0$, such that the mountaintop is visible if Måns places his tripod $l$ feet further away from the top, relative to $h_1$.
Points
There are three test groups, depending on whether Måns’ spends his holiday in Denmark, the Himalayas, or on Mars.
|
Group |
Points |
Constraints |
|
1 |
32 |
$h_ i \leq 600$ feet, $n\leq 1\, 000$ |
|
2 |
33 |
$h_ i \leq 30\, 000$ feet, $n\leq 10\, 000$ |
|
3 |
35 |
$h_ i \leq 72\, 000$ feet, $n\leq 100\, 000$ |
Explanation of samples 1 and 2
The sample inputs can be drawn as
![\includegraphics[width=0.25\textwidth ]{img/sample1.pdf}](/problems/olympusmans/file/statement/en/img-0002.png)
![\includegraphics[width=0.25\textwidth ]{img/sample2.pdf}](/problems/olympusmans/file/statement/en/img-0003.png)
In Sample 1, Måns just barely can include the mountaintop by putting the tripod $2$ feet away from $h_1$. If he were to move $1$ foot closer, the point $h_2=5$ would be in the way, spoiling the view.
In Sample 2, he can remain where he is.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 0 5 5 6 4 0 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 10 12 9 12 12 13 11 10 |
0 |
