← 返回题目列表

AtCoder · abc313_d

G. 奇数或偶数

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

分数: 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.