Zadanie

Tina rada organizuje párty pre svojich spolužiakov. Zorganizovať dobrú párty však nie je len tak. Medzi jej spolužiakmi panujú rôzne vzťahy. Napríklad Miro teraz strašne letí na Zuzu. Ak Tina pozve na párty Zuzu, určite musí pozvať aj Mira, inak by jej to do smrti vyčítal. No a Zuza sa minule strašne pohádala s Helou, a tak ak Tina pozve jednu z nich, určite nechce pozvať zároveň aj tú druhú. A tak ďalej.

Keď si tak Tina spísala všetky požiadavky koho môže a nemôže pozvať, zistila, že existujú presne tri možnosti, akú množinu spolužiakov na párty pozvať. Zorganizovala preto postupne tri párty – jednu pre každú možnosť.

Tina ti dala pre každú párty zoznam ľudí, ktorí sa jej zúčastnili. Nájdi jednu možnosť toho, ako vyzerajú vzťahy medzi ľuďmi v triede.

Úloha

Ľudí v triede si očíslujeme od \(1\) po \(n\).

Budeme uvažovať len jeden typ podmienok: implikácie. Každá podmienka má teda tvar “ak (niekto je alebo nie je na párty) tak (niekto musí alebo nesmie byť na párty)”. To, že človek \(x\) je/musí byť na párty, v podmienke zapíšeme \(+x\). To, že tam nie je/nesmie byť, zapíšeme \(-x\).

Na vstupe sú dané tri množiny ľudí, ktoré boli na párty. Zostrojte konkrétnu sadu implikácií, pre ktorú bude platiť, že existujú presne tri spôsoby, ako ich všetky naraz splniť, a tieto tri spôsoby zodpovedajú daným trom množinám ľudí.

Formát vstupu

V prvom riadku vstupu je číslo \(n\): počet ľudí v triede. Zvyšok vstupu tvoria tri riadky. V každom riadku je \(n\) núl alebo jednotiek: postupne od človeka \(1\) po človeka \(n\) je tam \(0\) ak na párty nebol, a \(1\) ak na nej bol.

Vstupom môžu byť ľubovoľné tri \(n\)-tice núl a jednotiek. Nie je teda zaručené, že hľadaná sada implikácií musí existovať.

Je päť sád vstupov. Postupne majú maximálnu hodnotu \(n\) rovnú \(3\), \(5\), \(10\), \(20\) a \(50\).

Formát výstupu

Ak neexistuje žiadna sada implikácií s požadovanou vlastnosťou, vypíšte jeden riadok a v ňom číslo \(-1\).

Ak existujú nejaké vyhovujúce sady implikácií, nájdite nejakú dostatočne malú. Presnejšie, sada, ktorú vypíšete, musí mať nanajvýš \(470\) implikácií. Vypíšte ju v nasledovnom formáte: najskôr riadok obsahujúci číslo \(p\) udávajúce počet implikácií, potom \(p\) riadkov a v každom z nich implikácia tvaru “ak [cislo] tak [cislo]”.

(Je zaručené, že ak existuje nejaká sada implikácií, existuje aj dostatočne malá sada.)

Príklady

Input:

3
0 0 0
0 1 0
1 0 0

Output:

ak +1 tak -2
ak +3 tak +1
ak +3 tak +2

Tina má troch kamarátov. Nazvime ich Anka (1), Boris (2) a Cecil (3). Na prvej párty nebol nik z nich. Na druhej bol len Boris. Na tretej bola len Anka. Ako môže vyzerať sada implikácií, pre ktorú sú toto jediné tri možnosti, koho pozvať?

Existuje veľa možností. Tá uvedená v príklade výstupu má nasledujúci význam: Ak Tina pozve Anku, nesmie pozvať Borisa. Ak pozve Cecila, musí pozvať Anku aj Borisa.

Logicky si odvoďme, koho môže Tina pozvať pre túto sadu implikácií. Ak by pozvala Cecila, tak z druhej a tretej implikácie musí pozvať aj zvyšných dvoch, to však spôsobí spor s prvou implikáciou. Preto Cecil má smolu a na žiadnej párty nebude. Do úvahy tiež nepripadá párty, na ktorej sú Anka s Borisom – opäť pre spor s prvou implikáciou. No a ľahko overíme, že už ostali len tie tri možnosti, ktoré boli zadané na vstupe, a že žiadna z nich k sporu nevedie.

