← 返回题目列表

Codeforces · 2135/B

B. 为了冠军

中文机器翻译题面 查看原题

这是一个交互问题。

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$$$ 作为对此举动的回应。
?长1011机器人向左移动 $$$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)$$$ 作为机器人的初始坐标。
?升01机器人向左移动 $$$0$$$ 单位,即保持在同一位置。然后,陪审团打印 $$$|(-1)-(-1)|+|0-(-1)|=1$$$ 作为对此举动的响应。可以证明,这是机器人与任意锚点之间的最小曼哈顿距离。
? U 12机器人向上移动$$$1$$$单位,当前坐标为$$$(-1, 1)$$$。然后,陪审团打印 $$$|(-1)-(-1)|+|1-(-1)|=2$$$ 作为对此举动的响应。
? R 20机器人向右移动$$$2$$$个单位,当前坐标为$$$(1, 1)$$$。然后,陪审团打印 $$$|1-1|+|1-1|=0$$$ 作为对此举动的回应。
! -1 0机器人已以某种方式确定其初始坐标并报告答案。由于输出是正确的并且没有更多的测试用例,陪审团和解决方案退出。