← 返回题目列表

AtCoder · arc184_a

A. 鉴定师

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

分数: 600 点

问题陈述

这个问题是 互动,以及 判断是否自适应。详细信息请参阅注释。
另外,问题陈述中的参数固定为 N=1000, M=10, Q=950.

有 N 硬币编号 1, 2, \dots, N.
正是 M 这些硬币是假币。

鉴定师可以在一次鉴定中确定两枚钱币是同一类型还是不同类型。具体来说:

  • 如果两枚钱币都是真品或者都是假币,则判定为同种。
  • 否则判断为不同类型。

识别最多使用的所有假币 Q 评估。

约束

  • \color{red}{N = 1000}
  • \color{red}{M = 10}
  • \color{red}{Q = 950}

互动

这是一个交互问题。
最初,接收 来自标准输入的 N, M,和 Q :

N M Q


接下来,您可以在 0 和 Q 次(含),如下。

首先,通过按以下格式输出到标准输出,表明您正在评估硬币 x 和 y。 (在末尾添加换行符。)

? x y

在这里, x 和 y 之间必须是不同的整数 1 和 N,包括在内。

作为回应,审判系统将回复以下三种响应之一。

0

如果响应是 0,表示硬币 x 和 y 属于同一类型。

1

如果响应是 1,表示硬币 x 和 y 属于不同类型。

-1

如果响应是 -1,表示该鉴定无效。具体来说,当至少满足以下条件之一时,会给出此响应:

  • 输出 x 和 y 不满足约束。
  • 评价数量超过 Q.

如果您收到此回复,则您的程序被视为不正确。立即终止您的程序。


最后,通过按以下格式输出到标准输出,您可以回答硬币 A_1, A_2, \dots, A_{M} 是假冒的。 (在末尾添加换行符。)

! A_1 A_2 \dots A_{M}

在这里, A_i 之间必须是不同的整数 1 和 N,包括在内。
在此输出之后,立即终止程序。

如果您的任何输出不符合指定的格式,您的程序将被视为不正确。 法官随后将作出回应 -1,因此在这种情况下,请立即终止您的程序。

注释

  • 每次输出时,请在末尾添加换行符并刷新标准输出。 如果不这样做可能会导致以下判决: TLE or WA.
  • 输出你的答案后(或收到 -1),立即终止您的程序。否则,判决是不确定的。
  • 请注意,不必要的换行符被视为格式错误。
  • 这个问题的判断是自适应的。 也就是说,在任何时候,只要能够保持一致性,法官就可以更改哪些硬币是假币。有关详细信息,请参阅示例交互。

示例交互

在这次互动中, N=5, M=2, Q=10,法官最初考虑硬币 1 和 2 为假冒产品。

注意,这个例子不满足约束条件,不包含在判断中。 给出了

输入  输出 说明
5 2 10 N, M,和 Q 。
? 1 2 您评估硬币 1 和 2.
0 硬币 1 和 2 被判断为同一类型。
? 1 3 您评估硬币 1 和 3.
1 硬币 1 和 3 被判断为不同类型。
? 1 4 您评估硬币 1 和 4.
1 硬币 1 和 4 被判断为不同类型。
! 1 2 你回答说硬币 1 和 2 是假冒的。
确实,硬币 1 和 2 被认为是假货,但也可以考虑硬币 3 和 4 为假冒产品,同时保持一致性。
因此,法官可能会将假币改为 3 和 4.
因此,法官可能会判定该答案不正确。