103133: [Atcoder]ABC313 D - Odd or Even
Description
Score : $550$ points
Problem Statement
This is an interactive task (where your program and the judge interact via Standard Input and Output).
You are given an integer $N$ and an odd number $K$.
The judge has a hidden length-$N$ sequence $A = (A_1, A_2, \dots, A_N)$ consisting of $0$ and $1$.
While you cannot directly access the elements of sequence $A$, you are allowed to ask the judge the following query at most $N$ times.
- Choose distinct integers $x_1, x_2, \dots$, and $x_K$ between $1$ and $N$, inclusive, to ask the parity of $A_{x_1} + A_{x_2} + \dots + A_{x_K}$.
Determine $(A_1, A_2, \dots, A_N)$ by at most $N$ queries, and print the answer.
Here, the judge is adaptive. In other words, the judge may modify the contents of $A$ as long as it is consistent with the responses to the past queries.
Therefore, your program is considered correct if the output satisfies the following condition, and incorrect otherwise:
- your program prints a sequence consistent with the responses to the queries so far, and that is the only such sequence.
Constraints
- $1 \leq K \lt N \leq 1000$
- $K$ is odd.
- $A_i$ is $0$ or $1$.
Input and Output
This is an interactive task (where your program and the judge interact via Standard Input and Output).
First of all, receive $N$ and $K$ from Standard Input.
$N$ $K$
Then, repeat asking queries until you can uniquely determine $(A_1, A_2, \dots, A_N)$.
Each query should be printed to Standard Output in the following format, where $x_1, x_2, \dots$, and $x_K$ are $K$ distinct integers between $1$ and $N$, inclusive.
$?$ $x_1$ $x_2$ $\dots$ $x_K$
The response to the query is given from Standard Input in the following format.
$T$
Here, $T$ denotes the response to the query.
-
$T$ is
0
when $A_{x_1} + A_{x_2} + \dots + A_{x_K}$ is even, and -
$T$ is
1
when $A_{x_1} + A_{x_2} + \dots + A_{x_K}$ is odd.
However, if $x_1, x_2, \dots$ and $x_K$ do not satisfy the constraints, or the number of queries exceeds $N$, then $T$ is -1
.
If the judge returns -1
, your program is already considered incorrect, so terminate the program immediately.
When you can determine all the elements of $A$, print those elements in the following format, and terminate the program immediately.
$!$ $A_1$ $A_2$ $\dots$ $A_N$
Notes
- Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE
Output
问题描述
这是一个交互式任务(即您的程序和裁判通过标准输入和输出进行交互)。
给定一个整数$N$和一个奇数$K$。
裁判有一个隐藏的长度为$N$的序列$A = (A_1, A_2, \dots, A_N)$,其中包含$0$和$1$。
虽然您不能直接访问序列$A$的元素, 但是您最多允许向裁判提出以下查询$N$次。
- 选择$1$到$N$之间的不同整数$x_1, x_2, \dots$和$x_K$,询问$A_{x_1} + A_{x_2} + \dots + A_{x_K}$的奇偶性。
通过最多$N$次查询确定$(A_1, A_2, \dots, A_N)$,并打印答案。
此处,裁判是自适应的。换句话说,只要与过去查询的响应一致,裁判就可以修改$A$的内容。
因此,如果输出满足以下条件,则认为您的程序是正确的,否则不正确:
- 您的程序打印出与到目前为止查询的响应一致的序列,并且这是唯一这样的序列。
约束条件
- $1 \leq K \lt N \leq 1000$
- $K$是奇数。
- $A_i$是$0$或$1$。
输入和输出
这是一个交互式任务(即您的程序和裁判通过标准输入和输出进行交互)。
首先,从标准输入接收$N$和$K$。
$N$ $K$
然后,重复提出查询,直到您能唯一确定$(A_1, A_2, \dots, A_N)$。
每次查询应以以下格式打印到标准输出,其中$x_1, x_2, \dots$和$x_K$是$1$到$N$之间不同的整数,包括$1$和$N$。
$?$ $x_1$ $x_2$ $\dots$ $x_K$
查询的响应从标准输入给出以下格式。
$T$
此处,$T$表示查询的响应。
- 当$A_{x_1} + A_{x_2} + \dots + A_{x_K}$为偶数时,$T$为
0
, - 当$A_{x_1} + A_{x_2} + \dots + A_{x_K}$为奇数时,$T$为
1
。
但是,如果$x_1, x_2, \dots$和$x_K$不满足约束条件,或者查询次数超过$N$,则$T$为-1
。
如果裁判返回-1
,则您的程序已被视为不正确,因此立