Az I/S. 45. feladat (2020. május)

I/S. 45. Jenő az Alföld tengersík vidékéről felköltözött a Budai-hegyekbe. Hogy minél inkább otthon érezze magát, szeretné a kertjét átrendezni, hogy kevésbé legyen hegyes-völgyes. A kert $\displaystyle N$ parcellából áll, az $\displaystyle i$-edik parcella tengerszint feletti magassága $\displaystyle A_{i}$ méter. Jenőnek egy órába telik egy parcella tetejéről egy réteg 1 méter magasságú földet áthordani egy másik parcella tetejére (ekkor az egyik parcella magassága 1 méterrel csökken, a másiké 1 méterrel nő). Jenő akkor fogja magát otthonosan érezni, ha a kertben bármely két parcella magasságának eltérése nem nagyobb, mint $\displaystyle K$ méter. Írjunk programot, amely megmondja, hogy minimum hány órát kell dolgoznia Jenőnek, hogy elégedett legyen a kertjével és otthonosan érezze magát új lakóhelyén.

Bemenet: az első sor tartalmazza a parcellák $\displaystyle N$ számát és $\displaystyle K$ értékét. A második sor $\displaystyle N$ darab számot: az $\displaystyle i$-edik szám az $\displaystyle i$-edik parcella $\displaystyle A_{i}$ tengerszint feletti magassága méterben.

Kimenet: egyetlen szám, amely megadja, hogy minimum hány órát kell dolgoznia Jenőnek, hogy bármely két parcella magasságának eltérése legfeljebb $\displaystyle K$ legyen.

Példa:

Korlátok: $\displaystyle 1\le N,K,A_{i}\le 10^{5}$, egész számok. Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha $\displaystyle N,K,A_{i}\le 1000$.

Beküldendő egy is45.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ó.

(10 pont)

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

Statisztika:

8 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Mócsy Mátyás, Varga 256 Péter.
9 pontot kapott:	Ürmössy Dorottya.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2020. májusi informatika feladatai