题目描述

题目译自 European Girls' Olympiad in Informatics 2023 Day1 T3. Find the Box

玛伊是隆德大学的机器人研究者。她听说大学地下室里藏着一件珍贵的宝物，装在一个宝箱中，位于地下深处一个空房间的某个格子里。可惜，玛伊无法亲自前往寻找，因为地下室非常黑暗，带灯进去会引起怀疑。她唯一的方法是远程控制居住在地下室的机器人吸尘器来寻找宝箱。

地下室被表示为一个 $H \times W$ 的网格，行从 $0$ 到 $H-1$（从上到下）编号，列从 $0$ 到 $W-1$（从左到右）编号。因此，左上角格子为 $(0, 0)$，右下角格子为 $(H-1, W-1)$。宝箱位于某个未知格子，但不会在 $(0, 0)$。

每晚，机器人吸尘器从左上角开始，在地下室中移动。玛伊可以给机器人发送一串指令，告诉它如何移动，指令由字符 <、>、^ 和 v 组成。具体来说，如果机器人在格子 $(r, c)$ 上，且四周无障碍：

• <：向左移动到 $(r, c-1)$。
• >：向右移动到 $(r, c+1)$。
• ^：向上移动到 $(r-1, c)$。
• v：向下移动到 $(r+1, c)$。

地下室的墙壁是坚固的，如果机器人试图移出网格，将停留在原地。宝箱也是固定的，无法被推动。每晚结束后，机器人会报告其所在位置，并返回左上角 $(0, 0)$。

时间紧迫，玛伊希望用最少的夜晚找到宝箱。

交互方式

这是一个交互题。

• 你的程序首先读取一行，包含两个整数 $H, W$，表示网格的高度和宽度。
• 然后，你的程序与交互器交互。每轮交互中： 你应输出一个问号 ?，后跟一个非空字符串 $s$，由字符 <、>、^、v 组成。字符串长度最多为 $20000$。 然后，读取两个整数 $r, c$（$0 \leq r \leq H-1, 0 \leq c \leq W-1$），表示机器人执行指令后的位置。注意，每次查询后，机器人都会回到 $(0, 0)$。
• 当你确定宝箱位置时，输出 !，后跟两个整数 $r_b, c_b$（$0 \leq r_b \leq H-1, 0 \leq c_b \leq W-1$），表示宝箱的行和列。之后，你的程序必须退出，不再进行任何查询。此最终输出不计入查询次数。

注意：每次查询后需刷新标准输出，否则可能被判为「Time Limit Exceeded」。在 Python 中，print() 自动刷新；在 C++ 中，cout << endl; 会刷新并换行；若使用 printf，需调用 fflush(stdout)。

交互器是非自适应的，宝箱位置在交互开始前已确定。

样例

网格高度 $H=4$，宽度 $W=5$，宝箱位于 $(r, c) = (2, 3)$。下图显示了第一次查询 ? vv>>>>>><^^^^^>! 时机器人的路径，最终停在 $(r, c) = (0, 2)$。第二次查询前，机器人回到左上角 $(0, 0)$。然后，程序发出第二次查询 ? >>>>>>>>vvvvvvvvvv!，机器人停在右下角 $(r, c) = (3, 4)$。随后，程序决定猜测答案，输出 ! 2 3，这是宝箱的正确位置。

交互器输出	用户程序输出
4 5
	? vv>>>>>><^^^^^^>
0 2
	? >>>>>>>>vvvvvvvvvv
3 4
	! 2 3

数据范围与提示

对于所有输入数据，满足：

• $1 \leq H, W \leq 50$
• 宝箱不会位于 $(0, 0)$，因此 $H + W \geq 3$
• 每次查询的指令字符串长度最多为 $20000$
• 你最多可进行 $2500$ 次查询（输出最终答案不计入查询次数）

如果你的程序在所有测试点中成功找到宝箱位置，你将被判为「Accepted」，并按以下公式计算分数：

$$\text{score} = \min\left(\frac{100\sqrt{2}}{\sqrt{Q}}, 100\right) $$

其中 $Q$ 是任意测试点中使用的最大查询次数。输出最终答案不计入查询次数。分数将四舍五入到最近的整数。

特别地，要获得 $100$ 分，你的程序必须在每个测试点中使用最多 $Q=2$ 次查询。下表显示了部分 $Q$ 值及其对应的分数：

$Q$	$2$	$3$	$4$	$5$	$\ldots$	$20$	$\ldots$	$50$	$\ldots$	$2500$
分数	$100$	$82$	$71$	$63$	$\ldots$	$32$	$\ldots$	$20$	$\ldots$	$3$

测试工具

为方便测试，我们提供了一个简单的测试工具，可在「文件」界面下载。你可以选择是否使用该工具，你可以对其进行修改。

注意，官方评分程序与测试工具不同。

示例用法（以 $H=4, W=5$，宝箱位置为 $r=2, c=3$ 为例）：

对于 Python 程序（如 solution.py，通常运行 pypy3 solution.py）：

python3 testing_tool.py pypy3 solution.py <<<"4 5 2 3"

对于 C++ 程序，先编译（例如 g++ -g -O2 -std=gnu++17 -static solution.cpp -o solution.out），然后运行：

python3 testing_tool.py ./solution.out <<<"4 5 2 3"