1512 : 测试玻璃

时间限制Time Limit 5 秒Sec 内存限制Memory Limit 256 兆MB 提交次数Submitted 0 次Times 通过次数Solved 0 次Times 交互评测Interactive Judge

题目描述Description

百闻不如一试。

— 匿名

这是一道交互题

最新研发的玻璃横空出世，现在要你来测试这款玻璃的硬度。

你需要在一栋有 n 层楼的高楼进行测试。因为玻璃未能实现量产，只有 m 块玻璃供你测试，但能保证所有的玻璃的硬度都是相同的。

你需要通过往下扔玻璃的方式来测试。换句话说，你可以进行以下查询：

已进行的测试不会影响玻璃的硬度，但碎了的玻璃无法继续使用。

玻璃的硬度为 h 当且仅当满足以下条件:

此外，玻璃在第 n + 1 层及以上扔下必碎，也就是说，玻璃的硬度 h 满足 0 \le h \le n 。

由于时间有限，你需要在有限次数内测出玻璃的硬度。

本题仅作场景假设，现实生活中严禁高空抛物。

每个测试包含多个测试用例。第一行包含测试用例的数量 t（1 \le t \le 10^4）。接下来是每个测试用例的描述。

每个测试用例仅一行包含两个整数 n 和 m（1 \leq m \leq 2 \cdot 10^5，1 \leq n \leq min(\left(\lceil\frac{2 \cdot 10^5}{m}\rceil\right)^m, 10^{18})）— 分别表示有 n 层楼和 m 块玻璃。

保证所有测试用例的 m \cdot \lfloor{n}^{\frac{1}{m}}\rfloor 之和不超过 2 \cdot 10^5。

对于每个测试用例，输出一个整数 h — 玻璃的硬度。

具体输出格式请查看交互说明。

交互说明

要进行查询，请按以下格式输出一行：

作为查询的响应，您将收到：

要报告答案，请按以下格式输出一行：

之后，继续执行下一个测试用例；如果这是最后一个测试用例，则终止程序。

你最多进行 k （未知）次查询，其中 k 为有 n 层 m 块玻璃时，最坏情况下需要得出玻璃硬度的测试次数。

请注意，报告答案不计入 k 次查询。

交互器是不自适应的。这意味着玻璃的硬度在一开始就已确定，不会根据您的查询而改变。

在打印每个查询后，不要忘记输出行尾并刷新输出 ¹。否则，你可能会收到 Idleness limit exceeded 的判决。

如果在任何交互步骤中，你读取到 -1 而不是有效数据，你的程序必须立即退出。这意味着你的程序将因为无效查询或其他错误而收到 Wrong answer。未能退出可能导致任意判决，因为你的程序将继续从已关闭的流中读取。

要刷新输出缓冲区，请使用：
- 在 C++ 中使用 fflush(stdout) 或 cout.flush()；
- 在 Python 中使用 sys.stdout.flush()；
- 其他语言请参阅相应文档。
↩︎

在测试样例中，交互过程如下。

解决方案	交互器	解释
	3	有 3 个测试用例。
	5 2	在第一个测试用例中，有 5 层 2 块玻璃（可计算得出最坏情况下需要至少 3 次查询）。
? 3	0	解决方案查询 3。交互器响应 0
? 5	1	解决方案查询 5。交互器响应 1
? 4	0	解决方案查询 4。交互器响应 0
! 4		由f = 4 时没碎， f = 5 时碎了可知玻璃的硬度为 4
	3 1	在第二个测试用例中，有 3 层 1 块玻璃（可计算得出最坏情况下需要至少 3 次查询）
? 1	0	解决方案查询 1。交互器响应 0
? 2	0	解决方案查询 2。交互器响应 0
? 3	0	解决方案查询 3。交互器响应 0
! 3		玻璃在 1, 2, 3 层都没碎可知玻璃的硬度为 3
	2 2	在第三个测试用例中，有 2 层 2 块玻璃（可计算得出最坏情况下需要至少 2 次查询）
? 1	1	解决方案查询 1。交互器响应 1
! 0		玻璃从第 1 层扔下碎了，说明硬度为 0

请注意，示例输入和输出中的空行只是为了方便阅读。它们不会出现在实际的交互中。

shihen

深圳技术大学第六届程序设计竞赛