4-SAT P37529


Statement
 

pdf   zip

thehtml

El conocido problema 4-SAT consiste en lo siguiente: Tenemos m variables booleanas (sólo pueden valer cierto o falso). Además, tenemos n cláusulas, formadas cada una por cuatro variables, no necesariamente diferentes. Veamos un ejemplo de clásula:

x1 ∨ x5 ∨ ¬ x3 ∨ x4

El símbolo ∨ es la OR booleana, y el símbolo ¬ es la NOT booleana. Así pues, la cláusula es falsa sólo si x1, x5 y x4 son falsas, y x3 es cierta.

El problema 4-SAT original pide asignar valores a las variables de manera que todas las cláusulas sean ciertas, o decir que no hay solución. Como ese problema es demasiado difícil, os pedimos una versión más sencilla: ¿Podéis encontrar una asignación tal que al menos el 90% de las cláusulas sean ciertas?

Entrada

La entrada tiene diversos casos. Cada uno empieza con n y m, seguidas de las n claúsulas, codificadas con cuatro enteros entre −m y m, sin ningún cero. Una i positiva indica xi, y una i negativa indica ¬ xi. Se garantiza que la entrada se ha generado de forma aleatoria.

Salida

Escribid una línea para cada caso. Si no existe solución, escribid “WA”. Si existe, escribid m ‍caracteres indicando el valor de las variables en orden: ‘0’ para falso y ‘1’ para cierto. Si hay más de una posible asignación, cualquiera sirve.

Puntuación

  • Test1:  ‍ Casos donde n ≤ 10, m ≤ 4 y se garantiza que existe solución.  ‍50 Puntos ‍
  • Test2:  ‍ Casos donde n ≤ 105 y 100 ≤ m ≤ 104.  ‍50 Puntos ‍
Public test cases
  • Input

    2 4
    -2 3 -4 3
    -2 1 2 -2
    
    2 3
    -2 -1 -2 1
    2 2 -3 -1
    
    5 3
    1 2 2 2
    1 3 3 3
    -1 -2 -2 -2
    -1 2 2 2
    1 3 3 3
    
    2 5
    -4 -5 -5 -4
    2 1 -2 -4
    
    4 6
    -4 2 -2 -3
    -4 -6 1 -6
    -3 -6 -1 -1
    1 -2 -3 6
    

    Output

    1011
    110
    011
    00000
    101100
    
  • Information
    Author
    Alex Alvarez Ruiz
    Language
    Spanish
    Official solutions
    C++
    User solutions