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 |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
