← 返回题目列表

Codeforces · 1999/G1

G1. 尺子(简易版)

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

这是问题的简单版本。两个版本之间的唯一区别是,在此版本中,您最多可以进行 $$$\mathbf{10}$$$ 查询。

这是一个交互问题。如果您不确定交互式问题如何运作,建议您阅读参与者指南。

我们有一把秘密统治者,缺少一个数字 $$$x$$$ ($$$2 \leq x \leq 999$$$)。当您测量长度为 $$$y$$$ 的物体时,标尺会报告以下值:

- 如果 $$$y < x$$$,则标尺(正确)测量对象的长度为 $$$y$$$。
- 如果 $$$y \geq x$$$,则标尺错误地将对象测量为长度为 $$$y+1$$$。

上面的标尺缺少数字 $$$4$$$,因此它正确地将第一段测量为长度 $$$3$$$,但错误地将第二段测量为长度 $$$6$$$,即使它实际上是 $$$5$$$。

您需要找到 $$$x$$$ 的值。为此,您可以进行以下形式的查询:

- $$$\texttt{?}~a~b$$$ — 作为响应,我们将用尺子测量 $$$a \times b$$$ 矩形的边长,然后将结果相乘,将矩形的测量面积报告给您。例如,如果 $$$x=4$$$ 并且您查询 $$$3 \times 5$$$ 矩形,我们将测量其边长为 $$$3 \times 6$$$ 并向您报告 $$$18$$$。

查找 $$$x$$$ 的值。您最多可以提出 $$$\mathbf{10}$$$ 查询。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

互动

每个测试用例没有初始输入。您应该通过询问来开始交互。

要进行查询,请输出 $$$\texttt{?}~a~b$$$ ($$$1 \leq a, b \leq 1000$$$) 形式的单行。作为回应,您将被告知根据我们的秘密尺子测量的矩形面积。

当您准备好打印答案时,输出 $$$\texttt{!}~x$$$ ($$$2 \leq x \leq 999$$$) 形式的单行。之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。打印答案不算作查询。

交互器不具有自适应性,这意味着答案在参与者提出问题之前就已知,并且不依赖于参与者提出的问题。

如果您的程序对一组输入数据进行超过 $$$10$$$ 查询、进行无效查询或打印错误的 $$$x$$$ 值,则对查询的响应将为 $$$-1$$$。收到这样的响应后,您的程序应立即终止以接收“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则,您可能会得到超出空闲限制的判决。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要进行破解,请使用以下格式。

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的唯一行应包含一个整数 $$$x$$$ ($$$2 \leq x \leq 999$$$) - 标尺上缺少的数字。

示例

输入 #1

2

18

25


9999

输出 #1

? 3 5

? 4 4

! 4
? 99 100

! 100

注意

在第一个测试中,交互进行如下。

SolutionJuryExplanation$$$\texttt{2}$$$有 2 个测试用例。$$$\texttt{? 3 5}$$$$$$\texttt{18}$$$陪审团秘密地选择了$$$x=4$$$。该解决方案要求 $$$3 \times 5$$$ 矩形,陪审团以 $$$3 \times 6 = 18$$$ 响应,如声明中所述。$$$\texttt{? 4 4}$$$$$$\texttt{25}$$$该解决方案要求 $$$4 \times 4$$$ 矩形,陪审团将其测量为 $$$5 \times 5$$$ 并以 $$$25$$$.$$$\texttt{! 4}$$$解决方案以某种方式确定$$$x=4$$$,并将其输出。由于输出正确,陪审团继续进行下一个测试用例。$$$\texttt{? 99 100}$$$$$$\texttt{1}$$$陪审团秘密地选择了$$$x=100$$$。该解决方案要求 $$$99 \times 100$$$ 矩形,陪审团将其测量为 $$$99 \times 101$$$,并以 $$$9999$$$.$$$\texttt{! 100}$$$解决方案以某种方式确定$$$x=100$$$,并将其输出。由于输出是正确的并且没有更多的测试用例,陪审团和解决方案退出。

请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。