Hide

Problem G
Olympus Måns

Languages da en
/problems/olympusmans/file/statement/da/img-0001.jpg
Olympus Mons på Mars. Kilde: ESA/DLR/FU Berlin (G. Neukum), CC BY-SA 3.0 IGO.

Din svenske ven Måns elsker at tage billeder af sig selv med bjergtoppe (eller høje bakker) i baggrunden. Til sin hjælp har Måns et kamerastativ, hvorpå kameraet kan monteres i op til 4 fods højde. Hvor langt skal han stå fra foden af bjerget for at få bjergets højeste top med på billedet?

Indlæsning

På første linje står heltallet $n \geq 2$, som angiver antallet af højder i højdeprofilen af bjerget. Den anden linje indeholder $n$ heltal, $h_1, \ldots , h_ n$, som beskriver højdeprofilen set fra Måns’ position ved foden af bjerget. Der er én fod horisontalt mellem hvert målepunkt, og vi antager at disse punkter er forbundet med lige linjer.

Det er garanteret, at bjerget har en entydig top, dvs. at det største tal i $h_1$, $\ldots $, $h_ n$ kun forekommer én gang. Desuden gælder $h_ i\geq 0$ for alle $i$.

Måns står på det første målepunkt, altså i højde $h_1$, og skal bevæge sig væk fra bjerget, indtil det er muligt at tage et billede, hvor toppen er med. Bjergets omgivelser er flade, dvs. at kameraets stativ skal opstilles i højde $h_1$. Der skal ikke tages hensyn til planetens krumning.

Stativet kan trækkes ud til en vilkårlig længde mellem $0$ og $4$ fod.

Udskrift

Det mindste hele antal fod $l\geq 0$, der er tilstrækkeligt for at bjergtoppen er synlig, når Måns stiller sit kamerastativ $l$ fod længere væk fra toppen, relativt til første målepunkt.

Pointsætning

Der er tre testgrupper, svarende til om Måns holder ferie i Danmark, Himalaya eller på Mars.

Gruppe

Point

Begrænsninger

1

32

$h_ i \leq 600$ fod, $n\leq 1\, 000$

2

33

$h_ i \leq 30\, 000$ fod, $n\leq 10\, 000$

3

35

$h_ i \leq 72\, 000$ fod, $n\leq 100\, 000$

Forklaring af eksempel 1 og 2

Eksempelinstanserne kan tegnes som

\includegraphics[width=0.25\textwidth ]{img/sample1.pdf} \includegraphics[width=0.25\textwidth ]{img/sample2.pdf}

I eksempel 1 kan Måns lige akkurat få toppen med på billedet, ved at stille stativet to fod fra det første målepunkt. Hvis han går en fod tættere på, så kommer målepunktet $h_2=5$ i vejen.

I eksempel 2 kan han blive stående, hvor han er.

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