AT_agc072_d [AGC072D] Magician

[problemUrl]: https://atcoder.jp/contests/agc072/tasks/agc072_d **这是一个交互式问题。** 桌面上有 $\binom{2N}{N}$ 张卡片，编号为 $1$ 到 $\binom{2N}{N}$。第 $i$ 张卡片的正面印有由 $N$ 个 `0` 和 $N$ 个 `1` 组成的、按字典序第 $i$ 小的长度为 $2N$ 的字符串，共有 $\binom{2N}{N}$ 种不同的字符串。 具体例子：例如当 $N=2$ 时，卡片 $1, 2, 3, 4, 5, 6$ 的正面分别印有 `0011`、`0101`、`0110`、`1001`、`1010`、`1100`。 魔女 Alice 会在每张卡片的背面写上前 $N$ 个大写英文字母中的某一个（例如 $N=2$ 时为 `A`、`B`），然后进行如下的 **魔法** 操作共 $T$ 次。 > **一次魔法的流程** > > 1. 主持人宣布前 $N$ 个大写英文字母中的某一个字母 $s$。 > 2. 主持人在黑板上写下一个全为 `0` 的长度为 $2N$ 的字符串。 > 3. 依次进行 $i=1,2,\dots,N$ 的如下操作。这里 $a_1, b_1, \dots, a_N, b_N$ 是 $1$ 到 $2N$ 之间互不相同的整数。 > - 首先，主持人将整数 $a_i$ 和 $b_i$ 告诉 Alice。 > - 然后，Alice 需要将黑板字符串的第 $a_i$ 或第 $b_i$ 个字符中的一个改为 `1`（只能改一个）。 > 4. 此时黑板上的字符串为 $x$。正面印有 $x$ 的卡片恰好有一张，查看其背面。如果背面的字母是 $s$，则本次魔法成功，否则失败。 注意，Alice 在决定将 $a_i$ 或 $b_i$ 位置改为 `1` 之前，并不知道后续 $a_{i+1}, b_{i+1}$ 的信息。 请实现一种策略，使得 $T$ 次魔法全部成功。现在，开始吧。

首先，从标准输入读取两个整数 $N, T$，格式如下： > $N$ $T$ 接下来，输出每张卡片背面要写的字母 $c_i$，格式如下，末尾需换行。这里 $c_i$ 必须是前 $N$ 个大写英文字母之一。 > $c_1\ c_2\ \cdots\ c_{{}_{2N}\mathrm{C}_N}$ 然后，以下过程重复 $T$ 次。第 $t$ 次（$1 \leq t \leq T$）对应第 $t$ 次魔法。 > 首先，从标准输入读取主持人宣布的字母 $s$，格式如下： > > > $s$ > > 接着，依次进行 $i=1,2,\dots,N$ 的如下操作。 > > - 首先，输入两个整数 $a_i, b_i$，格式如下： > > > $a_i$ $b_i$ > > - 然后，输出要改为 `1` 的位置 $d$，格式如下。$d$ 必须为 $a_i$ 或 $b_i$ 之一，末尾需换行。 > > > $d$ > > 如果输出格式有误，或上一次魔法失败，之后不会再输入 $s$ 或 $(a_i, b_i)$，而是输入 $-1$。此时应立即终止程序。（如果是在第 $T$ 次魔法首次失败，或第 $T$ 次魔法的 $i=N$ 时首次输出格式有误，则之后不会再有任何输入）

见上文输入格式说明。

### 限制条件 - $2 \leq N \leq 10$ - $1 \leq T \leq 5\,000$ - $s$ 是前 $N$ 个大写英文字母之一 - $1 \leq a_i < b_i \leq 2N$ - $a_1, b_1, a_2, b_2, \dots, a_N, b_N$ 互不相同 - $a_1, b_1, a_2, b_2, \dots, a_N, b_N, s$ 在与评测机交互前已确定 - $N, T, a_i, b_i$ 均为整数 ### 注意事项 **每次输出后都要刷新输出流。** 否则可能会因未及时输出而被判定为 TLE。 此外，如果从输入读到 `-1`，应立即终止程序。此时评测结果为 WA，但如果不终止，评测结果将不可预期。请注意，额外的换行也可能被视为输出格式错误。 本题的评测系统是**非自适应的（non-adaptive）**。即 $a_1, b_1, a_2, b_2, \dots, a_N, b_N, s$ 的值在与评测机交互前已确定，不会因你的输出而改变。 ### 输入输出样例 以下示例仅为交互过程的一个例子。 |输入|输出|说明| |:-:|:-:|:-:| | `2 2` | | 首先输入整数 $N$ 和 $T$。 | | | `ABABAB` | 输出 $6$ 张卡片背面的字母。 | | `A` | | 第 $1$ 次魔法开始。主持人宣布字母 `A`。 | | `1 2` | | $(a_1, b_1) = (1, 2)$。 | | | `2` | 将第 $2$ 位改为 `1`。 | | `3 4` | | $(a_2, b_2) = (3, 4)$。 | | | `3` | 将第 $3$ 位改为 `1`。最终黑板字符串为 `0110`，正面为 `0110` 的卡片背面是 `A`，魔法成功。 | | `B` | | 第 $2$ 次魔法开始。主持人宣布字母 `B`。 | | `1 3` | | $(a_1, b_1) = (1, 3)$。 | | | `1` | 将第 $1$ 位改为 `1`。 | | `2 4` | | $(a_2, b_2) = (2, 4)$。 | | | `2` | 将第 $2$ 位改为 `1`。最终黑板字符串为 `1100`，正面为 `1100` 的卡片背面是 `B`，魔法成功。 | 由 ChatGPT 4.1 翻译