Programozás‎ > ‎Feladatok‎ > ‎

Nagy Fal

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. Ha egy helyen több őrség is van, akkor a feleslegesek elküldhetők más őrhelyre (egynek azonban ott kell maradnia). 

Feladat

Írjunk programot, ami megadja a védett és az őrzött szakaszok számát, valamint azt, hogy a felesleges őrségek jó helyre küldésével hány további fal tehető védetté, illetve őrzötté! (Az utóbbi két feladathoz lehetséges, hogy a felesleges őrségeket más-más helyre kellene küldeni.)

Bemenet

A nagyfal.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.

Kimenet

A nagyfal.ki szöveges állományba négy 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 a védetté, a negyedik sorba az őrzötté tehető újabb falak számát kell írni!

Példa

Bemenet  Kimenet
12 9
6
3
12
11
4
5
8
6
6
2 [a 3-6 és a 11-12 között]
2 [a 2-9 és 10-12 közötti]
3 [pl. a 6-7,7-8 és 2-3 közötti]
3 [az 1-2 és a 9-10 közötti]



Tesztadatok

Címkék

A feladat forrása: NTOITV, 2013-2014, 2. forduló, 11-13. évfolyam
Algoritmusok: 

megoldás