Satisfactibilitat P93741
Feu un programa que trobi totes les solucions d’un conjunt de m clàusules c1, …, cm de tres literals en forma normal conjuntiva.
Per exemple, {a = cert, b = fals, c = cert, d = cert} és una solució possible per a les tres clàusules
| a o b o c, no a o b o c, b o no c o d. |
Com un altre exemple, {a = cert, b = fals} és una solució possible per a la clàusula
| b o no a o a. |
Sent rigurosos, aquesta clàusula no té tres literals (de fet és igual a cert, que no en té cap), però en aquest exercici permetem tenir literals repetits dins de la mateixa clàusula.
Entrada
L’entrada consisteix en un natural 1 ≤ n ≤ 20, seguit d’un natural m > 0, seguit de c1, …, cm. Els noms de les variables són les n primeres lletres minúscules, totes les quals apareixen a l’entrada com a mínim una vegada. Els literals negats s’indiquen amb un canvi de signe davant de la variable.
Sortida
Escriviu totes les solucions possibles del conjunt de clàusules. Els literals de cada solució han de sortir en ordre alfabètic. Si no hi ha cap solució, escriviu un guió.
Informació sobre el corrector
Podeu escriure les solucions d’aquest exercici en qualsevol ordre.
Input
4 7 a b c -a -d c a c c -c b -b a -b -c -b -c -d -d -d -d
Output
a b c -d a b -c -d a -b c -d a -b -c -d -a -b c -d
Input
3 5 c c a a b -c -a b b -b -b -b -c -c -b
Output
-
- Author
- Salvador Roura
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++