Az I/S. 32. feladat (2019. január)

I/S. 32. Egy iskola könyvtárban összesen \(\displaystyle M\) darab számítógép van. Egy nap \(\displaystyle N\) diák előre megadta, hogy melyik időpillanattól melyik időpillanatig szeretne használni egy gépet. Tegyük fel, hogy egy diák az \(\displaystyle a_{1}\) időpillanattól a \(\displaystyle b_{1}\) időpillanatig szeretne gépezni, egy másik pedig \(\displaystyle a_{2}\)-től \(\displaystyle b_{2}\)-ig. Ők csak akkor használhatják ugyanazt a gépet, hogyha \(\displaystyle b_{1}<a_{2}\) vagy \(\displaystyle b_{2}<a_{1}\). Ha egy diák nem tud használni egy gépet sem a teljes kért időtartam alatt, akkor a könyvtárosnak el kell utasítania a kérését. Mivel csak \(\displaystyle M\) gép van, így nem biztos, hogy mindenkinek lesz szabad gépe. A könyvtáros szeretne a lehető legkevesebb diáknak nemet mondani. Segítsünk neki egy programmal, amely megadja, hogy legkevesebb hány diáknak és kiknek kell nemet mondania.

Bemenet: Az első sor tartalmazza a diákok \(\displaystyle N\) számát és a gépek \(\displaystyle M\) számát. A diákokat 0-tól \(\displaystyle N-1\)-ig indexeljük. A következő \(\displaystyle N\) sor mindegyike egy \(\displaystyle a\) és egy \(\displaystyle b\) számot tartalmaz, amely leírja, hogy az adott diák mettől meddig szeretne gépezni.

Kimenet: Az első sor tartalmazza azt a minimum számot, ahány diáknak nemet kell mondani. A következő sor tartalmazza azon diákok indexét növekvő sorrendben, akiknek nemet kell mondani. Több lehetséges megoldás, vagyis azonos számú elutasított diák esetén a legkisebb indexű diákokat fogadja a könyvtáros.

Korlátok: \(\displaystyle 1\le N,M\le {10}^{5}\), \(\displaystyle 0\le a,b\le {10}^{9}\), egy diákra: \(\displaystyle a<b\).

Időkorlát: 0,5 mp.

Értékelés: A pontok 20%-a kapható, ha \(\displaystyle N\cdot M\le {10}^{6}\); további 20% kapható, ha \(\displaystyle b-a=1\) minden diákra; további 20% kapható, ha \(\displaystyle a,b\le {10}^{6}\) minden diákra; további 40% kapható az eredeti korlátokra.

Beküldendő egy is32.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 melyik fejlesztő környezetben futtatható.

(10 pont)

A beküldési határidő 2019. február 11-én LEJÁRT.

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Csertán András, Kovács Alex, Noszály Áron, Szente Péter.
8 pontot kapott:	1 versenyző.

A KöMaL 2019. januári informatika feladatai