QOJ.ac

QOJ

时间限制: 10.0 s 内存限制: 1024 MB 总分: 100 交互

#10092. 交互式素性测试

统计

这是一个交互式问题。

评测系统选择了 $T \le 10$ 个整数,范围在 $1$ 到 $10^{18}$(包含边界)。你需要逐一猜出这些数字。

假设评测系统选择的数字为 $x$。你可以重复询问一个 $1$ 到 $10^{18}$ 之间的整数 $y$,系统会告知你 $x + y$ 是素数还是合数。当你猜出该数字时,请将其输出,然后开始猜测下一个数字。

除了样例测试外,所有 $T$ 个数字都是从区间 $[1, 10^{18}]$ 中独立且均匀随机选择的。你需要使用总共不超过 $8750$ 次询问来猜出所有数字。

交互协议

首先,读取一行包含整数 $T$ 的内容:评测系统选择的整数个数($1 \le T \le 10$)。评测系统选择了 $T$ 个秘密整数 $x_1, \dots, x_T$,你需要依次猜出它们($1 \le x_i \le 10^{18}$)。

假设你正在尝试猜测数字 $x_i$。要进行一次询问,请输出一行格式为 “? y” 的内容($1 \le y \le 10^{18}$)。然后读取下一行:

  • 如果 $x_i + y$ 是素数,你将读取到单词 “Prime”;
  • 如果 $x_i + y$ 是合数,你将读取到单词 “Composite”;
  • 如果你进行了无效的询问(在整个程序运行期间第 $8751$ 次询问;或格式不符合要求;或 $y$ 不是规定范围内的正整数),你将读取到单词 “Busted”。

当你认为你知道 $x_i = z$ 时,请输出一行格式为 “! z” 的内容($1 \le z \le 10^{18}$)。该行不计入询问次数限制。然后读取下一行:

  • 如果确实 $x_i = z$,你将读取到单词 “Correct”。如果 $i = T$,程序应终止;否则,继续猜测数字 $x_{i+1}$。
  • 如果 $x_i \neq z$ 或者你违反了输出格式,你将读取到单词 “Busted”。

读取到 “Busted” 后,你的程序必须立即终止以获得 Wrong Answer 判决。否则,判决结果将不可预测。

样例

样例输入 1

1
Composite
Prime
Prime
Prime
Correct

样例输出 1

? 6
? 5
? 3
? 1
! 2

说明

共有 $30$ 组测试数据。在第 $i$ 组测试中,$T = \min\{i, 10\}$。在每组测试中,选定的 $T$ 个整数是预先固定的:对于每个解法的每次运行,它们都是相同的,并且在交互过程中不会改变。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#605Editorial Open集训队作业 解题报告 by 邱梓轩Qingyu2026-01-02 23:00:36 Download

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.