← 返回题目列表

AtCoder · joigsp2025_l

L. 电子电路2(电路2)

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

配点 : 100 点

分发文件


問題文

JOI 您正在玩电子电路组。 电子电路组 N 的 您可以创建一个包含 和零件,N 的 您可以创建一个包含 或零件 和1 的 您可以创建一个包含 电路板 它由 组成。 电路板 2N+1 的 您可以创建一个包含 开关 按住 和 按字典顺序比较 N 的 您可以创建一个包含 零件槽 它由 组成, 可以通过在各元件槽中放置 AND 元件或 OR 元件来使用。 根据安装的组件和开关的状态,电路板将: 输出 0 或 至少 1 的值。

电路板规格

  • 该开关有 它们的编号最多为 0 减去 2N ,每个开关都有 ON 或 OFF 状态。每个开关如下所示 0 或 至少 1 的值。
  • 零件槽有 它们的编号最大为 0 减去 N-1 。每个组件插槽如下所示 0 或 至少 1 的值。
  • 每个交换机和每个组件槽位的输出按照以下规则按编号降序排列(对于相同编号的交换机和组件槽位,组件槽位在前)。 关于
    • j = 2N, 2N-1, \dots, N ,切换 j 输出以下内容。 当
      • 开关 按住 j 关闭时, 当0 。 你只需要砍掉
      • 开关 按住 j 为ON时, 对于1 。 你只需要砍掉
    • j = N-1, N-2, \dots, 0 ,零件槽 j 的输出 x 当开关 输出 j 输出以下内容。 当
      • 开关 按住 j 关闭时, 当x 。 你只需要砍掉
      • 开关 按住 j 为ON时, 对于1-x 输出
    • i = N-1, N-2, \dots, 0 ,零件槽 i 是 您也可以写 2 开关 它连接到 U_i, V_i 。在这里,U_i, V_i 是 您也可以写 i < U_i < V_i \leqq 2N 很满意。开关 U_i 的输出 x,开关 当 V_i 的输出 y 时,组件槽 当 AND 部件安装在 i 输出以下内容。 当
      • 零件槽 它由 i 中时, 当 OR 部件安装在\min(x, y) 。 你只需要砍掉
      • 零件槽 它由 i 中时, 关于\max(x, y) 。 你只需要砍掉
  • j = 1, 2, \dots, 2N ,U_i = j 或 至少 V_i = j 似乎是 i (0 \leqq i \leqq N - 1)只是 1 有两个。
  • 电路板的输出是开关 相当于 0 的输出。

例如, 当分解为N = 3, U_0 = 1, V_0 = 2, U_1 = 3, V_1 = 4, U_2 = 5, V_2 = 6 ,零件槽 当AND部件、AND部件和OR部件安装在 0, 1, 2 中时,电路板如下图所示。

现在,当JOI尝试在所有零件槽中安装AND零件时,一些已安装的零件 很明显, 最大 R 個 的 OR 部分被混淆了。 由于“与”和“或”元件无法在视觉上区分,因此必须使用电路板来区分“与”和“或”元件。 你的工作是按照以下格式提出 JOI 问题。 该过程重复 1\,000 次,以确定 OR 组件安装在哪个组件插槽中。

  • 你对你来说就是 JOI 指示 2N+1 开关的状态。 JOI按照指示改变开关的状态并告诉你电路板的输出。

给定电路板上的电路连接信息以及安装的OR组件数量的上限,1\,000 编写一个程序,使用以下问题识别 OR 组件安装在哪个组件插槽中。

入出力

这个问题是 互动问题(您创建的程序和评分程序通过标准输入和输出进行交互的问题)。

首先,电路板上的电路连接信息以及安装的 OR 元件数量上限由标准输入以以下格式给出。

N R 
U_0 V_0 
U_1 V_1 
\vdots 
U_{N-1} V_{N-1} 

您的程序收到此消息后,必须与评分程序进行交互。 要提出

要向 JOI 提问,请按照以下格式与评分程序交互。

  • 首先,按以下格式输出到标准输出。
    ? s
    
    • s 是 '0' 和 '1长度由 ' 组成 是一个字符串 2N + 1 , s 可以得到第 j + 1 文字目 (0 \leqq j \leqq 2N) 是 '0'然后切换 关闭 j 关闭 s 可以得到第 j + 1 第一个字符是 '1'然后切换 关闭 j 。
    • 文字列 s 的长度是 2N+1 ,不正解[1] 已确定。 调用
    • 文字列 s 到 '0“但是”1如果包含非 ' 的字符,不正解[2] 已确定。 调用
  • 接下来回答问题 x 由标准输入以以下格式给出。
    x
    
    在这里,x 是 您也可以写 0, 1, -1 ,分别代表以下内容。 如果
    • x 是 在 0 ,那么 JOI 是 按照 s 改变开关的状态,检查改变后电路板的输出是否为 0 。
    • x 是 在 1 ,那么 JOI 是 按照 s 改变开关的状态,检查改变后电路板的输出是否为 1 。
    • x 是 在 -1 表示评分程序判定你的程序不正确。在这种情况下,请立即终止您的程序。 当

问一个问题 执行此操作的次数不要超过 1\,000 次。 如果您询问超过1\,000 次,不正解[3] 已确定。 调用

