Satisfactibilitat P93741


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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

    -
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++