配点: 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)