分数: 1400 点
问题陈述
这是一个交互问题。
有 \tbinom{2N}{N} 卡片编号 1 to \tbinom{2N}{N} 在桌子上。卡 i (1 \le i \le \tbinom{2N}{N}) 在其正面显示 i-组成的字符串中按字典顺序排列的第一个字符串 N 零和 N 的。
示例
对于 N = 2,卡片正面 1, 2, 3, 4, 5, 6 是0011, 0101, 0110, 1001, 1010, 1100。
女巫爱丽丝写下了第一个 N 大写字母(例如, A or B if N = 2)在每张卡的背面,然后执行以下操作 魔法 T 次。
单一魔法
- 主持人公布一封信 s 位列第一 N 大写字母。
- 主机写入一个长度-2N 全部字符串 黑板上的
0。- 对于 i = 1, 2, \dots, N 按照此顺序,执行以下操作。在这里, a_1, b_1, \dots, a_N, b_N 是不同的整数 1 to 2N.
- 首先,主机告诉Alice整数 a_i 和 b_i.
- 然后,Alice 恰好选择了其中之一 a_i-th 和 b_i黑板上字符串的第个字符,并将其设置为
1.- 让 x 是黑板上的最后一个字符串。仅显示一张卡片 x 在其正面;看看它的背影。当且仅当其背面的字母等于 s.
请注意,爱丽丝 学习 a_{i+1} 和 b_{i+1} 仅在选择其中一个之后 a_i-th 和 b_i要设置为的第个字符 1.
实施一项战略,让所有人 T 魔法成功了。现在,让我们开始吧。
约束
- 2 \le N \le 10
- 1 \le T \le 5\,000
- 这封信 s 是第一批 N 大写字母。
- 1 \le a_i < b_i \le 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 是整数。
输入和输出
首先,读取整数 N 和 T 从标准输入以以下格式给出:
N T
接下来,让 c_i 是写在卡片背面的字母 i,并按以下格式打印这些字母,后跟换行符。在这里, c_i 必须位于第一个 N 大写字母。
c_1 c_2 \cdots c_{\tbinom{2N}{N}}
接下来,重复以下过程 T 次。的 t第次迭代 (1 \leq t \leq T) 对应于 t-th 魔法。
阅读已公布的信件 s 按以下格式给出:
s那么,对于 i = 1, 2, \dots, N 按照此顺序,执行以下操作。
- 读取整数 a_i 和 b_i 按以下格式给出:
a_i b_i
- 打印所选位置 d 采用以下格式,后跟换行符。在这里, d 必须是 a_i or b_i.
d如果你的输出格式错误或之前的魔法失败,则不再有输入,例如 给出了 s or (a_i, b_i) ,但是
-1由标准输入给出。 在这种情况下,请立即退出。 (如果您在第一次失败 T-th 魔法,或者你的输出第一次出现格式错误 i = N 在 T-th 魔法,接下来不再输入。)
注释
每次输出后冲洗。 否则,您可能会收到 TLE 判决。
如果您阅读 -1,立即退出。如果您这样做,您将收到 WA 判决,但继续下去会导致不确定的判决。不必要的换行符可能会被视为格式错误。
法官是 非自适应;价值观 a_1, b_1, a_2, b_2, \dots, a_N, b_N, s 在交互开始之前已修复,并且不会受到您的输出的影响。
示例交互
请注意,这只是交互的示例。
| 输入 | 输出 | 评论 |
|---|---|---|
2 2 | 整数 N 和 T 由标准输入给出。 | |
ABABAB | 在六张卡片的背面打印字母。 | |
A | 第一个魔法开始了。 主持人声明 A. | |
1 2 | 主持人告诉你 (a_1, b_1) = (1, 2). | |
2 | 将第二个字符设置为 1. | |
3 4 | 主持人告诉你 (a_2, b_2) = (3, 4). | |
3 | 将第三个字符设置为 1.最终字符串是 0110,并且该卡带有 0110 其正面有
背面有 A ,所以魔法成功了。 | |
B | 第二个魔法开始了。 主持人声明 B. | |
1 3 | 主持人告诉你 (a_1, b_1) = (1, 3). | |
1 | 将第一个字符设置为 1. | |
2 4 | 主持人告诉你 (a_2, b_2) = (2, 4). | |
2 | 将第二个字符设置为 1.最终字符串是 1100,并且该卡带有 1100 其正面有
背面有 B ,所以魔法成功了。 |