要查明 OR 组件安装在哪个组件插槽中,请按以下格式将其输出到标准输出。

! t
  • t 是 '&' 和 '|长度由 ' 组成 是一个字符串 N , t 可以得到第 i + 1 文字目 (0 \leqq i \leqq N-1) 是 '&',组件槽 AND 部分安装在 i 中。 指示 OR 组件安装在 t 可以得到第 i + 1 第一个字符是 '|',组件槽 AND 部分安装在 i 。
  • 文字列 t 的长度是 N ,不正解[4] 已确定。 调用
  • 文字列 t 到 '&“但是”|如果包含非 ' 的字符,不正解[5] 已确定。 调用
  • 每个组件槽中实际安装的组件类型是一个字符串。 如果与 t 所代表的不同,不正解[6] 已确定。 调用
  • 答案就是 必须执行 1 次。 如果您回答的次数超过2 次,不正解[7] 被确定。答案将在程序结束时给出。 如果尚未执行 1 次,不正解[8] 已确定。 调用

当以上述以外的格式输出到标准输出时,不正解[9] 已确定。 调用

重要说明

  • 确保在每个输出结束时刷新标准输出。如果不flush,可能会判定已经超出了执行时间限制。
    • 提交C++程序时,cout << endl; 导致换行并自动刷新。如果 当使用 printf 时, 使用fflush(stdout) 。
    • 提交Python程序时,输入 只要你使用 input() ,就会自动冲掉。
  • 提问时 -1 ,请立即退出程序。如果未完成,则执行结果不确定。

评分注意事项

实际评分程序不是自适应的,而是从交互开始就有固定的答案。

测试工具

用于测试创建的程序的测试工具 testing_tool.py 包含在可以从竞赛网站下载的存档中。 并非必须使用该工具,并且允许对其进行修改。 请注意,实际评分程序与测试工具不同。

如果您的程序是用C++实现的,您可以按照以下步骤进行测试。

  • 首先,编译程序并生成可执行文件。 例如,如果您的程序 如果名称为 circuit.cpp ,则可以运行以下命令。 将生成一个名为 circuit 的可执行文件。
    g++ -std=gnu++20 -O2 -o circuit circuit.cpp
    
  • 接下来,执行以下命令。
    python3 testing_tool.py ./circuit
    

如果你的程序是用Python实现的,例如 如果名称为 circuit.py ,则运行以下命令。

python3 testing_tool.py pypy3 circuit.py

测试工具输入

T 是你的程序应该回答的长度 设其为字符串 N 。测试工具按以下格式从标准输入读取输入。

N R
U_0 V_0
U_1 V_1
\vdots
U_{N-1} V_{N-1}
T

测试工具输出

测试工具将以下信息输出到标准输出(引号实际上不输出)。

  • 如果正确,则函数 呼叫 query 的次数是 如果不是 Accepted: 22 。
  • 如果答案不正确,则错误答案的类型为 Wrong Answer [4] 。

如果要执行的程序满足多个错误答案条件,则显示的错误答案类型为 1 只有一个。


制約

  • 1 \leqq N \leqq 8\,000.
  • 1 \leqq R \leqq \min(N, 120).
  • i < U_i < V_i \leqq 2N (0 \leqq i \leqq N - 1).
  • j = 1, 2, \dots, 2N ,U_i = j 或 至少 V_i = j 似乎是 i (0 \leqq i \leqq N - 1)只是 1 有两个。

小課題

  1. (1 点) N = 1.
  2. (8 点) N \leqq 1\,000,R = 1.
  3. (10 点) N \leqq 1\,000.
  4. (21 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1),R \leqq 70.
  5. (9 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1).
  6. (25 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1),R \leqq 70.
  7. (9 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1).
  8. (14 点) R \leqq 70.
  9. (3 点)没有额外的限制。

交互示例

测试工具读取的输入示例和相应的交互如下所示。

入力例 1

1 1
1 2
|

1 对于第二个问题,电路板的输出可以计算如下。

  • 开关 按住 1, 2 的状态分别为 ON 和 OFF,因此开关 1, 2 分别是 它总是能被 1, 0 。 你只需要砍掉
  • 零件槽 它由 0 安装了 OR 部件,并连接了开关 输出 1, 2 分别是 它总是能被 1, 0 ,因此组件槽 0 是 您也可以写 \max(1, 0) = 1 。 你只需要砍掉
  • 开关 按住 0 的状态为OFF,组件槽为 0 的输出是 1 ,所以切换 0 的输出是 1 。
  • 因此,电路板的输出为 1 。

此输入示例满足所有子任务约束。


入力例 2

3 3
1 2
3 4
5 6
&&|

问题文本中的图表代表此输入示例的电路板。

此输入示例是一个小作业。 3, 6, 7, 8, 9 满足约束。

在可以从竞赛网站下载的文件中,sample-01-in.txt 是一个输入示例 对应于 1 , 对应于sample-02-in.txt 是一个输入示例 对应于 2 。 另外,sample-03-in.txt 是一个小作业 3, 4, 5, 8, 9 满足约束,sample-04-in.txt 是一个小作业 3, 6, 7, 8, 9 满足约束。