ロボットの回路を実装している最中に、いくつかの異常に気づきました。ロボットが実行する可能性のあるプログラムが $N = 128$ 個あり、それぞれ $0$ から $N-1$ までの番号が振られています。通常、ある瞬間に実行されるプログラムは（$N$ 個のうち）ただ 1 つであるはずです。しかし、何らかの理由で、時折ちょうど 3 つのプログラムが同時に実行されることがあります。幸い、経験豊富なプログラマであるあなたは、この状況に対処する方法を知っており、そのような異常を検出するための回路を実装することにしました。
まず、$N$ 個の入力を作成します。$i$ 番目の入力は、$i$ 番目のプログラムが実行されていなければ $0$、実行されていれば $1$ となります。次に、ゲートを追加します。ゲートには $N$ から始まる連続した番号が割り当てられます。各ゲートは一定数の入力を受け取り、単一の出力（$0$ または $1$）を生成します。 $i$ 番目のゲートの入力には、番号が $i$ 未満のゲートの出力、または初期の $N$ 個の入力のいずれかを使用できます。
ゲートには以下の 3 種類があります。
NOT: 入力をちょうど 1 つ受け取ります。入力が $0$ なら出力は $1$、入力が $1$ なら出力は $0$ となります。OR: 入力をちょうど 2 つ受け取ります。両方の入力が $0$ なら出力は $0$、それ以外なら出力は $1$ となります。AND: 入力をちょうど 2 つ受け取ります。両方の入力が $1$ なら出力は $1$、それ以外なら出力は $0$ となります。
最後のゲートの出力は、異常が検出された場合（つまり、最初の $N$ 個の入力のうちちょうど 3 つが $1$ である場合）に $1$ となり、最初の $N$ 個の入力のうちちょうど 1 つが $1$ である場合に $0$ となる必要があります。
最初の $N$ 個の入力のうち $1$ であるものの数は、ちょうど 1 つまたはちょうど 3 つのいずれかであることが保証されています。
実装の詳細
$\color{red}{N = 128}$ に対する有効な回路を記述した出力ファイルを作成してください。
出力の最初の行には、使用したゲートの数を表す整数を記述します。
残りの各行は、以下の 3 つの形式のいずれかである必要があります。
NOT in_1 OR in_1 in_2 AND in_1 in_2
それぞれ、NOT、OR、AND ゲートを追加します。NOT の場合、in_1 はそのゲートの入力のインデックスです。OR および AND の場合、in_1 と in_2 はそのゲートの入力のインデックスです。最初の行の後に続く $i$ 行目に追加されるゲートのインデックスは $N-1 + i$ となります。
ゲートの総数は $1024$ を超えてはなりません。つまり、出力ファイルの総行数は $1025$ を超えてはなりません。
小課題
- (100 点) 追加の制約はありません。
スコアリング
各小課題において、回路が正しく動作しないケースが存在する場合、スコアは $0$ となります。
それ以外の場合、$K$ を回路で使用したゲートの数とします。あなたのスコアは $f(K) \times$ [小課題の配点] となり、$f(K)$ は以下のように定義されます。
$$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}$$
図 1: 各 $K$ に対するタスクのスコア
解答は 1.out という名前の出力ファイルに書き込み、それらの出力ファイルを 1 つの .zip ファイルに圧縮して提出してください。
入出力例
$N = 4$ の場合の簡略化されたタスクを考えます（$N = 128$ の場合の解答のみを提供すればよいことに注意してください）。考えられる解決策として、以下の回路を構築します。
3 OR 0 1 OR 2 3 AND 4 5
この回路は以下のように動作します。
- ゲート $4$ は、入力 $0$ または $1$ の少なくとも一方が $1$ ならば $1$ を出力します。
- ゲート $5$ は、入力 $2$ または $3$ の少なくとも一方が $1$ ならば $1$ を出力します。
- ゲート $6$ は、ゲート $4$ とゲート $5$ の両方の出力が $1$ ならば $1$ を出力します。
すべての可能な入力に対して、この回路が正しい答えを出すことを確認できます。