分数: 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. 因此,法官可能会判定该答案不正确。 |