QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#14330. Minus Operator

الإحصائيات

二进制值 $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))

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.