AT_abc337_e [ABC337E] Bad Juice

题目描述

本题为交互式问题（你的程序将与评测程序通过标准输入输出进行交互）。

有 $N$ 瓶编号为 $1$ 到 $N$ 的果汁。其中恰好有 $1$ 瓶已经变质。如果喝了哪怕一小口变质的果汁，第二天就会肚子不舒服。

高桥君必须在第二天之前确定哪一瓶果汁变质了。为此，他需要召集最少数量的朋友，并让每个朋友品尝部分果汁。每个朋友可以喝任意多瓶果汁，每瓶果汁也可以被任意多位朋友品尝。

你需要输出召集的朋友数量以及每位朋友要喝的果汁编号。第二天，你会收到每位朋友是否肚子不舒服的信息，然后输出变质果汁的编号。

输入格式

本题为交互式问题（你的程序将与评测程序通过标准输入输出进行交互）。

在交互开始前，评测程序会秘密选择一个 $1$ 到 $N$ 之间的整数 $X$，表示变质果汁的编号。$X$ 的值不会告诉你。此外，在交互过程中，只要不与限制条件和你之前的输出矛盾，$X$ 的值可能会发生变化。

首先，评测程序会输入 $N$。

$N$

你需要输出召集的朋友数量 $M$ 并换行。

$M$

接下来，你需要进行 $M$ 次输出。对于第 $i$ 次输出，表示第 $i$ 位朋友要喝的果汁数量 $K_i$ 以及这些果汁的编号（按升序排列），用空格分隔并换行。

$K_i$ $A_{i,1}$ $A_{i,2}$ $\ldots$ $A_{i,K_i}$

随后，评测程序会输入一个长度为 $M$ 只包含 0 和 1 的字符串 $S$。

$S$

对于 $i=1,2,\ldots,M$，如果 $S$ 的第 $i$ 个字符为 1，则第 $i$ 位朋友第二天肚子不舒服，否则没有不适。

你需要输出变质果汁的编号 $X'$ 并换行。

$X'$

之后，立即结束程序。

如果你输出的 $M$ 是确定变质果汁所需的最小朋友数，并且你输出的 $X'$ 与实际变质果汁编号 $X$ 一致，则判定为正确。

输出格式

（见上文输入格式说明）

说明/提示

限制

• $N$ 为整数
• $2 \leq N \leq 100$

注意事项

• 每次输出后请在末尾加换行并刷新标准输出，否则可能会因超时（TLE）被判错。
• 如果在交互过程中输出不合法，或程序中途退出，评测结果不确定。 特别是如果程序运行时发生运行时错误，评测结果可能不是 RE，而是 WA 或 TLE。
• 输出 $X'$ 后请立即结束程序，否则评测结果不确定。
• 本题评测为自适应评测。即，只要不与限制条件和你之前的输出矛盾，$X$ 的值可能会发生变化。

输入输出样例

以下为 $N=3$ 时的输入输出示例。

输入 输出 说明
3
// 评测程序输入果汁数量 $N$
2
// 你输出召集的朋友数 $M$
2 1 2
// 第 1 位朋友喝果汁 1 和 2
1 2
// 第 2 位朋友喝果汁 2
10
// 评测程序输入每位朋友是否肚子不舒服的字符串 $S$
1
// 你输出变质果汁的编号

由 ChatGPT 4.1 翻译