Balkáni Informatikai Olimpia 1999

Egy szegény ország elkülönített területén N város található utakkal összekötve. Bármely két város összeköttetésben van egymással, de a kapcsolat nem feltétlenül közvetlen. Az utak egyike sincs kikövezve. A kormányzatnak érdeke az utak kikövezése az alábbi feltételek mellett:

• bármely városból bármely másikba el lehessen kövezett úton jutni
• nem tartják meg a le nem kövezett utakat.

A kiválasztás érdekében a kormányzat kíváncsi az összes lehetséges kövezési módot.

Bemenet:

A bemeneti állomány (INPUT.TXT) első sorában az N és R érték szerepel, ahol N a városok száma (2 <= N <= 20), az R az utak száma (N-1 <= R <= 190). E számok szóközzel vannak elválasztva. A következő R sor írja le a közvetlen összeköttetésben lévő várospárok K és L sorszámát (0<= K, L <= N-1).

Kimenet:

A kimeneti állományba (OUTPUT.TXT) egyetlen számot, a lehetséges kikövezések számát kell bejegyezni.

Példa:

INPUT.TXT	OUTPUT.TXT
4 4 0 2 0 1 0 3 1 3	3

A fordítós egy régi egyszemélyes játék neve. M sorban és 9 oszlopban kártyákat helyezünk el, melyek egyik oldala fehér másik fekete. Ha egy fehér oldalát mutató lapot megfordítunk, fekete lesz.

A játék során egy lépésben teljes sor, illetve teljes oszlop lapjait lehet megfordítani.

Elképzelhető, hogy bármennyi műveletet is hajtunk végre, mindig maradnak fekete oldalukat mutató lapok.

Bemenet:

A bemeneti állomány (INPUT.TXT) első sorában a csúcspontok N száma olvasható. Az első sorban lévő szám a játéktábla sorainak számát adja. (1 <= M <= 1000). A következő M sor pontosan 9 számot tartalmaz, 0 és 1 számjegyeket egyetlen 0 választja el egymástól. A 0 jelenti a fehér, 1 pedig a fekete oldalt.

Kimenet:

A kimeneti állománynak (OUTPUT.TXT) a "legfehérebb" állapotban található fekete lapok számát kell tartalmaznia.

Példa:
 

INPUT.TXT	OUTPUT.TXT
4 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0	1

Az El Greco galéria olyan szobát tartalmaz, melynek falai észak-déli, illetve kelet-nyugati tájolásúak. Azeonkívül a falak felülnézeti képben egyetlen zárt sokszöget alkotnak. Drága festmények lógnak minden falon, ezért a galéria tulajdonosai egy őrző-védő céget bíznak meg a szoba felügyeletével. Ezért szeretnék meghatározni a szoba azon pontját, ahonnan minden fal látható. A falat láthatónak tekintjük, akkor is, ha az őr egyvonalban áll a fallal.

Bemenet:

A bemeneti állomány (INPUT.TXT), első sorában a szoba sarkainak száma található (4 <= N <= 1000). A következő N sorban lévő számpárok X és Y értéke az adott sorszámú sarok koordinátáit adják az óramutató járásának megfelelően. (0 <= X, Y <= 1000)

Kimenet:

A kimeneti állomány (OUTPUT.TXT) csak egy sort tartalmaz, annak a pontnak a koordinátáit, ahonnan a galéria őre belátja az összes falat. A koordinátákat szóközzel választjuk el egymástól. Ha több lehetséges pont van, elegendő egy megoldást adni. Ha egyetlen pozíció sem megfelelő, akkor az állományba a "NO POINT" szöveget kell írni.

Példa:
 

INPUT.TXT	OUTPUT.TXT
6 0 0 0 50 50 50 50 100 100 100  100 0	70 10