Existujú aj iné správne riešenia. Mohli sme napríklad použiť aj implikáciu “ak +3 tak -3”, z ktorej by tiež vyplývalo, že Cecil na žiadnu párty nesmie.

Input:

4
0 0 1 0
1 0 0 0
1 0 1 1

Output:

-1

Neexistuje sada implikácií, pre ktorú by boli prípustné len tieto tri zloženia účastníkov párty a žiadne iné.

Úloha má viac možných riešení, ukážeme si to, ktoré sa asi najľahšie implementuje.

Dvaja ľudia sú ekvivalentní, ak boli na tej istej množine párty. Ak máme vo vstupe dvoch ekvivalentných ľudí, napríklad Maru a Usamca, môžeme sa jedného z nich zbaviť tak, že do výstupu pridáme implikácie “ak Maru tak Usamec” a “ak Usamec tak Maru”.

Keďže boli len tri párty, existuje len \(8\) rôznych typov ľudí. (Jeden z nich sú napr. ľudia, ktorí boli len na prvej párty, čiže tí, čo majú na vstupe stĺpec 100.) Keď sme sa zbavili ekvivalentných ľudí, ostal nám teda vstup, v ktorom je nanajvýš osem ľudí.

Už v tomto okamihu by sa dala na doriešenie úlohy vhodne použiť hrubá sila, ale porozmýšľajme ešte.

Ak máme človeka Quasimoda, ktorý nebol na žiadnej párty, zbavíme sa ho pridaním podmienky “ak Quasimodo tak nie Quasimodo”. A naopak, ak máme jeho opak Esmeraldu, tej sa zbavíme podmienkou “ak nie Esmeralda tak Esmeralda”. A už nám ostalo ľudí len šesť.

Dvaja ľudia sú opační, ak bol na každej párty práve jeden z nich. Ak máme vo vstupe dvoch opačných ľudí, tiež sa vieme jedného zbaviť. Ak sú napríklad Jekyll a Hyde opační, stačí pridať implikácie “ak Jekyll tak nie Hyde” a “ak Hyde tak nie Jekyll”.

A keď sme sa zbavili aj opačných ľudí, ostal nám vstup s nanajvýš troma ľuďmi.

To isté si teraz môžeme povedať aj matematicky. Máme \(n\) boolovských premenných a snažíme sa napísať logický výraz, ktorý bude splnený pre práve tri kombinácie hodnôt premenných, a to pre tie tri predpísané na vstupe. Vyššie uvedeným postupom sme zostrojili časť tohto výrazu: zbavili sme sa konštánt, ekvivalentných premenných, aj premenných, ktoré sú negáciou jedna druhej. Skončili sme v situácii, že máme nanajvýš tri voľné premenné. Keď zvolíme ich pravdivostné hodnoty, nami zostrojená sada implikácií jednoznačne určí hodnoty všetkých ostatných premenných. A ľahko nahliadneme, že všetky tri ohodnotenia zo vstupu sa nachádzajú medzi tými ohodnoteniami, ktoré takto vieme dostať.

Sú len dve možnosti: buď máme voľné premenné presne dve, alebo presne tri. (Rozumiete, prečo sa nemôže stať, že by bola len jedna?)

Ak sú presne dve, je doteraz zostrojený výraz pravdivý pre štyri rôzne ohodnotenia premenných, a my z nich potrebujeme ešte zakázať to jedno, ktoré nechceme. Toto sa vždy dá dosiahnuť. Predstavme si napríklad, že tie dve voľné premenné sú ľudia Rasťo a Marína, ktorým na vstupe zodpovedajú stĺpce 101 a 001. Potom potrebujeme vylúčiť možnosť, v ktorej má Rasťo 0 a Marína 1, čiže možnosť, že Rasťo na párty nebol a Marína áno. Toto spravíme pridaním implikácie “ak Marína tak Rasťo”. Analogicky vieme postupovať pre ľubovoľné dve voľné premenné.

Ak sú voľné premenné presne tri, má doteraz zostrojená sada implikácií osem vyhovujúcich ohodnotení premenných. Spomedzi týchto by sme chceli tie tri dobré nechať a zvyšných päť zlých zakázať. Dá sa ale dokázať (rozmyslite si, ako), že toto nikdy nejde spraviť. Ak teda po spravení všetkých redukcií počtu premenných vidíme tri voľné premenné, úloha nemá riešenie.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.