Az I/S. 72. feladat (2023. május)

I/S. 72. Egy levelibéka szeretne átjutni egy patak átellenes oldalára. A patak átellenes pontja, ahova a béka szeretne eljutni, $\displaystyle M$ centiméterre van a béka jelenlegi pozíciójától. Szerencsére a patakon vízinövények élnek, melyekre ugorva könnyebb lehet az átkelés. A béka útjában összesen $\displaystyle N$ számú vízinövény található (egyenes vonalban, a tó átellenes pontja felé), az $\displaystyle i$-edik vízinövény $\displaystyle T[i]$ cm-re van a béka kiindulási helyétől.

A béka minden egyes másodpercben vagy szökken pontosan 1 cm-t (vagy a partra, vagy egy másik vízinövényre), vagy pedig ugrik legfeljebb $\displaystyle D$ cm-t (vagy a partra, vagy egy másik vízinövényre). Az ugrás nagyon fárasztó, ezért minden ugrás után pihenésként szökkennie kell a békának (legalább egyszer).

Adjuk meg, hogy minimum mekkora $\displaystyle D$ ugrásra kell képesnek lennie a békának, hogy át tudjon jutni a patak átellenes oldalára.

A bemenet első sorában az $\displaystyle N$ és $\displaystyle M$ számok találhatók szóközzel elválasztva: a vízinövények száma, és a patak szélessége. A második sor szóközzel elválasztva tartalmaz $\displaystyle N$ szigorúan monoton növekvő sorrendben adott számot: az $\displaystyle i$-edik szám az $\displaystyle i$-edik növény $\displaystyle T[i]$ távolsága a béka indulási helyétől.

A kimenet egyetlen sorában egy szám szerepeljen: a minimális $\displaystyle D$ távolság, amivel a béka át tud jutni a túlpartra.

Minták:

Magyarázat: az első példában a béka ugrik az 1. növényre, aztán szökken a 2. növényre, aztán ugrik a túlpartra. A második példában a béka egyből átugrik a túlsó partra (nem tudja felhasználni a növényt, mivel nem tudna szökkenni ugrás után).

Korlátok: $\displaystyle 1\le N, M \le 10^5$, $\displaystyle 0 < T[i] < M$, $\displaystyle T[~]$ szigorú monoton növekvő. Időkorlát: 0,4 mp.

Értékelés: a pontok 50%-a kapható, ha a program helyes kimenetet ad az $\displaystyle N,M \le 100$ esetekben.

Beküldendő egy is72.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. június 15-én LEJÁRT.

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Gyönki Dominik, Horváth Milán, Szabó Imre Bence.
9 pontot kapott:	Zádor-Nagy Zsombor.

A KöMaL 2023. májusi informatika feladatai