二进制值 $a$ 和 $b$ 的减法运算符定义为:若 $a = 1$ 且 $b = 0$,则 $(a - b) = 1$;否则 $(a - b) = 0$。 此外,表达式的语法定义如下。其中,$x$、括号和减号为终结符,$E$ 为起始符号。
$$E ::= x \mid (E - E)$$
评测程序拥有一个符合 $E$ 定义的表达式。该表达式对你隐藏。开始时,你仅获知表达式中终结符 $x$ 的数量,记为 $n$。
你的任务是通过有限次数的查询来猜出该表达式。
在单次查询中,你需指定一个长度为 $n$ 的二进制字符串 $S$。评测程序会将表达式中从左往右第 $i$ 个终结符 $x$ 临时替换为 $S_i$(其中 $i = 1, \dots, n$),并根据减法运算符的定义对替换后的表达式求值。随后,评测程序会向你返回求值结果,即 0 或 1。
交互
输入的第一行包含一个整数 $n$ ($3 \le n \le 200$)。读取该整数后,你的程序可以开始进行查询。对于每次查询,你的程序应输出一行格式为 “query $S$” 的内容。其中 $S$ 是一个长度为 $n$ 的二进制字符串,每个字符必须为 0 或 1。作为响应,你将从输入中读取到一个包含求值结果的行。
你的程序最多可以进行 500 次查询。如果你的程序查询次数超过 500 次,将被判为 “Wrong Answer”。
当你的程序确定了评测程序所拥有的表达式后,应输出一行格式为 “answer $T$” 的内容,其中 $T$ 为该表达式。输出后,交互结束,你的程序应终止。
在上述约束条件下,可以证明该表达式是可以唯一确定的。
说明
- 求值过程是非对抗性的,这意味着表达式是在查询开始前预先选定的,而不是根据你的查询实时生成的。
- 输出后请务必刷新缓冲区。详情请参阅 “Judging Details” 文档。
- 我们提供了一个用于本地测试的命令行工具,以及与样例交互对应的输入文件。你可以从 DOMjudge 下载这些文件。工具顶部有关于其用法的注释。
样例
样例输入 1
3 0
样例输出 1
query 111 answer ((x-x)-x)
说明 1
当 $n = 3$ 时,只有两种可能的表达式:$((x-x)-x)$ 或 $(x-(x-x))$。对于查询 $s = 111$,这些表达式的求值结果分别为: $((1 - 1) - 1) = (0 - 1) = 0$,以及 $(1 - (1 - 1)) = (1 - 0) = 1$。
在此样例中,评测程序返回 0,表明第一个表达式是正确的。
样例输入 2
4 0 1
样例输出 2
query 0000 query 1001 answer ((x-x)-(x-x))