E - Exclusive☆OR

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100

こちらの問題は現在ジャッジが正常に動作しておらず,提出すると IE (内部エラー) となります.現在原因を調査中です.今しばらくお待ちください.申し訳ありません.ジャッジが正常に動作するようになりました.ご迷惑をおかけしました.

ストーリー

くろうさ「XOR は甘え」

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

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

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

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

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

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

問題文

整数 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 - 1j = 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 % が与えられる.

入力

入力は以下の形式で標準入力から与えられる。

N

出力

問題文の仕様を満たす,NOT の使用回数が最小のプログラムを 1 つ出力せよ.

採点結果の AC は,問題文の仕様を満たすプログラムを出力したことを表す.


入力例 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 の場合はこちらで手で遊べる.

AND と OR はふたつ,NOT はひとつ選んでから演算子ボタンを押そう! (動作確認:Chrome 70, Firefox 60)