Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | 2sat.in, 2sat.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 0.425 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
2SAT
Problema satisfiabilitatii, notata prescurtat cu SAT cere determinarea existentei unei atribuiri satisfiabile pentru o formula booleana. O atribuire de valori booleene pentru variabilele acestei expresii se numeste atribuire satisfiabila daca evaluarea expresiei dupa atribuirea valorilor da rezultat ca valoare de adevar "adevarat". Un exemplu de formula ar fi:
((x1 SAU x2) SI ((NOT x3) SI x1) SAU x4)
aceasta avand o atribuire satisfiabila x1=1 x2=0 x3=0 x4=1.
Orice formula booleana poate fi transformata in 2 forme: forma normal conjunctiva (expresia este scrisa ca o conjunctie de propozitii P1 SI P2 SI ... SI Pn, unde Pi este de forma T1 SAU T2 SAU ... SAU Tk, Tj fiind un termen care poate sau nu sa fie negat) si forma normal disjunctiva (expresia este scrisa ca o disjunctie de propozitii in interiorul carora exista doar conjunctii intre termeni). In rezolvarea acestei probleme ne intereseaza doar forma normal conjunctiva.
Problema SAT este NP-completa, chiar si daca restrictionam expresiile la unele care in forma normal conjunctiva au doar 3 termeni in fiecare dintre propozitii. Problema satisfiabilitatii pentru asemenea expresii se numeste 3SAT. Problema 2SAT (2 termeni in fiecare din propozitiile care alcatuiesc forma normal conjunctiva) este rezolvabila in timp polinomial.
Un exemplu de expresie 2SAT este:
(x1 SAU x3) SI (x2 SAU (NOT x1)) SI ((NOT x4) SAU x3)
Cerinta
Dandu-se o expresie 2SAT sa se determine o atribuire satisfiabila a acesteia.
Date de intrare
Fişierul de intrare 2sat.in va contine pe prima linie 2 numere naturale, N - numarul de termeni care apar in expresie si M - numarul de propozitii disjunctive din care este formata expresia. Pe fiecare dintre urmatoarele M linii se vor afla cate 2 numere intregi, numerele de ordine ale termenilor prezenti in fiecare dintre propozitii. Semnul - in fata unui numar reprezinta ca termenul respectiv apare negat in expresie.
Date de ieşire
În fişierul de ieşire 2sat.out se vor afisa N numere naturale, 0 sau 1, reprezentand o atribuire satisfiabila pentru expresia data in fisierul de intrare.
Restricţii
- 1 ≤ N ≤ 100000
- 1 ≤ M ≤ 100000
Exemplu
| 2sat.in | 2sat.out |
|---|---|
| 4 5 1 -2 -1 -3 1 2 4 -3 4 -1 | 1 0 0 1 |
Indicatii pentru rezolvare
O solutie evidenta este incercarea celor 2N configuratii posibile pentru termenii expresiei si apoi verificarea lor, aceasta abordare ducand la o complexitate de O(2N * M). Cu aceasta complexitate se obtin 20 de puncte, iar o sursa demonstrativa se gaseste aici.
Următoarea soluţie pare trivială, dar găsirea acestui algoritm şi realizarea faptului că el rezolvă corect problema sunt mai grele decât impresia lăsată după citirea ei. Considerăm o propoziţie oarecare cu două variabile p şi q, apoi una dintre ele, de exemplu p. Ii atribuim lui p valoarea 0. Pentru ca propoziţia respectivă să aibă 1 valoarea de adevăr, atunci valoarea lui q trebuie fixată. Fixând si valoarea lui q, probabil si alte propoziţii ce conţin literalul q vor avea celălalt literal fixat. Propagăm astfel o serie de schimbări. După ce toate schimbările forţate au fost făcute, propoziţiile rezultate vor fi de următoarele tipuri: A SAU B, 1 SAU 0, 1 SAU 1, 1 SAU B. Propozitii de tipul 0 SAU B nu pot aparea, pentru ca toate schimbarile fortate au fost deja propagate. Dacă apare o propoziţie 0 SAU 0 atunci alegerea făcută pentru valoarea lui p este greşită. Vom încerca şi alegerea opusă pentru p. Dacă ambele duc la o propoziţie de tip atunci expresia nu poate fi satisfăcută. Propoziţiile de forma 1 SAU 0, 1 SAU 1, 1 SAU B pot fi ignorate. În acest fel am eliminat cel puţin o variabilă şi o propoziţie din expresie. Dacă expresia iniţială era satisfiabilă, atunci şi expresia din care s-au eliminat câteva propoziţii a rămas satisfiabilă. Continuând pe această idee obţinem un algoritm de complexitate O(N * M), pentru că la fiecare atribuire de valoare pentru o variabilă parcurgem şirul de propoziţii o dată.
