P13711 [NWERC 2023] Lateral Damage

你正在一片辽阔的海洋中玩“战舰”游戏，使用的是大型战舰。 更具体地说，有一个最大为 $100\times 100$ 的正方形网格，在其中最多有 $10$ 艘“战舰”游戏中最大的舰种——航空母舰。每艘航空母舰长度为 $5$ 个格子，可以水平或垂直放置。 这些舰船不会重叠，但允许彼此相邻。参见图 L.1 示例。  :::align{center} 原始的“战舰”游戏，在升级为 $100\times 100$ 网格之前。CC BY-NC 3.0，作者 Pavel Ševela，来源 [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Hra_n%C3%A1mo%C5%99n%C3%AD_bitva_(1).jpg) ::: 不幸的是，你的对手似乎会随心所欲地修改规则。 看起来他们并不总是在你开始射击前就确定舰船的位置。 你对他们的作弊行为并不感到惊讶，决定无论如何都要赢得这场游戏。  :::align{center} 图 L.1：示例交互 1，在前四次射击后。 ::: 你的目标是在最多 $2500$ 次射击内找出并击沉所有对手的航空母舰，也就是说，你必须击中所有舰船的每一个格子（每艘船有 $5$ 个格子）。

这是一个交互题。 你的提交将与一个“交互器”进行对话，交互器从你的标准输出读取数据，并向你的标准输入写入数据。交互过程遵循如下协议： 交互器首先输出一行两个整数 $n$ 和 $k$（$5 \le n \le 100$，$1 \le k \le 10$），分别表示网格的大小和舰船的数量。保证可以在网格中放下 $k$ 艘航空母舰且不重叠。 接下来，你的程序需要开始射击。 每次射击通过输出一行“$\texttt{x y}$”来完成（$1 \le x, y \le n$），表示你向 $(x, y)$ 位置射击。交互器会返回“$\texttt{hit}$”表示命中，“$\texttt{sunk}$”表示击沉了一艘航空母舰，“$\texttt{miss}$”表示未命中。如果你对同一位置重复射击，返回结果为“$\texttt{miss}$”。 当你击沉最后一艘航空母舰时，交互结束，你的程序应当退出。 交互器是自适应的：舰船的位置可能在交互过程中动态决定，并且可能依赖于你的射击位置。 每次输出后请确保刷新输出缓冲区。 题目提供了测试工具以帮助你开发解决方案。 如果射击次数超过 $2500$ 次，将判为错误答案。

无

由 ChatGPT 4.1 翻译