P13589 [NWRRC 2023] Intersegment Activation

这是一个交互题。 有一个包含 $n$ 个格子的数组，编号从 $1$ 到 $n$。对于每一对整数 $(i, j)$，其中 $1 \le i \le j \le n$，都有一个覆盖从 $i$ 到 $j$（包括 $i$ 和 $j$）的屏障。每个屏障要么是激活的，要么是未激活的。如果没有任何激活的屏障覆盖某个格子，则该格子是可见的；否则，该格子是不可见的。 你并不知道每个屏障的状态。你唯一能观察到的是当前可见格子的数量。但你可以翻转任意一个屏障的状态：如果它是激活的，则变为未激活，反之亦然。你的任务是让所有屏障都变为未激活状态，使得所有格子都可见。 ### 交互协议 首先，读取一个整数 $n$，表示格子的数量（$1 \le n \le 10$）。 接下来的交互将分为若干轮进行。你的程序每一轮应先读取一个整数 $k$，表示当前可见格子的数量（$0 \le k \le n$）。 - 如果 $k = n$，则任务完成，你的程序应当退出。 - 如果 $k < n$，你可以翻转任意一个屏障的状态。在单独一行输出两个整数 $i$ 和 $j$，表示翻转 $(i, j)$ 这个屏障的状态（$1 \le i \le j \le n$）。在你的操作之后，进入下一轮，你需要读取新的 $k$ 值。 你的解法必须在不超过 $2500$ 次翻转内使所有格子可见。初始时，并非所有格子都是可见的（第一轮 $k < n$）。 交互器是非自适应的：每个测试中，所有屏障的状态在程序执行前就已确定。

见交互协议。

见交互协议。

初始状态。  在示例中，最初只有 $(1, 2)$ 和 $(2, 3)$ 两个屏障是激活的。这两个屏障覆盖了所有三个格子，因此第一轮 $k = 0$。 - 翻转 $(2, 2)$ 屏障后，现在有三个激活的屏障，依然 $k = 0$ 个可见格子。 - 翻转 $(1, 2)$ 屏障后，第 $1$ 个格子变为可见，因此现在 $k = 1$ 个可见格子。 - 翻转 $(2, 3)$ 屏障后，第 $3$ 个格子也变为可见。现在唯一不可见的格子是 $2$，它被唯一激活的屏障 $(2, 2)$ 覆盖，此时 $k = 2$ 个可见格子。 - 翻转 $(2, 2)$ 屏障后，所有屏障都未激活，所有格子都可见。读取到 $k = 3$ 后，程序终止。 由 ChatGPT 4.1 翻译