问题陈述
有一个岛,由 N\times N 方块。 让 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 据算命先生高桥先生说,有 M 岛下有未勘探的油田。
每个油田都有一个相连的 多联骨牌 1×1正方形的边相连的形状,其形状和方位也是通过占卜预先知道的。然而,他们在岛上的确切位置仍然未知。 每个油田都完全包含在 N\times N 正方形,但多个油田可能重叠并共享同一个正方形。 对于每个 (i,j) 正方形,定义 石油储量 v(i,j) 为包含该正方形的油田数量。 最多重复以下三种操作 2 N^2 次。
- 选择一个方格并在该方格的地下钻探。的价值 v(i,j) 被揭露,产生 1 点成本。
- 选择一组 S 两个或更多方格并占卜这些方格中石油储量的总和 v(S)=\sum_{(i,j)\in S} v(i,j)。选择的方格数量越多,成本越低,选择 k 方块成本 1/\sqrt{k}。另一方面,占卜所得值的方差成比例增加 k。让 x 是从以下正态分布中采样的值,平均值为 \mu 和方差 \sigma^2,使用错误参数 \epsilon 提前给出。那么得到的值为 \max(0,\mathrm{round}(x)).
- 平均值 \mu = (k-v(S))\epsilon + v(S)(1-\epsilon)
- 方差 \sigma^2 = k\epsilon (1-\epsilon)
- 猜测所有正方形 v(i,j)>0。如果答案正确,则操作结束;如果不正确,则操作继续,成本为 1。
请识别所有方块,使得 v(i,j)>0 以尽可能低的成本。
评分
如果您成功识别出所有方块,使得 v(i,j)>0 在指定的操作次数内,您获得的绝对分数为 \mathrm{round}(10^6\times \max(C, 1/N)),其中 C 是您支付的费用总和。 如果失败,您将获得绝对分数 10^9。 绝对分数越低越好。
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。
最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:3000。我们将发布 种子.txt (sha256=45933552af3c557ff53d4e1397ef9fe10cedea89f10fe8140ceb489569dacea2) 比赛结束后。
关于相关评价体系
在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入和输出
一、岛屿大小 N, 油田数量 M,错误参数 \epsilon,每个油田的形状由标准输入以以下格式给出。
N M \epsilon
d_1 i_{1,1} j_{1,1} \cdots i_{1,d_1} j_{1,d_1}
\vdots
d_M i_{M,1} j_{M,1} \cdots i_{M,d_M} j_{M,d_M}
- 岛屿尺寸 N 满足 10\leq N\leq 20.
- 油田数量 M 满足 2\leq M\leq 20.
- 错误参数 \epsilon 满足 0.01\leq \epsilon\leq 0.2 是的倍数 0.01.
- 的 d_k 表示面积 k第油田并满足 4\leq d_k\leq N^2/M。随后的 d_k 坐标 (i_{k,1},j_{k,1}),\cdots,(i_{k,d_k},j_{k,d_k}) 表示平移后多格骨牌中每个方格的坐标,以便顶部和左侧坐标都是 0。例如,一个 2\times 2 方形多骨牌表示为
4 0 0 0 1 1 0 1 1. - 多个油田可能具有完全相同的形状。
读完以上信息后,最多重复以下过程 2 N^2 次。 在每次迭代中,根据要执行的操作类型执行以下操作。
如果选择一格 (i, j) 并在该广场地下钻探,按以下格式输出到标准输出。
q 1 i j
输出后,值为 v(i,j) 在标准输入的一行中给出。 您可以再次钻一个已经钻过的正方形,尽管它没有特别的优势。
如果您选择一套 S=\{(i_1,j_1),\cdots,(i_d,j_d)\} of d (\geq 2) 方格与神圣 v(S),按以下格式输出到标准输出。
q d i_1 j_1 \cdots i_d j_d
这里,每个坐标 (i_k,j_k) 必须与其他不同。如果集合多次包含相同坐标,则判断为 WA。 输出后,一个 近似值 的值 v(S) 在标准输入的一行中给出。
如果你能猜出所有的方块 v(i,j)>0,让 S=\{(i_1,j_1),\cdots,(i_d,j_d)\} 是您确定拥有的一组正方形 v(i,j)>0 并按以下格式输出到标准输出。
a d i_1 j_1 \cdots i_d j_d
这里,输出设置 S 必须包括通过第一次作业在地下钻探已发现具有石油储量的所有方格。
各坐标 (i_k,j_k) 必须与其他不同。如果集合多次包含相同坐标,则判断为 WA。
输出后,
如果猜测的集合正确,则 1 将在标准输入的一行中给出,并且 0 如果是错误的。
如果
返回 1 ,不处理后续查询,应立即终止程序的执行。
如果
返回 0 ,您可以执行最多限制的附加操作,然后重试。
输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE.
您的程序可能会输出以以下开头的注释行 #。网页版可视化工具会在相应的时间显示注释行,这可能有助于调试和分析。由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。
评论中,以 #c 经过特殊处理,可以以以下形式输出 #c i j color 让可视化工具任意更改每个方块的颜色。例如,输出 #c 0 1 red or #c 0 1 #ff0000 将改变颜色 (0,1) 为红色。
示例
| t | 输出 | 输入 |
|---|---|---|
| 先前信息 | 15 2 0.01 19 0 3 1 1 1 3 1 6 2 0 2 1 2 2 2 3 2 4 2 5 2 6 3 1 3 2 3 3 3 4 3 5 4 1 4 2 4 4 19 0 1 1 1 2 1 3 1 3 2 3 3 3 4 4 1 4 2 5 0 5 1 5 2 5 3 6 1 6 2 6 3 7 1 7 3 8 3 |
|
| 1 | q 25 0 0 0 1 0 2 ... 4 4 |
8 |
| 2 | q 1 0 0 |
0 |
| \vdots | ||
| 185 | a 38 2 3 2 10 3 1 ... 10 12 |
1 |
示例解决方案
这是 Python 中的示例解决方案。 该程序按顺序钻取所有方格,并输出最终实际产出石油的方格。
# read prior information
line = input().split()
N = int(line[0])
M = int(line[1])
eps = float(line[2])
fields = []
for _ in range(M):
line = input().split()
ps = []
for i in range(int(line[0])):
ps.append((int(line[2*i+1]), int(line[2*i+2])))
fields.append(ps)
# drill every square
has_oil = []
for i in range(N):
for j in range(N):
print("q 1 {} {}".format(i, j))
resp = input()
if resp != "0":
has_oil.append((i, j))
print("a {} {}".format(len(has_oil), ' '.join(map(lambda x: "{} {}".format(x[0], x[1]), has_oil))))
resp = input()
assert resp == "1"
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
岛屿尺寸 N 是由生成的 \mathrm{rand}(10,20)。 油田数量 M 是由生成的 \mathrm{rand}(2,\mathrm{floor}(N^2/20))。 错误参数 \epsilon 是由生成的 0.01\times \mathrm{rand}(1,20).
要生成每个油田的形状,需要两个参数 a,d 首先生成如下。
- a=\mathrm{floor}(\mathrm{rand}(\mathrm{floor}(N^2/5),\mathrm{floor(N^2/2)})/M)
- d=\mathrm{rand}(0,a-4)
对于每个 k=1,\cdots,M,形状 k第油田生成如下。 首先,油田规模由下式生成: s_k=\mathrm{rand}(a-d,a+d)。 开始于 S_k=\{(\mathrm{floor}(N/2),\mathrm{floor}(N/2))\},一次添加一个方格,从邻近的一组方格中均匀随机选择 S_k,直到大小 S_k 变为 s_k。 最后翻译一下 S_k 这样最小 i 坐标和最小值 j 中包含的方块的坐标 S_k 都是 0.
生成每个油田的形状后,岛内每个油田的位置是随机统一选择的,确保它们不会超出岛屿边界。 换句话说,给定最大 i 组成油田的方格之间的坐标为 i_{\text{max}},以及最大 j 坐标为 j_{\text{max}},生成 d_i=\mathrm{rand}(0,N-i_{\text{max}}-1) 和 d_j=\mathrm{rand}(0,N-j_{\text{max}}-1)。然后,将油田定位在移动了 (d_i, d_j).
工具(输入生成器、本地测试器和可视化器)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
工具使用的输入/输出文件规范
提供给本地测试器的输入文件包括以下格式的附加信息,附加到提供给解决方案程序的先验信息的末尾。
di_1 dj_1
\vdots
di_M dj_M
v_{0,0} \cdots v_{0,N-1}
\vdots
v_{N-1,0} \cdots v_{N-1,N-1}
e_1
\vdots
e_{2N^2}
- (di_k,dj_k) 表示坐标 位于 k第油田。也就是说,最小 i- 属于该油田的正方形的坐标是 di_k 和最小值 j- 坐标是 dj_k.
- 每个 v_{i,j} 代表石油储量 广场的 v(i,j) 广场的 (i,j).
- 每个 e_k 是从标准正态分布中采样的值,用于计算结果的误差 k第一个查询。