← 返回题目列表

AtCoder · joig2026final_f

F. 动物园

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

配点 : 100 点

分发文件

問題文

你在动物园 N 我养海狸。到海狸 0 它们的编号最大为 N-1 。

这个动物园里的海狸吃苹果。每只海狸都偏爱苹果; i (0 \leqq i \leqq N-1) 是 重量 L_i 克以上 R_i 喜欢重量小于一克的苹果。但是,您可以 我不知道 L_i 和 R_i 的具体值。

你现在是 N 在海狸之中 K 我正在考虑选一件放在展览区。但是,如果满足以下条件: 海狸 i 和海狸 j (0 \leqq i < j \leqq N-1)同时进入展区,这 2 动物们开始打斗。

  • 海狸 有一个苹果,其重量 i 和海狸 j 都喜欢。换句话说,L_i \leqq x \leqq R_i 和 所有满足 L_j \leqq x \leqq R_j 满足的实数 x 存在。

您可能已经从以前的经验中学到了类似的东西。 因此 (i, j) 对不存在 K 我记得我可以在海狸之间进行选择, 我忘记了如何选择最重要的海狸。

您可以通过下面的表格提出问题 此操作最多可以执行 1\,000 次。

  • 0 以上 N 的整数 m 并且,0 以上 N-1 以下各不相同 指定 m 整数 t_0, t_1, \ldots, t_{m-1} 。 m 海狸 t_0, t_1, \ldots, t_{m-1} 在选择展示区放置的河狸时,必须选择展示区放置的河狸的最大数量,以避免打架。 询问是否可以进入。

通过提问,您可以具体识别 Beaver。 K 我想想办法选一个放在展区。此外,我想尽量减少提出问题的数量。

海狸数量 N 以及展区内可放置的海狸数量 鉴于 K ,1\,000 问题如下: 海狸 K 编写一个程序,找到一种方法来选择一种动物并将其放入展示区。

入出力

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

一、河狸数量 N 以及展区内可放置的海狸数量 鉴于 K 由标准输入以以下格式给出。

N K

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

1 问题,请按以下格式与评分程序交互。

  • 首先,按以下格式输出到标准输出。
    ? m t_0 t_1 \ldots t_{m-1}
    
    • m 表示 0 以上 N 是以下整数。如果不满足这一点,不正解[1] 被确定。
    • 其次是 m 整数 t_0, t_1, \ldots, t_{m-1} 表示 0 以上 N-1 以下整数彼此不同。 如果不满足这一点,不正解[2] 被确定。
  • 然后是一个代表问题答案的整数。 它是小于或等于 r 由标准输入以以下格式给出。
    r
    
    这里 r 表示 -1 以上 N 的整数。 r = -1 表示评分程序判定您的程序不正确。 在这种情况下,请立即终止您的程序。 当 0 \leqq r \leqq N 时,m 海狸 t_0, t_1, \ldots, t_{m-1} 仅选择海狸放入展区时 至多 r 表示海狸可以放置在展示区而不需战斗。 请注意,它也可能是r > K 。

问题是 请勿超过 1\,000 次。 如果执行次数超过1\,000 次,不正解[3] 被确定。

海狸 K 要回答一种选择动物并将其放入展览区的方法,请按以下格式将其输出到标准输出。

! s_0 s_1 \ldots s_{K-1}
  • K 整数 s_0, s_1, \ldots, s_{K-1} 是 代表将K 海狸 s_0, s_1, \ldots, s_{K-1} 放入展示区。
  • s_0, s_1, \ldots, s_{K-1} 表示 0 以上 N - 1 必须是以下不同的整数。 如果不满足这一点, 如果将不正解[4] 被确定。
  • 海狸 有一个苹果,其重量 s_0, s_1, \ldots, s_{K-1} 放入展示区时发生打斗,不正解[5] 被确定。
  • 答案正是 必须执行 1 次。 如果您回答的次数超过2 次,不正解[6] 已确定。 程序末尾的答案是 如果尚未执行 1 次,不正解[7] 被确定。

如果以上述任何格式以外的格式输出到标准输出,不正解[8] 被确定。

重要说明

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

评分注意事项

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

测试工具

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

要测试您用 C++ 编写的程序,请按照以下步骤操作。

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

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

python3 testing_tool.py python3 zoo.py

测试工具输入

测试工具按以下格式从标准输入读取输入。

N K 
L_0 R_0 
L_1 R_1 
\vdots 
L_{N-1} R_{N-1}

测试工具输出

如果程序执行正常结束,则测试工具将以下信息输出到标准输出(引号实际上不输出)。

  • 如果答案正确,则提出的问题数为“ 输出Accepted: 22“。
  • 如果答案不正确,则错误答案的类型为“ 输出Wrong Answer [2]“。

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


制約

所有输入数据满足以下条件。

  • 1 \leqq N \leqq 1\,000.
  • 1 \leqq K \leqq \min(10, N).
  • 1 \leqq L_i \leqq R_i \leqq 10\,000 (0 \leqq i \leqq N-1).
  • 避免打架 K 选择海狸的方法不止一种。
  • 所有输入值都是整数。

小課題

  1. (6 点) N \leqq 8.
  2. (7 点) N \leqq 12.
  3. (14 点) N \leqq 20.
  4. (21 点) N \leqq 50.
  5. (16 点) N \leqq 90.
  6. (36 点)没有额外的限制。对于此子任务,将根据以下方式确定分数: 对于
    • 小課題 6 对应的测试用例,1 如果有任何错误答案,则该子任务的分数将为 0 成为重点。
    • 否则,计算此子任务的所有测试用例中提出的最大问题数。 T 。 此时,子任务的分数确定如下。
      • 100 < T \leqq 1\,000 的情况,13 点.
      • T \leqq 100 的情况,36 点.

小課題 1,2,3,4,5 的分数不取决于提出的问题数量 (1\,000 次或更少),但是 如果超过100 次, 在竞赛网站上,有时会写为“输出部分正确。”

交互示例

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

入力例 1

4 2
2 6
3 6
4 10
8 11

1 对于第二个问题,海狸 0 和海狸 2 当从一只海狸中选择放入展示区时,询问展示区最多可以放入多少只海狸。 海狸 如果您选择 0 如果你选择 1 展览区内最多可以拥有 1 只海狸,这是最多的数量。因此,1 由标准输入给出。

2 对于第二个问题,海狸 1 当从一只海狸中选择放入展示区时,询问展示区最多可以放入多少只海狸。 海狸 如果您选择 1 如果你选择 1 展览区内最多可以拥有 1 只海狸,这是最多的数量。因此,1 由标准输入给出。

3 对于第二个问题,海狸 1 和海狸 2 和海狸 3 当从一只海狸中选择放入展示区时,询问展示区最多可以放入多少只海狸。 海狸 如果您选择 1 和海狸 3 如果你选择 2 展览区内最多可以拥有 1 只海狸,这是最多的数量。因此,2 由标准输入给出。

最后,海狸 将 1 和海狸 3 放入展区 2 就是答案。

请注意,本次交流只是一个示例,并不一定意味着您已获得从这些问题中获得正确答案所需的信息。

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