Problem Description

This is an output-only problem.

While implementing circuits for a robot, you noticed some abnormal behavior. The robot can run $N = 128$ programs, numbered from $0$ to $N - 1$. Normally, at any given time, there should be only one program (among the $N$ programs) running. However, for some unknown reason, sometimes exactly three programs run at the same time. Fortunately, as an experienced programmer, you know how to handle this situation and decide to implement a circuit to detect these anomalies.

First, you create $N$ inputs. If program $i$ is not running, then input $i$ is $0$; otherwise it is $1$. Then, you add logic gates to the circuit, whose indices are consecutively numbered starting from $N$. Each logic gate can take a fixed number of inputs and produce one output, which is either $0$ or $1$. The inputs of gate $i$ can be the output of any logic gate with index less than $i$, or any of the initial $N$ inputs.

There are three types of logic gates:

• NOT: Takes exactly one input. If the input is $0$, the output is $1$; otherwise the output is $0$.
• OR: Takes exactly two inputs. If both inputs are $0$, the output is $0$; otherwise the output is $1$.
• AND: Takes exactly two inputs. If both inputs are $1$, the output is $1$; otherwise the output is $0$.

If an anomaly is detected—that is, exactly three of the first $N$ inputs are $1$—the output of the last logic gate should be $1$. If exactly one of the first $N$ inputs is $1$, then the output should be $0$.

It is guaranteed that the number of $1$'s among the first $N$ inputs is either exactly one or exactly three.

Output Format

You need to write the description of a circuit for $N = 128$ to the output file (output file).

The first line of the output should contain one integer, the number of logic gates used.

Each of the remaining lines of the output should be in one of the following three formats:

NOT in_1
OR in_1 in_2
AND in_1 in_2

They append a NOT, OR, or AND gate, respectively. For NOT, in_1 is the index of the input to this gate. For OR and AND, in_1 and in_2 are the indices of the inputs to this gate. The index of the logic gate appended on line $i$ after the first line is $N - 1 + i$.

The total number of logic gates must not exceed $1024$. In other words, the number of lines in the output file must not exceed $1025$.

Hint

Sample

Consider a simplified version of the task with $N = 4$ (note that you only need to provide a solution for $N = 128$). One possible solution is to build the following circuit.

3
OR 0 1
OR 2 3
AND 4 5

This circuit contains:

• Gate $4$, which outputs $1$ if at least one of inputs $0$ and $1$ is $1$;
• Gate $5$, which outputs $1$ if at least one of inputs $2$ and $3$ is $1$; and
• Gate $6$, which outputs $1$ if both gate $4$ and gate $5$ output $1$.

It can be verified that for all possible inputs, this circuit produces the correct answer.

Subtasks

• ($100$ points) No additional constraints.

Scoring

For each subtask, if there exists any case where the circuit fails (that is, the circuit you designed cannot successfully detect the anomaly), your score will be $0$.

Otherwise, let $K$ be the number of logic gates used in the circuit. Your score will be $f(K) \times [\text{score for this subtask}]$, where:

$$\begin{aligned} 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} \end{aligned}$$

Translated by ChatGPT 5