Mientras implementas un circuito para un robot, notas algunas anomalías. Hay $N = 128$ programas, numerados del $0$ al $N-1$, que el robot puede ejecutar. Normalmente, solo un programa (de los $N$ programas) debería estar ejecutándose en cualquier momento dado. Sin embargo, por razones desconocidas, a veces exactamente tres programas se ejecutan simultáneamente. Afortunadamente, como programador experimentado, sabes cómo manejar esta situación y decides implementar un circuito para detectar tales anomalías.
Primero creas $N$ entradas. La $i$-ésima entrada es $0$ si el $i$-ésimo programa no se está ejecutando, y $1$ en caso contrario. Luego, añades puertas, las cuales tienen índices numerados consecutivamente comenzando desde $N$. Cada puerta puede tomar un cierto número de entradas y producir una única salida, ya sea $0$ o $1$. Las entradas de la $i$-ésima puerta pueden ser la salida de cualquier puerta con índice menor que $i$, o cualquiera de las $N$ entradas iniciales.
Existen tres tipos de puertas:
NOT: toma exactamente una entrada. La salida es $1$ si la entrada es $0$, y $0$ en caso contrario.OR: toma exactamente dos entradas. La salida es $0$ si ambas entradas son $0$, y $1$ en caso contrario.AND: toma exactamente dos entradas. La salida es $1$ si ambas entradas son $1$, y $0$ en caso contrario.
La salida de la última puerta debe ser $1$ si se detecta una anomalía (es decir, si exactamente tres de las primeras $N$ entradas son $1$) y $0$ si exactamente una de las primeras $N$ entradas es $1$.
Se garantiza que el número de $1$s entre las primeras $N$ entradas es o bien exactamente uno o bien exactamente tres.
Detalles de implementación
Debes escribir en un archivo de salida describiendo un circuito válido para $\color{red}{N = 128}$.
La primera línea de la salida debe contener un entero que represente el número de puertas utilizadas.
Cada línea del resto de la salida debe seguir uno de los siguientes tres formatos:
NOT in_1 OR in_1 in_2 AND in_1 in_2
Cada una añade una puerta NOT, OR o AND, respectivamente. Para NOT, in_1 es el índice de la entrada de la puerta. Para OR y AND, in_1 e in_2 son los índices de las entradas de la puerta. El índice de la puerta añadida en la $i$-ésima línea después de la primera línea es $N-1 + i$.
El número total de puertas no debe exceder $1024$. En otras palabras, el número total de líneas en el archivo de salida no debe exceder $1025$.
Subtareas
- (100 puntos) Sin restricciones adicionales.
Puntuación
Para cada subtarea, si existe un caso que el circuito no supera, tu puntuación será $0$.
De lo contrario, sea $K$ el número de puertas utilizadas por el circuito. Tu puntuación será $f(K) \times$ [la puntuación de la subtarea], donde:
$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$
Figura 1: La puntuación de la tarea para cada valor de $K$
Debes escribir tu solución en el archivo de salida 1.out, luego comprimir los archivos de salida en un único archivo .zip y enviar el archivo .zip.
Ejemplos
Entrada 1
(input data)
Salida 1
3 OR 0 1 OR 2 3 AND 4 5
Nota
Considera una versión simplificada de la tarea con $N = 4$ (Ten en cuenta que solo necesitas proporcionar la solución para $N = 128$). Una posible solución es construir el siguiente circuito. El circuito tiene:
- la puerta $4$ que emite $1$ si al menos una de las entradas $0$ o $1$ es $1$;
- la puerta $5$ que emite $1$ si al menos una de las entradas $2$ o $3$ es $1$; y
- la puerta $6$ que emite $1$ si tanto la salida de la puerta $4$ como la de la puerta $5$ es $1$.
Se puede verificar que para todas las entradas posibles, el circuito da la respuesta correcta.