4-SAT P37529
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
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
- Author
- Alex Alvarez Ruiz
- Language
- Spanish
- Official solutions
- C++
- User solutions