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