这是一个交互问题。
RiOI团队正在举办机器人锦标赛!
这次,你的机器人被传送到一个 无限 带有笛卡尔坐标系的 2D 平面。平面上有 $$$n$$$ 个锚点,第 $$$i$$$ 个锚点的坐标为 $$$(x_i, y_i)$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$)。一旦你的机器人被传送到飞机上,陪审团就会将这些信息交给你的机器人。然而,你的机器人一开始并不知道它的初始坐标。
为了测试你的机器人的智商,RiOI 团队想出了一个有趣的游戏。您的机器人需要通过以下动作找出初始坐标 $$$(X, Y)$$$ ($$$-10^9\le X, Y\le 10^9$$$)。
在一次移动中,假设当前坐标为 $$$(a,b)$$$,您的机器人可以选择一个非负整数 $$$k$$$ ($$$0\le k\le 10^9$$$) 并执行以下四种操作之一:
- 向上移动$$$k$$$个单位,即你的机器人将移动到$$$(a,b+k)$$$;
- 向下移动$$$k$$$个单位,即你的机器人将移动到$$$(a,b-k)$$$;
- 向左移动$$$k$$$个单位,即你的机器人将移动到$$$(a-k,b)$$$;
- 向右移动 $$$k$$$ 个单位,即你的机器人将移动到 $$$(a+k,b)$$$。
每次移动后,评审团将给出机器人当前坐标与任意锚点之间的最小曼哈顿距离。更正式地说,假设你的机器人在移动后的坐标是 $$$(c,d)$$$,陪审团将输出
$$\min_{1\le i\le n}\left ( \left|x_i-c\right|+\left|y_i-d\right|\right ).$$
要赢得奖品,您必须证明您的机器人具有高智商。所以你必须为你的机器人编写一个程序来找到它 初始 坐标 $$$(X, Y)$$$ 移动不超过 $$$10$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 100$$$) — 锚点的数量。
接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$) — 第 $$$i$$$ 锚点的坐标。
保证锚点的坐标两两不同。
互动
对于每个测试用例,首先读取整数 $$$n$$$ 和锚点的坐标。那么您最多可以进行 $$$10$$$ 的移动。
要进行移动,您应该使用以下格式之一打印新行:
- $$$\texttt{? U }k$$$ — 向上移动 $$$k$$$ 个单位;
- $$$\texttt{? D }k$$$ — 向下移动 $$$k$$$ 个单位;
- $$$\texttt{? L }k$$$ — 向左移动 $$$k$$$ 单位;
- $$$\texttt{? R }k$$$ — 向右移动 $$$k$$$ 单位。
您需要保证$$$0\le k\le 10^{9}$$$。
在每次移动结束时,评审团将打印一个整数 $$$s$$$ — 机器人当前坐标与任意锚点之间的最小曼哈顿距离。
要报告您已找到机器人的初始坐标,请按以下格式打印新行:
- $$$\texttt{! }X\texttt{ }Y$$$ — 机器人的初始坐标是 $$$(X, Y)$$$。
打印答案不算作 $$$10$$$ 动作之一。
之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。
假设你的机器人的初始坐标是$$$(X, Y)$$$。保证 $$$-10^{9}\le X, Y\le 10^{9}$$$。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
这个问题中的交互者是 不 自适应。换句话说,机器人的初始坐标在交互步骤中不会改变。
黑客
要执行黑客攻击,请使用以下格式:
输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 100$$$) — 锚点的数量。
接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$) — 第 $$$i$$$ 锚点的坐标。
在下一行中打印两个整数 $$$X$$$ 和 $$$Y$$$ ($$$-10^9\le X, Y\le 10^9$$$) — 机器人的初始坐标。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 1 0 0 100 1 4 1 1 2 2 3 3 -1 -1 1 2 0
输出复制
? D 99 ? L 101 ! 100 99 ? L 0 ? U 1 ? R 2 ! -1 0
注意
以下是示例的进度:
| 解决方案 | 评审团 | 说明 |
| 2 | 此测试中有 $$$2$$$ 测试用例。 | |
| 1 | 此测试用例中有 $$$1$$$ 锚点。 | |
| 0 0 | 唯一锚点的坐标是$$$(0,0)$$$。 | |
| 评审团选择 $$$(100,99)$$$ 作为机器人的初始坐标。 | ||
| ? 99号 | 100 | 机器人向下移动 $$$99$$$ 单位,当前坐标为 $$$(100, 0)$$$。然后,陪审团打印 $$$|100-0|+|0-0|=100$$$ 作为对此举动的回应。 |
| ?长101 | 1 | 机器人向左移动 $$$101$$$ 单位,当前坐标为 $$$(-1, 0)$$$。然后,陪审团打印 $$$|(-1)-0|+|0-0|=1$$$ 作为对此举动的响应。 |
| ! 100 99 | 机器人以某种方式确定了其初始坐标并报告答案。由于输出正确,陪审团继续进行下一个测试用例。 | |
| 4 | 此测试用例中有 $$$4$$$ 锚点。 | |
| 1 1 | 第一个锚点的坐标是$$$(1,1)$$$。 | |
| 2 2 | 第二个锚点的坐标是$$$(2,2)$$$。 | |
| 3 3 | 第三个锚点的坐标是$$$(3,3)$$$。 | |
| -1 -1 | 第四个锚点的坐标是$$$(-1,-1)$$$。 | |
| 评审团选择 $$$(-1,0)$$$ 作为机器人的初始坐标。 | ||
| ?升0 | 1 | 机器人向左移动 $$$0$$$ 单位,即保持在同一位置。然后,陪审团打印 $$$|(-1)-(-1)|+|0-(-1)|=1$$$ 作为对此举动的响应。可以证明,这是机器人与任意锚点之间的最小曼哈顿距离。 |
| ? U 1 | 2 | 机器人向上移动$$$1$$$单位,当前坐标为$$$(-1, 1)$$$。然后,陪审团打印 $$$|(-1)-(-1)|+|1-(-1)|=2$$$ 作为对此举动的响应。 |
| ? R 2 | 0 | 机器人向右移动$$$2$$$个单位,当前坐标为$$$(1, 1)$$$。然后,陪审团打印 $$$|1-1|+|1-1|=0$$$ 作为对此举动的回应。 |
| ! -1 0 | 机器人已以某种方式确定其初始坐标并报告答案。由于输出是正确的并且没有更多的测试用例,陪审团和解决方案退出。 |