Az S. 98. feladat (2015. április)

S. 98. Szeretnénk a számítógépünket felújítani, ezért vásárolnunk kell bele néhány alkatrészt, így a régieket az újakra tudjuk cserélni. A lehető legolcsóbban szeretnénk a felújítást elvégezni, így a legkevesebb alkatrészt szeretnénk megvásárolni (mindegyik azonos árban van). Viszont előfordulhat, hogy valamilyen összetartozó \(\displaystyle k\) db alkatrész közül \(\displaystyle k-1\)-et újra cserélünk, ekkor kötelezően a \(\displaystyle k\)-adikat is ki kell cserélni. A boltban összesen \(\displaystyle N\) (\(\displaystyle 1\le N\le 1\;000\;000\)) típusú alkatrész található (1-től \(\displaystyle N\)-ig számozva). Az összetartozó csoportok mérete bármekkora lehet, de összes méretük legfeljebb 250000 lehet. Tudjuk továbbá azt is, hogy az 1-es számú alkatrészt mindenképp ki kell cserélnünk.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle C\)-t (a csoportok számát), majd a következő \(\displaystyle C\) sorból a csoportban lévő alkatrészek \(\displaystyle \mathrm{db}_i\) számát, majd a csoportban lévő alkatrészek típusát \(\displaystyle \mathrm{db}_i\) darab 1 és \(\displaystyle N\) közötti egész formájában. A két csoportnak akár közös elemei is lehetnek. A program írja a standard output első sorába a megvásárolandó alkatrészek minimális számát. Magyarázat: a példában az 1, 2, 3, 4-es számú alkatrészeket kell megvenni.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s98.zip állományban a program forráskódja (s98.pas, s98.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s98.txt, s98.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2015. május 11-én LEJÁRT.

Statisztika:

12 dolgozat érkezett.
10 pontot kapott:	Alexy Marcell, Bálint Martin, Dóczi András, Gáspár Attila, Kiss Gergely, Molnár-Sáska Zoltán, Szakály Marcell, Weisz Ambrus.
9 pontot kapott:	Zalavári Márton.
8 pontot kapott:	3 versenyző.

A KöMaL 2015. áprilisi informatika feladatai