Guess the Cycle Size

题意翻译

## 题意简述 现有一个有 $n$ 个结点的无向图,这个图是一个循环图(圈状)：这个循环图的边数恰好是 $n$ ,这个图的点从 $1$ 到 $n$编号 ,点的顺序是任意的.你可以以这种方式 $?$ $a$ $b$ 以询问 $a$ 和 $b$ 之间的距离,如果 $a$ 或者 $b$ 超过了 $n$ ,则给你返回$-1$,给你最多50次询问机会,你需要以如下方式 $!$ $n$ 回答你判断的图中点的个数 注意 , $?$ $a$ $b$ 与 $?$ $b$ $a$ 的值可能不同.交互器会以相同的概率选择两个顶点之间路径之一. 图中的顶点是随机放置的,点的位置是固定的 ### 数据范围 $1\leq a,b\leq10^{18} , 3\leq n\leq10^{18}$

题目描述

This is an interactive problem. I want to play a game with you... We hid from you a cyclic graph of $ n $ vertices ( $ 3 \le n \le 10^{18} $ ). A cyclic graph is an undirected graph of $ n $ vertices that form one cycle. Each vertex belongs to the cycle, i.e. the length of the cycle (the number of edges in it) is exactly $ n $ . The order of the vertices in the cycle is arbitrary. You can make queries in the following way: - "? a b" where $ 1 \le a, b \le 10^{18} $ and $ a \neq b $ . In response to the query, the interactor outputs on a separate line the length of random of two paths from vertex $ a $ to vertex $ b $ , or -1 if $ \max(a, b) > n $ . The interactor chooses one of the two paths with equal probability. The length of the path —is the number of edges in it. You win if you guess the number of vertices in the hidden graph (number $ n $ ) by making no more than $ 50 $ queries. Note that the interactor is implemented in such a way that for any ordered pair $ (a, b) $ , it always returns the same value for query "? a b", no matter how many such queries. Note that the "? b a" query may be answered differently by the interactor. The vertices in the graph are randomly placed, and their positions are fixed in advance. Hacks are forbidden in this problem. The number of tests the jury has is $ 50 $ .

输入输出格式

输入格式

输出格式

You can make no more than $ 50 $ of queries. To make a query, output on a separate line: - "? a b", where $ 1 \le a, b \le 10^{18} $ and $ a \neq b $ . In response to the query, the interactor will output on a separate line the length of a random simple path from vertex $ a $ to vertex $ b $ (not to be confused with the path from $ b $ to $ a $ ), or $ -1 $ if $ \max(a, b) > n $ . The interactor chooses one of the two paths with equal probability. If your program gets a number 0 as a result of a query, it means that the verdict for your solution is already defined as "wrong answer" (for example, you made more than $ 50 $ queries or made an invalid query). In this case, your program should terminate immediately. Otherwise, in this scenario you may get a random verdict "Execution error", "Exceeded time limit" or some other verdict instead of "Wrong answer". The answer, like queries, print on a separate line. The output of the answer is not counted as a query when counting them. To print it, use the following format: - "! n": the expected size of the hidden graph ( $ 3 \le n \le 10^{18} $ ). After that, your program should terminate. After the output of the next query, be sure to use stream cleaning functions so that some of your output is not left in some buffer. For example, in C++ you should use function flush(stdout), in Java call System.out.flush(), in Pascal flush(output) and stdout.flush() for Python. Note that the interactor is implemented in such a way that for any ordered pair $ (a, b) $ , it always returns the same value for query "? a b", no matter how many such queries. Note that the "? b a" query may be answered differently by the interactor. The vertices in the graph are randomly placed, and their positions are fixed in advance. Hacks are forbidden in this problem. The number of tests the jury has is $ 50 $ .

输入输出样例

输入样例 #1

1

2

-1

输出样例 #1

? 1 2

? 1 3

? 1 4

! 3

说明

In the first example, the graph could look like this The lengths of the simple paths between all pairs of vertices in this case are $ 1 $ or $ 2 $ . - The first query finds out that one of the simple paths from vertex $ 1 $ to vertex $ 2 $ has a length of $ 1 $ . - With the second query, we find out that one of the simple paths from vertex $ 1 $ to vertex $ 3 $ has length $ 2 $ . - In the third query, we find out that vertex $ 4 $ is not in the graph. Consequently, the size of the graph is $ 3 $ .