← 返回题目列表

AtCoder · agc072_d

D. 魔术师

中文机器翻译题面 查看原题

分数: 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 次。

单一魔法

  1. 主持人公布一封信 s 位列第一 N 大写字母。
  2. 主机写入一个长度-2N 全部字符串 黑板上的 0 。
  3. 对于 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.
  4. 让 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 ,所以魔法成功了。