 |
Az S. 128. feladat (2018. október) |
S. 128. A fáraó elrendelte egy piramis építését, ehhez kőtömböket kell szállítani a bányától \(\displaystyle Q\) kilométerre levő építési területig. \(\displaystyle N\) kereskedő megadta, hogy mettől-meddig tud tömböt szállítani. Minden kereskedő legfeljebb egyszer szállít legfeljebb egy kőtömböt. A fáraó legfeljebb \(\displaystyle M\) kereskedőt kérhet meg a szállításra a költségek csökkentése érdekében. Segítsünk a fáraónak kiszámolni, hogy legfeljebb hány kőtömböt tud elszállíttatni az építési területre, és ehhez minimum hány embert kell megfizetnie. Egy kereskedő akkor tudja átadni a kőtömbjét egy másiknak szállításra, ha legalább addig el tudja vinni a tömböt, ahonnan a másik indulhat.
Bemenet: Az első sor tartalmazza a kereskedők \(\displaystyle N\) számát, a maximálisan megkérhető kereskedők \(\displaystyle M\) számát, valamint a bánya és az építési terület \(\displaystyle Q\) távolságát. A kereskedőket 0-tól \(\displaystyle N-1\)-ig sorszámozzuk. A következő \(\displaystyle N\) sor mindegyike két számot tartalmaz: az adott kereskedő hányadik kilométertől hányadik kilométerig tud szállítani.
Kimenet: Az első sorba írjuk ki, hogy maximum hány kőtömböt lehet elszállítani; a következő sorba, hogy ehhez minimálisan hány kereskedőnek kell fizetni.
Korlátok: \(\displaystyle 1\le M\le N\le {10}^{5}\), \(\displaystyle 0\le Q\le 2\cdot {10}^{9}\), egészek. Időlimit: 1 s, memórialimit 100 MiB.
Értékelés: A pontok 20%-a kapható, ha maximum egy tömböt tud a fáraó elszállíttatni; további 20% kapható, ha \(\displaystyle M=N\); további 20% kapható, ha \(\displaystyle N\le 1000\); további 10% kapható, ha \(\displaystyle Q\le {10}^{5}\); további 30% kapható az eredeti korlátokra.
Az I/S és S-jelű feladatok megoldását a http://mester.inf.elte.hu automatikus értékelő rendszer segítségével kipróbálhatod, tesztelheted (Téma: KöMaL - 2018/19).
(10 pont)
A beküldési határidő 2018. november 12-én LEJÁRT.
Statisztika:
11 dolgozat érkezett. 10 pontot kapott: Csertán András, Horcsin Bálint, Molnár Bálint, Noszály Áron, Szente Péter, Varga 256 Péter. 9 pontot kapott: Gyimesi Péter, Ürmössy Dorottya. 8 pontot kapott: 1 versenyző. 6 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző.
A KöMaL 2018. októberi informatika feladatai