QOJ.ac

QOJ

总分: 100 仅输出

#18421. 三重电路

统计

在为机器人实现电路时,你发现了一些异常情况。机器人可能会运行 $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

每一行分别添加一个 NOTORAND 门。对于 NOTin_1 是该门输入的索引。对于 ORANDin_1in_2 是该门输入的索引。在第一行之后的第 $i$ 行添加的门的索引为 $N-1 + i$。

门的总数不应超过 $1024$。换句话说,输出文件的总行数不应超过 $1025$。

子任务

  1. (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$。

可以验证,对于所有可能的输入,该电路都能给出正确答案。


或者逐个上传:

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.