QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif

#8451. Karl Coder

Statistiques

Karl 是一位有抱负的 C 语言程序员,他对底层手动内存管理的风险与回报感到兴奋。在他目前开发的程序中,他将一个包含 $N$ 个非零字节的字符串存储在一个名为 buf 的缓冲区中。由于失误,他错误地将缓冲区的大小设为了 $2N$。缓冲区最后的 $N$ 个字节全部为零。

现在,Karl 需要在程序的另一部分获取字符串的长度 $N$。传统上,你会使用 strlen 函数通过线性扫描来获取缓冲区中第一个零字节的位置,从而恢复字符串的长度。然而,Karl 发现这种方法太慢了,这违背了使用 C 语言的初衷。你能否帮助 Karl 在不导致程序崩溃的情况下高效地恢复 $N$?

样例交互 3 中的缓冲区内容如图所示。

交互

这是一个交互式问题,交互过程分多轮进行。在每一轮中,你的程序可以尝试从缓冲区读取一个字节或报告答案($N$ 的值):

  • read: 如果你想尝试读取缓冲区的第 $i$ 个字节,请输出一行包含 buf[i] 的内容。如果 $0 \le i < 2N$,你将得到存储在缓冲区索引 $i$ 处的字节值。如果 $i < N$,这将是一个 1 到 255 之间的整数;否则,它将是 0。如果 $i \ge 2N$ 或 $i < 0$,你将收到响应 Segmentation fault (core dumped),此时你的程序应退出。
  • answer: 如果你想报告你认为 $N = M$,请输出一行包含 strlen(buf) = M 的内容。随后你的程序应退出。如果你的回答正确,且没有触发段错误,也没有尝试读取缓冲区次数过多,你的提交将被接受。

最多可以进行 $2\lceil \log_2 N \rceil$ 次读取。如果你的程序在达到限制后仍尝试从缓冲区读取,它将收到响应 Too many reads,此时你的程序应退出。

保证 $2 \le N \le 10^{18}$。

样例

输入格式 1

65

输出格式 1

buf[1]

输入格式 2

0

输出格式 2

buf[2]

输入格式 3

strlen(buf) = 2

输入格式 4

50

输出格式 4

buf[1]

输入格式 5

0

输出格式 5

buf[5]

输入格式 6

Segmentation fault (core dumped)

输出格式 6

buf[7]

输入格式 7

78

输出格式 7

buf[0]

输入格式 8

67

输出格式 8

buf[1]

输入格式 9

80

输出格式 9

buf[2]

输入格式 10

67

输出格式 10

buf[3]

输入格式 11

Too many reads

输出格式 11

buf[4]

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.