Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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