Programozás‎ > ‎Feladatok‎ > ‎

Fal (2014)

A Kínai Nagy Falon N őrhelyet létesítettek. Közülük azonban csak M helyen van őrség. Két szomszédos őrhely közötti fal őrzött, ha legalább az egyik végén van őrség; védett, ha mindkét végén van őrség. Őrzött szakasznak nevezzük egymást követő őrzött falak nem bővíthető sorozatát. Hasonlóan, védett szakasznak nevezzük egymást követő védett falak nem bővíthető sorozatát. 

Feladat

Készíts programot, amely megadja a védett és az őrzött szakaszok számát, valamint azt, hogy minimum hány helyre kell még őrséget küldeni, hogy minden fal őrzött legyen! 

Bemenet

A fal.be szöveges állomány első sorában az őrhelyek száma (1 <= N <= 100) és az őrségek száma (1 <= M <= 100) van, egy szóközzel elválasztva. A következő M sor az őrségek leírását tartalmazza, közülük az i-edik annak az őrhelynek a sorszáma, ahol az i-edik őrség van. Tudjuk, hogy minden helyen legfeljebb 1 őrség van. 

Kimenet

A fal.ki szöveges állományba három sort kell írni! Az első sorba a védett szakaszok száma, a másodikba az őrzött szakaszok száma kerüljön! A harmadik sorba az új őrségek minimális számát kell írni, amivel elérhető, hogy minden fal őrzött legyen! 

Példa

Bemenet  Kimenet
15 9
6
3
12
11
4
5
8
15
14
3 [3-6., 11-12., 14-15.]
2 [2-9., 10-15.]
2 [1., 9.]


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013/2014, 9-10. évfolyam, 2. forduló
Algoritmusok: