Az S. 142. feladat (2020. március)

S. 142. Egy élelmiszerfeldolgozással foglalkozó cég raktárában az almák egy futószalagon érkeznek sorban. Mindegyik almáról tudjuk, hogy mennyire finom. Az almákat szeretnék zsákokba rendezni úgy, hogy az első néhány az első zsákba kerül, a következő néhány a második zsákba, a következő néhány a harmadikba, és így tovább. Egy zsákba legfeljebb \(\displaystyle K\) darab alma fér. Egy zsák alma annyira finom, mint a benne lévő legfinomabb alma. Írjunk programot, ami úgy osztja be az almákat a zsákokba, hogy a legfinomabb és legkevésbé finom zsák almák finomsága közötti különbség a lehető legkisebb legyen.

Bemenet: az első sor tartalmazza az almák \(\displaystyle N\) számát és a zsákok \(\displaystyle K\) méretét. A második sor \(\displaystyle N\) darab számot tartalmaz: az \(\displaystyle i\)-edik szám azt jelenti, hogy az \(\displaystyle i\)-edik alma finomsága \(\displaystyle F_{i}\).

Kimenet: egyetlen szám, amely megadja a legkisebb finomságbeli különbséget a legfinomabb és legkevésbé finom zsák alma között optimális beosztás esetén.

Példa:

Korlátok: \(\displaystyle 1\le N, K\le 100\, 000\), \(\displaystyle 1\le F_{i}\le {10}^{9}\). Időkorlát: 0,3 mp.

Értékelése: a pontok 30%-a kapható, ha \(\displaystyle N\le 1000\).

Beküldendő egy s142.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. április 14-én LEJÁRT.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Mócsy Mátyás, Noszály Áron, Szente Péter, Varga 256 Péter.
0 pontot kapott:	2 versenyző.

A KöMaL 2020. márciusi informatika feladatai