← 返回题目列表

AtCoder · xmascon18_e

E. 独家☆或

中文机器翻译题面 查看原题

配点: 100 点

这个问题目前裁判系统无法正常运行,提交将会出现 IE(内部错误)。目前正在调查原因,请稍等。非常抱歉。裁判系统已经恢复正常运行。给您带来不便,十分抱歉。

故事

黑兔子「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 % 的分数。

入力

输入是按以下格式从标准输入给出的。

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)