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:

$$\begin{equation*} x_1 \vee x_5 \vee \neg x_3 \vee x_4 \end{equation*}$$

El símbolo $\vee$ es la OR booleana, y el símbolo $\neg$ es la NOT booleana. Así pues, la cláusula es falsa sólo si $x_1$, $x_5$ y $x_4$ son falsas, y $x_3$ 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 $x_i$, y una $i$ negativa indica $\neg x_i$. 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 \le 10$, $m \le 4$ y se garantiza que existe solución.

• Test2:   Casos donde $n \le 10^5$ y $100 \le m \le 10^4$.