Az S. 171. feladat (2023. május)

S. 171. Jázmin készített egy listát a nyári programokról, amiken részt szeretne venni. Ismerjük továbbá minden program kezdetét és végét napokban és azt is, hogy az adott program mennyibe kerül. Jázmin nem tud egyszerre két programon ott lenni, pontosabban, ha egy program az \(\displaystyle i\)-edik napon befejeződik, akkor a következő program csak az \(\displaystyle i+1\)-edik napon kezdődhet. Jázmin úgy szeretné kiválasztani a programokat, hogy azok hossza összesen a lehető legnagyobb legyen, de az összköltségük ne lépjen át egy megadott \(\displaystyle K\) értéket. (Ha az esemény az \(\displaystyle i\)-edik napon kezdődik és a \(\displaystyle j\)-edik napon ér véget, akkor annak hossza \(\displaystyle (j-i+1)\) nap.)

A bemenet első sorában a programok \(\displaystyle N\) száma és a maximális összköltség, \(\displaystyle K\) szerepel. A következő \(\displaystyle N\) sorban az egyes programok adatai szerepelnek. Minden sorban szerepel a program elejének és végének időpontja napokban \(\displaystyle (e_i, v_i)\), majd a költsége, \(\displaystyle k_i\).

Kimenet: a kimenet első sorába a programok lehetséges legnagyobb összes hossza kerüljön. A második sorban adjuk meg a programok sorszámait, melyek összes hossza az előbb kiírt érték és teljesítik a feltételeket, azaz nem fedik át egymást és az összköltségük nem nagyobb, mint \(\displaystyle K\). A programokat a listában lévő sorrend szerint, 1-től indexeljük.

Minta:

Magyarázat: az első és a harmadik program összköltsége túl nagy, ezért a második programot választjuk.

Korlátok: \(\displaystyle 1\le N \le 10\,000\), \(\displaystyle 0\le e_i \le v_i \le 100\), \(\displaystyle 1 \le k_i \le 10\,000\) (\(\displaystyle i = 1\ldots N\)). Időkorlát: 1 mp.

Értékelés: a pontok 40%-a kapható, ha a program helyes kimenetet ad az \(\displaystyle {N\le 15}\) tesztesetekre.

Beküldendő egy s171.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:

2 dolgozat érkezett.
10 pontot kapott:	Horváth Milán.
1 pontot kapott:	1 versenyző.

A KöMaL 2023. májusi informatika feladatai