P9465 [EGOI 2023] Find the Box / 找箱子

Day 1 Problem C. 题面译自 [EGOI2023 findthebox](https://egoi23.se/assets/tasks/day1/findthebox.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

**本题是一道 I/O 式交互题。** 玛伊是一名机器人研究员，在隆德大学工作。她了解到在大学的地下室里有一个价值连城的宝藏。宝藏就在地下深处一个空房间的箱子里。不幸的是，玛伊不能直接去找那个箱子。地下室里非常黑，且带着灯去会引起怀疑。她找到宝藏的唯一办法就是遥控住在地窖里的吸尘器机器人。 地下室是一个 $H\times W$ 的网格，其中行从 $0$ 到 $H-1$（从上到下）编号，列从 $0$ 到 $W-1$（从左到右）编号，也就是说左上角格子是 $(0,0)$，右下角格子是 $(H-1,W-1)$。装宝藏的箱子在与 $(0,0)$ 不同的某个未知的格子中。每天晚上，吸尘器机器人从左上角格子开始在地下室中移动。 每天晚上，玛伊给机器人一系列指令以指导机器人移动，指令是一个包含字符 ``、`^` 和 `v` 的字符串。形式化地，如果机器人在格子 $(r,c)$ 且四周未被遮挡，`` 使得机器人向右移动到 $(r,c+1)$，`^` 使得机器人向上移动到 $(r-1,c)$，`v` 使得机器人向下移动到 $(r+1,c)$。 地下室的墙十分坚硬，因此如果机器人试图移动到格子外，什么都不会发生。箱子也十分坚硬，并且不能被推动。在每晚结束时，机器人会报告它的位置，并回到左上角格子。 时间就是金钱，因此玛伊需要用尽量少的晚上找到箱子。

无

本题是一道 I/O 式交互题。 - 在开始时，你的程序应当输入一行两个整数 $H,W$，表示格子的高度和宽度。 - 之后，你的程序与交互库交互。在每一轮交互过程中，你应当输出一个问号 `?`，其后是一个非空字符串 $s$ 包含字符 ``、`^` 和 `v`。字符串的长度必须至多为 $2\times10^4$。然后，你的程序输入两个整数 $r,c$（$0\le r\le H-1$，$0\le c\le W-1$），表示执行完指令后机器人的位置。注意每次询问后，机器人都会回到 $(0,0)$。 - 当你知道箱子的位置时，输出 `!` 和两个整数 $r_b,c_b$（$0\le r_b\le H-1$，$0\le c_b\le W-1$），表示箱子的坐标。在这之后，你的程序必须不再进行任何询问并退出。这个最终的输出在计算你的得分时不被计入询问次数。 请确保在每次询问后刷新输出流，否则你的程序可能被判定为 TLE。在 Python 中，`print()` 自动刷新输出流。在 C++ 中，`cout

**样例解释** 考虑样例。格子有高度 $H=4$ 和宽度 $W=5$，箱子在 $(r,c)=(2,3)$。下图展示了机器人在收到指令 `? vv>>>>>>` 后的路径，机器人最终停在 $(r,c)=(0,2)$。在第二次询问前，机器人回到左上角 $(0,0)$。程序询问 `? >>>>>>>>vvvvvvvvvv`，机器人最终停在右下角 $(r,c)=(3,4)$。此时，程序决定猜答案，输出了 `! 2 3`，惊喜地发现，这恰好是箱子的正确位置！  --- **数据范围** 对于全部数据，$1\le H,W\le 50$，箱子不会位于 $(0,0)$ 处（这意味着 $H+W\ge 3$），每次询问最多包含 $2\times 10^4$ 个指令，你可以询问至多 $2500$ 次（给出最终答案不被计入询问）。 你的程序会被测试于一定数量的测试点。如果你的程序在*任何*一个测试点失败（例如：给出错误的箱子坐标（WA）、程序崩了（RE）、超出时间限制（TLE）等），你会得到 $0$ 分和适当的评测结果。 如果你的程序在*所有*测试点都成功找到了箱子，你会得到 AC（**译者注：在洛谷，非满分即为 WA**），分数由下式决定： $$ \textrm{score}=\min\left(\frac{100\sqrt{2}}{\sqrt{Q}},100\right)\textrm{ 分} $$ 其中 $Q$ 是所有测试点中询问次数的最大值。输出最终答案不被计入询问。分数将被四舍五入到最接近的整数。 具体地，要得到 $100$ 分，你的程序必须在 $Q=2$ 次询问内解决所有测试点。下表展示了一些 $Q$ 的值和其得分。 |$Q$|$2$|$3$|$4$|$5$|$\cdots$|$20$|$\cdots$|$50$|$\cdots$|$2500$| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |分数|$100$|$82$|$71$|$63$|$\cdots$|$32$|$\cdots$|$20$|$\cdots$|$3$|