在为机器人实现电路时,你发现了一些异常情况。机器人可能会运行 $N = 128$ 个程序,编号从 $0$ 到 $N-1$。通常情况下,在任何给定时刻都应该只有一个程序(在 $N$ 个程序中)在运行。然而,由于某些未知原因,有时会恰好有三个程序同时运行。幸运的是,作为一名经验丰富的程序员,你知道如何处理这种情况,并决定实现一个电路来检测此类异常。
你首先创建 $N$ 个输入。如果第 $i$ 个程序没有运行,则第 $i$ 个输入为 $0$,否则为 $1$。然后,你添加门电路,其索引从 $N$ 开始连续编号。每个门可以接收一定数量的输入,并产生一个输出($0$ 或 $1$)。 第 $i$ 个门的输入可以是索引小于 $i$ 的任何门的输出,或者是最初的 $N$ 个输入中的任意一个。
门电路有三种类型:
NOT:恰好接收一个输入。如果输入为 $0$,则输出为 $1$,否则输出为 $0$。OR:接收两个输入。如果两个输入均为 $0$,则输出为 $0$,否则输出为 $1$。AND:接收两个输入。如果两个输入均为 $1$,则输出为 $1$,否则输出为 $0$。
如果检测到异常(即前 $N$ 个输入中恰好有三个为 $1$),则最后一个门的输出应为 $1$;如果前 $N$ 个输入中恰好有一个为 $1$,则输出应为 $0$。
保证前 $N$ 个输入中 $1$ 的个数要么恰好是一个,要么恰好是三个。
实现细节
你需要编写一个输出文件,描述一个针对 $\color{red}{N = 128}$ 的有效电路。
输出的第一行应包含一个整数,表示所使用的门的数量。
输出的其余部分,每一行应为以下三种格式之一:
NOT in_1 OR in_1 in_2 AND in_1 in_2
每一行分别添加一个 NOT、OR 或 AND 门。对于 NOT,in_1 是该门输入的索引。对于 OR 和 AND,in_1 和 in_2 是该门输入的索引。在第一行之后的第 $i$ 行添加的门的索引为 $N-1 + i$。
门的总数不应超过 $1024$。换句话说,输出文件的总行数不应超过 $1025$。
子任务
- (100 分) 无额外限制。
评分
对于每个子任务,如果存在电路无法通过的情况,你的得分为 $0$。
否则,令 $K$ 表示电路所使用的门数量。你的得分为 $f(K) \times$ [子任务的分数],其中:
$$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$$
图 1:每个 $K$ 值对应的任务得分
你需要将你的解决方案写入输出文件 1.out,然后将输出文件压缩成一个 .zip 文件并提交该 .zip 文件。
样例
考虑一个 $N = 4$ 的简化版任务(注意,你只需要提供 $N = 128$ 的解决方案)。一种可能的解决方案是构建以下电路。
3 OR 0 1 OR 2 3 AND 4 5
该电路包含:
- 门 $4$,如果输入 $0$ 或 $1$ 中至少有一个为 $1$,则输出 $1$;
- 门 $5$,如果输入 $2$ 或 $3$ 中至少有一个为 $1$,则输出 $1$;以及
- 门 $6$,如果门 $4$ 和门 $5$ 的输出均为 $1$,则输出 $1$。
可以验证,对于所有可能的输入,该电路都能给出正确答案。