AT_xmascon18_e.Exclusive☆OR

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数 $N$ ，请编写一个程序，该程序需要在少使用 NOT 操作的情况下实现特定功能（即便不是最少使用 NOT 的情况，也可能获得部分分数）。

程序的输入是 $N$ 个布尔变量 $b_0, b_1, \ldots, b_{N-1}$ 。我们的目标是计算所有可能的组合 $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$ 。

输入格式

从标准输入中读取一个整数 $N$ 。

输出格式

输出一个程序，该程序在保证符合题目要求的情况下，NOT 操作的使用次数最少。如果输出的程序达到了题目要求，则会被判定为 AC。

输入输出样例

输入#1

输出#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]

说明/提示

故事背景

黑兔：「用 XOR 就太耍赖了！」

白兔：「又来了……」

黑兔：「我还可以接受 AND 和 OR。」

白兔：「呃，这个……」

黑兔：「否定是不好的哦～好好。」

白兔：「否定是指 NOT 吗？」

黑兔：「总之，今年也要加油哦！」

约束条件

$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\%$ 。

给予符合要求的程序奖励，不符合要求但次优的程序也能获得部分分数。

通过这些信息，您可尝试优化程序设计，并努力减少 NOT 操作的使用次数。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页