分数: 550 点
问题陈述
这是一个 交互式任务 (您的程序和法官通过标准输入和输出进行交互)。
给你一个整数 N 和 奇数 K.
法官有隐藏长度-N 序列 A = (A_1, A_2, \dots, A_N) 组成 0 和 1.
虽然您无法直接访问序列的元素 A, 您最多可以向法官提出以下问题 N 次。
- 选择不同的整数 x_1, x_2, \dots,和 x_K 之间 1 和 N,包含在内,询问奇偶校验 A_{x_1} + A_{x_2} + \dots + A_{x_K}.
确定 (A_1, A_2, \dots, A_N) 至多 N 查询,并打印答案。
在这里, 判断是自适应的。 换句话说,法官可以修改 A 只要与过去查询的响应一致即可。
因此,如果输出满足以下条件,则认为您的程序是正确的,否则是错误的:
- 您的程序打印一个与迄今为止对查询的响应一致的序列,并且这是唯一的这样的序列。
约束
- 1 \leq K \lt N \leq 1000
- K 是奇数。
- A_i is 0 or 1.
输入和输出
这是一个 交互式任务 (您的程序和法官通过标准输入和输出进行交互)。
首先,接收 来自标准输入的 N 和 K 。
N K
然后,重复询问,直到可以唯一确定 (A_1, A_2, \dots, A_N).
每个查询应按以下格式打印到标准输出,其中 x_1, x_2, \dots,和 x_K 是 K 之间的不同整数 1 和 N,包括在内。
? x_1 x_2 \dots x_K
对查询的响应由标准输入以以下格式给出。
T
在这里, T 表示对查询的响应。
- T is
0当 A_{x_1} + A_{x_2} + \dots + A_{x_K} 是偶数,并且 - T is
1当 A_{x_1} + A_{x_2} + \dots + A_{x_K} 是奇数。
但是,如果 x_1, x_2, \dots 和 x_K 不满足约束,或者查询次数超过 N,那么 T is -1.
如果法官返回 -1,您的程序已被认为不正确,因此请立即终止该程序。
当你可以确定的所有元素 A,按以下格式打印这些元素,并立即终止程序。
! A_1 A_2 \dots A_N
注释
- 在每条消息的末尾打印换行符并刷新标准输出。否则,您可能会得到一个 TLE 判决。
- 如果交互过程中出现格式错误的输出或程序过早退出,则判决将是不确定的。
- 打印答案后立即终止程序,否则结论将不确定。
- 这个问题的判断是自适应的。这意味着法官可以修改 A 只要与过去查询的响应一致即可。
示例交互
在以下交互中, N=5 和 K=3. 请注意,以下输出本身将导致 WA.
在这里, A = (1, 0, 1, 1, 0) 确实与回复一致,但也是如此 (0, 0, 1, 0, 0),所以序列 A 不是唯一确定的。因此,该程序被认为是不正确的。
| 输入 | 输出 | 说明 |
|---|---|---|
5 3 | 首先,给你整数 N 和 K. | |
? 2 4 1 | 您提出查询 (x_1, x_2, x_3) = (2, 4, 1). | |
0 | 对查询的响应是 0,因此判断返回该值。 | |
? 5 3 2 | 您提出查询 (x_1, x_2, x_3) = (5, 3, 2). | |
1 | 对查询的响应是 1,因此判断返回该值。 | |
! 1 0 1 1 0 | 您打印 (1, 0, 1, 1, 0) 猜测 A。 由于序列 A 不是唯一确定的,判决将是 WA. |