QOJ.ac

QOJ

Límite de tiempo: 5 s Límite de memoria: 1024 MB Puntuación total: 34 Interactivo

#11453. Dat Bae

Estadísticas

一个研究财团为他们的新数据中心建立了一个新的数据库系统。该数据库由一台主计算机和 $N$ 台工作计算机组成,工作计算机的 ID 从 $0$ 到 $N-1$。每台工作计算机恰好存储一位信息……这看起来相当浪费,但这些数据非常重要!

你受雇评估该数据库的以下指令:

TEST_STORE <bits>:主计算机读入 <bits>(一个长度为 $N$ 的位串),并将第 $i$ 位发送给第 $i$ 台工作计算机进行存储。随后,主计算机将从工作计算机中读回这些位,并按读入时的顺序返回给用户。

在正常运行情况下,TEST_STORE 应该返回与读入相同的位串,但不幸的是,有 $B$ 台工作计算机损坏了!

损坏的工作计算机能够正确存储分配给它们的位,但每当主计算机尝试从损坏的工作计算机读取数据时,都不会返回任何位。这导致 TEST_STORE 操作仅返回 $N-B$ 位,即存储在未损坏工作计算机上的位(按其 ID 的升序排列)。例如,假设 $N=5$,第 $0$ 台和第 $3$ 台工作计算机损坏(即 $B=2$)。那么:

  • TEST_STORE 01101 返回 111
  • TEST_STORE 00110 返回 010
  • TEST_STORE 01010 返回 100
  • TEST_STORE 11010 也返回 100

出于安全考虑,数据库隐藏在地下山体金库中,因此调用 TEST_STORE 非常耗时。你的任务是使用最多 $F$ 次 TEST_STORE 调用来找出哪些工作计算机损坏了。

输入格式

这是一个交互式问题。请确保你已阅读我们 FAQ 中关于交互式问题的相关信息。

程序首先应读取包含单个整数 $T$ 的单行,表示测试用例的数量。然后,你需要处理 $T$ 个测试用例。

对于每个测试用例,程序首先读取包含三个整数 $N$、$B$ 和 $F$ 的单行,分别表示工作计算机的数量、损坏的工作计算机数量,以及你可以发送的行数(如下所述)。

然后,你可以向评测机发送最多 $F$ 行,每行包含一个长度恰好为 $N$ 的字符串,由 01 组成。每次发送一行时,评测机都会检查你是否进行了超过 $F$ 次调用。如果超过了,评测机将发送包含单个 -1 的单行,然后结束所有通信并等待你的程序结束。否则,评测机将发送一个长度为 $N-B$ 的字符串:即 TEST_STORE 返回的字符串,如上所述。

一旦你的程序知道了 $B$ 台损坏工作计算机的索引,就可以通过发送 $B$ 个空格分隔的整数来结束该测试用例:即损坏工作计算机的 ID,按升序排列。这不计入你的 $F$ 次调用。

如果这 $B$ 个整数不是损坏工作计算机的准确 ID,你将收到 Wrong Answer 判决,评测机将发送包含 -1 的单行,之后不再进行任何通信。如果你的答案正确,评测机将发送包含 1 的单行,随后是下一测试用例的起始行(如果是最后一个测试用例,则退出)。

数据范围

时间限制:每个测试集 20 秒。 内存限制:1GB。 $1 \le T \le 100$。 $2 \le N \le 1024$。 $1 \le B \le \min(15, N-1)$。

测试集 1(可见)

$F = 10$。

测试集 2(隐藏)

$F = 5$。

样例

样例交互

以下交互满足测试集 1 的限制。

t = readline_int() // 读取 2 到 t
n, b, f = readline_int_list() // 读取 5, 2, 10 到 n, b, f
printline 01101 to stdout // 接下来的四次输出与题目描述中的示例匹配
flush stdout
response = readline_str() // 读取 111 到 response。(此时,我们可以确定答案;剩余的查询仅为示例!)
printline 00110 to stdout
flush stdout
response = readline_str() // 读取 010 到 response
printline 01010 to stdout
flush stdout
response = readline_str() // 读取 100 到 response
printline 11010 to stdout
flush stdout
response = readline_str() // 读取 100 到 response
printline 0 3 to stdout // 猜测答案。注意我们不需要使用所有 10 次允许的查询。
flush stdout
verdict = readline_int() // 读取 1 到 verdict。我们答对了该测试用例!
n, b, f = readline_int_list() // 读取 2, 1, 10 到 n, b, f
printline 01 to stdout // 01 是一个查询,而不是对最终答案的猜测(如果我们想猜测只有 1 号工作计算机损坏,我们必须像下面那样发送 1)
flush stdout
response = readline_str() // 读取 1 到 response
printline 1 to stdout // 进行了一个(错误的)盲猜
verdict = readline_str() // 读取 -1 到 verdict
exit // 退出以避免模糊的 TLE 错误

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.