h2(#party). 'Party':problema/party (preOni 2003/2004)

bq. George vrea să îşi organizeze majoratul, şi vrea ca petrecerea să fie de neuitat, mâncarea, băutura, locaţia şi sonorizarea sunt deja asigurate, mai rămâne problema chemării prietenilor. El şi cu prietenul lui cel mai bun Lucian au preferinte diferite şi pentru a nu se certa au pus la punct o listă de cerinţe care vor trebui să fie îndeplinite astfel încât cheful să se desfăşoare în cele mai bune condiţii! Pentru uşurinţă,  prietenii lui George vor fi indentificaţi prin numere întregi de la $1$ la $N (1 ≤ N ≤ 100)$ şi cerinţele în număr de $M  (1 ≤ M ≤ 1.000)$ vor fi de tipurile $0$, $1$, $2$ sau $3$. O cerinţă de genul $x y 0$ are semnificaţia că $x$ sau $y$ trebuie să participe la petrecere; $x y 1$ are semnificaţia că dacă $x$ participă nu există nici o restricţie pentru $y$, dar dacă $x$ nu participă atunci nici $y$ nu participa; $x y 2$ are semnificaţia simetrică cu cerinţa $1$; iar cerinţa $x y 3$ are semnificaţia că cel puţin unul dintre $x$ si $y$ nu participă la petrecere. Scrieţi un program care să-i ajute pe cei doi să determine care persoane vor fi invitate la petrecere. Se garantează că va fi posibilă întotdeauna organizarea unei petreceri!

bq. George vrea să îşi organizeze majoratul, şi vrea ca petrecerea să fie de neuitat, mâncarea, băutura, locaţia şi sonorizarea sunt deja asigurate, mai rămâne problema chemării prietenilor. El şi cu prietenul lui cel mai bun Lucian au preferinte diferite şi pentru a nu se certa au pus la punct o listă de cerinţe care vor trebui să fie îndeplinite astfel încât cheful să se desfăşoare în cele mai bune condiţii! Pentru uşurinţă,  prietenii lui George vor fi indentificaţi prin numere întregi de la $1$ la $N (1 ≤ N ≤ 100)$ şi cerinţele în număr de $M  (1 ≤ M ≤ 1.000)$ vor fi de tipurile $0$, $1$, $2$ sau $3$. O cerinţă de genul $x y 0$ are semnificaţia că $x$ sau $y$ trebuie să participe la petrecere; $x y 1$ are semnificaţia că dacă $x$ participă nu există nici o restricţie pentru $y$, dar dacă $x$ nu participă atunci nici $y$ nu participa; $x y 2$ are semnificaţia simetrică cu cerinţa $1$; iar cerinţa $x y 3$ are semnificaţia că cel puţin unul dintre $x$ si $y$ nu participă la petrecere. Scrieţi un program care să-i ajute pe cei doi să determine care persoane vor fi invitate la petrecere. Se garantează că va fi posibilă întotdeauna organizarea unei petreceri!

h3. Soluţie

Este evident că şi această problemă se poate uşor transforma într-o instanţă de $2SAT$. Fiecare turist ne dă prin dorinţele sale o expresie literală cu doi literali. Vizitarea sau nevizitarea oraşului de index $i$ va fi reprezentată prin variabila booleană <tex> A_{i} </tex>.  Exemplul din problemă poate fi transformat astfel: <tex> (A_{1} \vee \sim A_{2}) \wedge (A_{2} \vee A_{4}) \wedge (A_{3} \vee A_{1}) </tex>.