CF1368F Lamps on a Circle

这是一个交互题。 John 和他的想象朋友玩一个游戏。有 $n$ 盏灯按圆形排列。灯的编号为 $1$ 到 $n$，顺时针排列，也就是说，对于任意 $i = 1, \ldots, n-1$，灯 $i$ 和 $i+1$ 相邻，灯 $n$ 和 $1$ 也相邻。最开始所有灯都是关闭的。 John 和他的朋友轮流行动，John 先手。在他的回合，John 可以选择终止游戏，或者进行一次操作。每次操作，John 可以选择任意正整数 $k$，并将任意 $k$ 盏他选择的灯打开。作为回应，John 的朋友会选择 $k$ 盏连续的灯，并将它们全部关闭（如果这些灯本来就是关闭的，则保持关闭）。注意，这里的 $k$ 与 John 上一次操作的 $k$ 相同。例如，如果 $n=5$，John 刚刚打开了三盏灯，那么 John 的朋友可以选择关闭灯 $1,2,3$，或 $2,3,4$，或 $3,4,5$，或 $4,5,1$，或 $5,1,2$。 之后，John 可以选择终止游戏或继续操作，依此类推。但 John 不能进行超过 $10^4$ 次操作。 John 想要让游戏结束时点亮的灯数量尽可能多，而他的朋友则想让这个数量尽可能少。你的任务是为 John 提供一个策略，使他能获得最优结果。你的程序需要作为 John 与评测机（扮演 John 的朋友）进行交互。 假设游戏中有 $n$ 盏灯。令 $R(n)$ 表示如果双方都采取最优策略，游戏结束时点亮的灯的数量。你的程序必须在 $10^4$ 次操作内终止游戏，并且保证此时点亮的灯数不少于 $R(n)$。具体交互细节见下文。 出于技术原因，本题不支持 Hack。

无

首先，评测机会给出一个整数 $n$（$1 \leq n \leq 1000$），表示游戏中的灯数。然后评测机会等待你的操作。 每次操作，你需要输出一行，首先是一个整数 $k$（$1 \leq k \leq n$），然后是 $k$ 个不同的整数 $l_1, \ldots, l_k$（$1 \leq l_i \leq n$），表示你想要点亮的灯的编号。编号顺序可以任意。如果你尝试点亮已经点亮的灯，这不会有任何影响。 如果你的操作无效，或者你已经进行了超过 $10^4$ 次操作，评测机会回复一行，内容为 $-1$。否则，评测机会会回复一行，内容为一个整数 $x$（$1 \leq x \leq n$），表示他选择关闭从 $x$ 开始的 $k$ 盏连续灯（顺时针）。 之后你可以继续操作或选择终止游戏。 如果你想终止游戏，而不是进行操作，输出一行，内容为单个整数 $0$。如果此时点亮的灯数不少于 $R(n)$，则测试通过（注意 $R(n)$ 和判题结果不会反馈给你的程序）。该操作不计入操作次数（即你可以在正好 $10^4$ 次操作后终止游戏）。 收到 $-1$ 或输出 $0$ 后，你的程序应立即终止。 每次操作后不要忘记刷新输出。

当 $n=3$ 时，John 的任何操作都可以被完全抵消，因此 $R(3)=0$，直接终止游戏是最优策略。 当 $n=4$ 时，$R(4)=1$，一种实现该结果的策略见第二个样例。 样例交互中的空行仅为说明所用，实际输出时不应输出空行。 由 ChatGPT 4.1 翻译