{"problem":{"name":"[EGOI 2023] Find the Box / 找箱子","description":{"content":"**本题是一道 I/O 式交互题。** 玛伊是一名机器人研究员，在隆德大学工作。她了解到在大学的地下室里有一个价值连城的宝藏。宝藏就在地下深处一个空房间的箱子里。不幸的是，玛伊不能直接去找那个箱子。地下室里非常黑，且带着灯去会引起怀疑。她找到宝藏的唯一办法就是遥控住在地窖里的吸尘器机器人。 地下室是一个 $H\\times W$ 的网格，其中行从 $0$ 到 $H-1$（从上到下）编号，列从 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9465"},"statements":[{"statement_type":"Markdown","content":"**本题是一道 I/O 式交互题。**\n\n玛伊是一名机器人研究员，在隆德大学工作。她了解到在大学的地下室里有一个价值连城的宝藏。宝藏就在地下深处一个空房间的箱子里。不幸的是，玛伊不能直接去找那个箱子。地下室里非常黑，且带着灯去会引起怀疑。她找到宝藏的唯一办法就是遥控住在地窖里的吸尘器机器人。\n\n地下室是一个 $H\\times W$ 的网格，其中行从 $0$ 到 $H-1$（从上到下）编号，列从 $0$ 到 $W-1$（从左到右）编号，也就是说左上角格子是 $(0,0)$，右下角格子是 $(H-1,W-1)$。装宝藏的箱子在与 $(0,0)$ 不同的某个未知的格子中。每天晚上，吸尘器机器人从左上角格子开始在地下室中移动。\n\n每天晚上，玛伊给机器人一系列指令以指导机器人移动，指令是一个包含字符 `<`、`>`、`^` 和 `v` 的字符串。形式化地，如果机器人在格子 $(r,c)$ 且四周未被遮挡，`<` 使得机器人向左移动到 $(r,c-1)$，`>` 使得机器人向右移动到 $(r,c+1)$，`^` 使得机器人向上移动到 $(r-1,c)$，`v` 使得机器人向下移动到 $(r+1,c)$。\n\n地下室的墙十分坚硬，因此如果机器人试图移动到格子外，什么都不会发生。箱子也十分坚硬，并且不能被推动。在每晚结束时，机器人会报告它的位置，并回到左上角格子。\n\n时间就是金钱，因此玛伊需要用尽量少的晚上找到箱子。\n\n## Output\n\n本题是一道 I/O 式交互题。\n\n- 在开始时，你的程序应当输入一行两个整数 $H,W$，表示格子的高度和宽度。\n- 之后，你的程序与交互库交互。在每一轮交互过程中，你应当输出一个问号 `?`，其后是一个非空字符串 $s$ 包含字符 `<`、`>`、`^` 和 `v`。字符串的长度必须至多为 $2\\times10^4$。然后，你的程序输入两个整数 $r,c$（$0\\le r\\le H-1$，$0\\le c\\le W-1$），表示执行完指令后机器人的位置。注意每次询问后，机器人都会回到 $(0,0)$。\n- 当你知道箱子的位置时，输出 `!` 和两个整数 $r_b,c_b$（$0\\le r_b\\le H-1$，$0\\le c_b\\le W-1$），表示箱子的坐标。在这之后，你的程序必须不再进行任何询问并退出。这个最终的输出在计算你的得分时不被计入询问次数。\n\n请确保在每次询问后刷新输出流，否则你的程序可能被判定为 TLE。在 Python 中，`print()` 自动刷新输出流。在 C++ 中，`cout << endl;` 在输出换行后也会刷新输出流；如果使用 `printf`，请使用 `fflush(stdout)`。\n\n交互库不自适应，意味着箱子的位置在交互开始前被确定。\n\n[samples]\n\n## Background\n\nDay 1 Problem C.\n\n题面译自 [EGOI2023 findthebox](https://egoi23.se/assets/tasks/day1/findthebox.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例解释**\n\n考虑样例。格子有高度 $H=4$ 和宽度 $W=5$，箱子在 $(r,c)=(2,3)$。下图展示了机器人在收到指令 `? vv>>>>>><^^^^^>` 后的路径，机器人最终停在 $(r,c)=(0,2)$。在第二次询问前，机器人回到左上角 $(0,0)$。程序询问 `? >>>>>>>>vvvvvvvvvv`，机器人最终停在右下角 $(r,c)=(3,4)$。此时，程序决定猜答案，输出了 `! 2 3`，惊喜地发现，这恰好是箱子的正确位置！\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/f540broe.png)\n\n---\n\n**数据范围**\n\n对于全部数据，$1\\le H,W\\le 50$，箱子不会位于 $(0,0)$ 处（这意味着 $H+W\\ge 3$），每次询问最多包含 $2\\times 10^4$ 个指令，你可以询问至多 $2500$ 次（给出最终答案不被计入询问）。\n\n你的程序会被测试于一定数量的测试点。如果你的程序在*任何*一个测试点失败（例如：给出错误的箱子坐标（WA）、程序崩了（RE）、超出时间限制（TLE）等），你会得到 $0$ 分和适当的评测结果。\n\n如果你的程序在*所有*测试点都成功找到了箱子，你会得到 AC（**译者注：在洛谷，非满分即为 WA**），分数由下式决定：\n\n$$\n\\textrm{score}=\\min\\left(\\frac{100\\sqrt{2}}{\\sqrt{Q}},100\\right)\\textrm{ 分}\n$$\n\n其中 $Q$ 是所有测试点中询问次数的最大值。输出最终答案不被计入询问。分数将被四舍五入到最接近的整数。\n\n具体地，要得到 $100$ 分，你的程序必须在 $Q=2$ 次询问内解决所有测试点。下表展示了一些 $Q$ 的值和其得分。\n\n|$Q$|$2$|$3$|$4$|$5$|$\\cdots$|$20$|$\\cdots$|$50$|$\\cdots$|$2500$|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|分数|$100$|$82$|$71$|$63$|$\\cdots$|$32$|$\\cdots$|$20$|$\\cdots$|$3$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9465","tags":["2023","交互题","Special Judge","O2优化","EGOI（欧洲/女生）"],"sample_group":[["4 5\n\n0 2\n\n3 4","\n? vv>>>>>><^^^^^>\n\n? >>>>>>>>vvvvvvvvvv\n\n! 2 3"]],"created_at":"2026-03-03 11:09:25"}}