ストーリー

くろうさ「XOR は甘え」

しろうさ「まーた始まった」

くろうさ「AND と OR は許してあげる」

しろうさ「えっとえっと」

くろうさ「否定はよくないよね〜うんうん」

しろうさ「否定ってもしかして NOT のこｔ

くろうさ「というわけで今年もがんばってねっ」

問題文

整数 N が与えられたとき，以下の仕様を満たすプログラムのうち，プログラム中での NOT の使用回数が最小のものを 1 つ出力せよ (NOT の使用回数が最小でないときも，後述のように部分点が与えられる場合がある)．

プログラムの入力は N 個のブール変数 b_0, b_1, \ldots, b_{N-1} であり，これらから 2 個を選んで XOR をとった値 b_i \operatorname{XOR} b_j をすべて求めたい．

プログラムは以下の N + N^2 + 10^5 個のブール変数 (true または false の値をとる) を扱うことができる：

• \mathrm{in}[i]   (i = 0, 1, \ldots, N - 1)
• \mathrm{out}[i][j]   (i = 0, 1, \ldots, N - 1，j = 0, 1, \ldots, N - 1)
• \mathrm{a}[k]   (k = 0, 1, \ldots, 10^5 - 1)

プログラムは 0 行以上 10^5 行以下からなり，上から下へと実行される．各行は

• 変数 = 変数 AND 変数
• 変数 = 変数 OR 変数
• 変数 = NOT 変数

のいずれかの形であり，右辺の計算結果を左辺の変数に代入することを表す．

実行開始時に，各 \mathrm{in}[i] は入力 b_i で，各 \mathrm{out}[i][j] および各 \mathrm{a}[k] は false で初期化される．実行終了時に，各 \mathrm{out}[i][j] の値は b_i \operatorname{XOR} b_j でなければならない．

制約

• 1 \le N \le 16

部分点

• N \le 2 を満たすデータセットに正解した場合は，10 点が与えられる．
• N \le 3 を満たすデータセットに正解した場合は，上記とは別に 10 点が与えられる．
• N \le 4 を満たすデータセットに正解した場合は，上記とは別に 20 点が与えられる．
• N \le 8 を満たすデータセットに正解した場合は，上記とは別に 20 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 40 点が与えられる．
• 各データセットについて，正解ではないが，すべての入力について NOT の使用回数が N - 1 以下の正しいプログラムを出力した場合，そのデータセットの配点の 20 % が与えられる．

入力例 1

3

出力例 1

a[0] = NOT in[0]
a[1] = NOT in[1]
a[2] = NOT in[2]
a[901] = in[0] AND a[1]
a[902] = in[0] AND a[2]
a[910] = in[1] AND a[0]
a[912] = in[1] AND a[2]
a[920] = in[2] AND a[0]
a[921] = in[2] AND a[1]
out[0][1] = a[901] OR a[910]
out[0][2] = a[902] OR a[920]
out[1][0] = a[910] OR a[901]
out[1][2] = a[912] OR a[921]
out[2][0] = a[920] OR a[902]
out[2][1] = a[921] OR a[912]

このプログラムは，3 回の NOT の使用によって XOR をすべて計算している．ただし，NOT の使用回数はこれが最小ではない．

N = 3 の場合はこちらで手で遊べる． 表示/非表示