← 返回题目列表

Codeforces · 1729/E

E. 猜测周期大小

中文机器翻译题面 查看原题

这是一个交互问题。

我想和你玩游戏...

我们向您隐藏了 $$$n$$$ 个顶点的循环图 ($$$3 \le n \le 10^{18}$$$)。循环图是由 $$$n$$$ 顶点组成一个循环的无向图。每个顶点都属于循环,即循环的长度(其中的边数)恰好为$$$n$$$。循环中顶点的顺序是任意的。

您可以通过以下方式进行查询:

- “? a b”,其中 $$$1 \le a、b \le 10^{18}$$$ 和 $$$a \neq b$$$。为了响应查询,交互器在单独的行上输出从顶点 $$$a$$$ 到顶点 $$$b$$$ 的两条路径的随机长度,如果 $$$\max(a, b) > n$$$,则输出 -1。交互者以相同的概率选择两条路径之一。路径的长度——是其中的边数。

如果您通过进行不超过 $$$50$$$ 查询来猜测隐藏图中的顶点数量(数量 $$$n$$$),那么您就赢了。

请注意,交互器的实现方式是,对于任何有序对 $$$(a, b)$$$,它始终为查询“? a b”返回相同的值,无论有多少个这样的查询。请注意,交互器可能会以不同的方式回答“? b a”查询。

图中的顶点是随机放置的,并且它们的位置是预先固定的。

此问题禁止黑客攻击。陪审团的测试数量为 $$$50$$$。

互动

您最多可以进行 $$$50$$$ 的查询。要进行查询,请在单独的行上输出:

- “? a b”,其中 $$$1 \le a、b \le 10^{18}$$$ 和 $$$a \neq b$$$。为了响应查询,交互器将在单独的行上输出从顶点 $$$a$$$ 到顶点 $$$b$$$ 的随机简单路径的长度(不要与从 $$$b$$$ 到 $$$a$$$ 的路径混淆),或者如果 $$$\max(a, b) > n$$$ 则输出 $$$-1$$$。交互者以相同的概率选择两条路径之一。

如果您的程序在查询结果中得到数字 0,则意味着您的解决方案的结论已被定义为“错误答案”(例如,您进行了超过 $$$50$$$ 查询或进行了无效查询)。在这种情况下,您的程序应立即终止。否则,在这种情况下,您可能会得到一个随机判决“执行错误”、“超出时间限制”或其他一些判决,而不是“错误答案”。

答案与查询一样,打印在单独的行上。在计算它们时,答案的输出不计为查询。要打印它,请使用以下格式:

- “!n”:隐藏图的预期大小 ($$$3 \le n \le 10^{18}$$$)。

之后,您的程序应该终止。

下一个查询输出后,请务必使用流清理功能,以便某些输出不会留在某些缓冲区中。例如,在C++中,您应该使用函数flush(stdout),在Java中,您应该使用System.out.flush(),在Pascal中,您应该使用flush(output),而在Python中,您应该使用stdout.flush()。

请注意,交互器的实现方式是,对于任何有序对 $$$(a, b)$$$,它始终为查询“? a b”返回相同的值,无论有多少个这样的查询。请注意,交互器可能会以不同的方式回答“? b a”查询。

图中的顶点是随机放置的,并且它们的位置是预先固定的。

此问题禁止黑客攻击。陪审团的测试数量为 $$$50$$$。

示例

输入 #1

1

2

-1

输出 #1

? 1 2

? 1 3

? 1 4

! 3

注意

在第一个示例中,图表可能如下所示

在这种情况下,所有顶点对之间的简单路径的长度为 $$$1$$$ 或 $$$2$$$。

- 第一个查询发现从顶点 $$$1$$$ 到顶点 $$$2$$$ 的简单路径之一的长度为 $$$1$$$。
- 通过第二个查询,我们发现从顶点 $$$1$$$ 到顶点 $$$3$$$ 的简单路径之一的长度为 $$$2$$$。
- 在第三个查询中,我们发现顶点 $$$4$$$ 不在图中。因此,图表的大小为 $$$3$$$。