QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 1024 MB Total points: 34 Interactive

#12426. 蒙眼靶心

Statistics

Gary 有一面巨大的正方形墙,高和宽均为 $2 \times 10^9$ 纳米。墙上放置了一个圆形飞镖靶,其半径在 $A$ 到 $B$ 纳米之间(包含 $A$ 和 $B$)。飞镖靶完全位于墙内,但可以接触墙的边缘。飞镖靶的圆心距离墙的每一条边均为整数纳米。

Gary 邀请他的朋友 Mika 来玩一个有趣的游戏。Gary 蒙住 Mika 的眼睛,并挑战她向飞镖靶的中心投掷飞镖。为了帮助她,每当 Mika 向墙上投掷飞镖时,Gary 都会告诉她飞镖是否击中了飞镖靶。

Mika 不知道飞镖靶在墙上的位置,但由于 Mika 飞镖技术精湛,她可以以纳米级的精度投掷飞镖。也就是说,她可以瞄准并击中距离墙的每一条边均为整数纳米的任何点。在每次投掷飞镖后,Gary 会立即告诉她是否击中了飞镖靶的中心、飞镖靶的其他部分,或者完全没中而击中了光秃秃的墙面。

你能帮助 Mika 击中飞镖靶的中心,且投掷次数不超过 300 次吗?

输入格式

程序首先应读取一行,包含三个整数 $T$、$A$ 和 $B$,分别表示测试用例的数量以及飞镖靶半径的最小值和最大值(包含)。(注意:对于同一个测试集中的每个测试用例,$A$ 和 $B$ 是相同的。)

然后,你需要处理 $T$ 个测试用例。

我们将飞镖可以瞄准的点表示为坐标对 $(x, y)$,其中 $x$ 和 $y$ 是 $-10^9$ 到 $10^9$ 之间的整数(包含)。坐标对 $(x, y)$ 表示距离墙左边缘 $x + 10^9$ 纳米、距离墙底边缘 $y + 10^9$ 纳米的点。因此,点 $(0, 0)$ 位于墙的中心。

对于每个测试用例,裁判会以设计好的(非随机)方式在限制范围内秘密选择一个半径 $R$ 和一个飞镖靶中心 $(X, Y)$。对于每个测试用例,你需要与裁判进行最多 300 次交互。你的程序代表 Mika,裁判程序代表 Gary。

第 $i$ 次交互中,你的程序首先输出一行,包含两个整数 $X_i$ 和 $Y_i$,两者均在 $-10^9$ 到 $10^9$ 之间(包含),裁判会回复一行,内容为以下之一:

  • CENTER,如果 $X_i = X$ 且 $Y_i = Y$
  • HIT,如果 $0 < (X - X_i)^2 + (Y - Y_i)^2 \leq R^2$
  • MISS,在其他所有情况下。

在发送 CENTER 后,裁判将开始等待下一个测试用例的第一次交互(如果有的话)。

如果你输出的格式不正确或包含越界的值,裁判将回复一行 WRONG。如果在没有收到 CENTER 的情况下进行了 300 次交互(包括裁判的 300 次回复),或者如果你收到了 WRONG,裁判将结束所有通信。

数据范围

时间限制:每个测试集 30 秒。 内存限制:1GB。 $1 \leq T \leq 20$。 $A \leq R \leq B$。 $-10^9 + R \leq X \leq 10^9 - R$。 $-10^9 + R \leq Y \leq 10^9 - R$。

子任务

测试集 1(可见判决) $A = B = 10^9 - 5$。

测试集 2(可见判决) $A = B = 10^9 - 50$。

测试集 3(隐藏判决) $A = 10^9 / 2$。 $B = 10^9$。

样例

// 以下读取 20 到 t,999999995 到 a 和 b。
t, a, b = readline_int_list()
// 裁判秘密选择 R = 999999995(此处无选择余地)以及 X = -1, Y = 3(此处有选择余地)。
// (注意:实际的测试集 1 不一定使用此示例中的值。)
// 我们尝试瞄准墙的左上角,飞镖靶不覆盖该点。
printline -1000000000 1000000000 to stdout
flush stdout
r = readline_string() // 读取 MISS。
// 我们尝试瞄准墙的中心。这击中了飞镖靶,但不是中心。
printline 0 0 to stdout
flush stdout
r = readline_string() // 读取 HIT。
// 我们做了一个超级幸运的选择,瞄准了飞镖靶的中心。
printline -1 3 to stdout
flush stdout
r = readline_string() // 读取 CENTER。
// 裁判开始下一个测试用例。它秘密选择 R = 999999995 且 X = 5, Y = 5。
// 我们不小心投掷了一个超出允许范围的飞镖。
printline -1234567890 1234567890 to stdout
flush stdout
r = readline_string() // 读取 WRONG。
exit // 退出以避免模糊的 TLE 错误。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.