← 返回题目列表

AtCoder · future_contest_2023_final_a

A. 探矿棒

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

问题陈述

通灵者高桥发现了一张藏宝图。 到地图上有 50 在无人居住的岛屿的地下埋藏着宝藏。 该岛呈圆形,半径为 R=10^9。 不幸的是,地图上没有标明埋藏宝藏的位置。 既然不可能把地面全部挖出来,他决定用神通按照以下方式寻找宝藏。

  1. 选择所需位置并立一根木杆。
  2. 如果半径范围内有宝藏 D=10^6 从选定的位置开始,棍子将保持站立状态,他可以通过挖掘半径内的所有区域来找到宝藏 D.
  3. 如果半径范围内没有宝藏 D 从选定的位置开始,棒子会根据下面描述的规则向某个方向落下,从而提供宝藏位置的线索。

通过重复此过程直至 1000 次,尽快找到尽可能多的宝藏。

杆下落方向的规律

让 q=(qx, qy) 是杆所在的坐标,然后是下落方向 \theta (0\leq \theta<2\pi) 使用常数计算如下 \sigma 作为输入给出。

  1. 在尚未挖出的宝藏中,以与欧氏距离平方的倒数成正比的概率选择一个 q.
  2. 让 p=(px,py) 为所选宝藏的坐标,并计算方向 \hat{\theta}=\mathrm{atan2}(py-qy,px-qx) of p-q.
  3. 从具有均值的高斯分布中采样一个值 \hat{\theta} 和标准差 \sigma 并让 \theta 为余数除以 2\pi.

输入和输出

一、标准差 \sigma 在标准输入的一行中给出。 \sigma 是的倍数 0.001 并满足 0.001\leq \sigma\leq 0.100.

读取输入后,重复以下过程直至 1000 次。 在 k第进程,首先选择位置 (qx_k, qy_k) 站立杆,并按以下格式将单行输出到标准输出。

qx_k qy_k

qx_k 和 qy_k 必须是满足以下条件的整数 qx_k^2+qy_k^2\leq R^2。 如果您指定范围之外的点,您将得到 WA。 输出后面必须有一个新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE.

然后,有关杆所发生情况的信息将在标准输入的一行中给出,如下所示。

如果杆朝以下方向落下 \theta_k:

0 \theta_k

\theta_k 介于 0 和 2\pi 并四舍五入为 10 小数位。

如果杆保持站立并且你在坐标处找到宝藏 (x_k,y_k):

r_k x_k y_k

r_k is 2 如果找到的宝藏是最后一个,并且 1 否则。 不同宝藏之间的距离保证大于 2D,所以你不会同时找到多个宝藏。 当你找到所有宝藏后,你必须立即终止程序。 否则,任何后续查询都不会返回响应,因此提交可能会被判断为 TLE or RE.

示例

k 输出 输入
0
0.051
1
-449800796 341903569
0 4.2119508044
2
-302629026 250885846
0 4.7012310463
3
-132900000 -988000000
1 -132899921 -988157302
\vdots

评分

如果你没能找到里面的所有宝藏 1000 查询,测试用例的分数为 100F,其中 F 是您找到的宝藏数量。 如果你找到了所有的宝藏 Q(\leq 1000) 查询,测试用例的分数为 10000-5Q。 如果您还没有找到所有宝藏且查询次数小于 1000,提交的作品将被判定为 WA.

有200个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。

输入生成

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。 \sigma 是由生成的 0.001\times \mathrm{rand}(1,100)。 坐标 p_0\cdots,p_{49} of 50 埋藏宝藏的生成方式如下。

  1. 生成坐标 p_i=(px_i,py_i) 的 i- 第一个埋藏的宝藏在满足条件的整数中均匀随机 px_i^2+py_i^2\leq R^2.
  2. 虽然已经生成了 p_j (j<i) 的欧几里得距离 p_i 小于或等于 2D,重新生成 p_i.

工具(输入生成器、可视化工具和本地测试器)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。

工具使用的输入/输出文件规范

提供给本地测试器的输入文件具有以下格式。

\sigma
px_0 py_0
\vdots
px_{49} py_{49}
\mathrm{seed}

最后 \mathrm{seed} 是用于生成下降方向的随机种子值。 由于方向取决于杆的位置,因此输入文件仅包含随机种子值。

本地测试器将程序的输出直接写入输出文件。您的程序可能会输出以以下内容开头的注释行 #。 可视化工具显示带有相应查询的注释行,这对于调试和分析可能很有用。 由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。

以下开头的注释行在可视化工具中具有特殊含义。

  • #r:当您不使用提供的本地测试器时,通过以以下形式输出给解决方案程序的响应字符串 #r 0 0.0123456789,您可以向可视化工具提供信息。提供的本地测试器也会自动插入这些注释行。
  • #c:通过按以下格式输出,可以标记一个点 (x, y) RGB 颜色 (r,g,b) (0\leq r,g,b\leq 255)。例如,您可以利用此功能来检查埋藏宝藏的可能位置。标记每回合都会被删除,因此如有必要,每回合都将其输出。
#c x y r g b