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:
|