← 返回题目列表

AtCoder · ahc022_a

A. 探索另一个空间

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

故事

人类发现了我们世界之外的另一个区域,称为 Another Space.
另一个空间由一个表示 L \times L 网格,形成一个环面。 这意味着从顶行向上移动一个方块将到达同一列的底行,这同样适用于左右移动。

要进入另一个空间,我们使用 虫洞.
有 N 虫洞,每个都是独立的,并将我们的世界与另一个空间的一个单元连接起来。 另一个空间中连接到 虫洞 被称为 退出单元格。 有 N 退出单元格 在另一个空间,并且每个 虫洞 对应一 退出单元格。 我们知道的立场 网格上的 退出单元格 。但我们不知道它们之间的具体对应关系 虫洞 和 退出单元格。我们想找到这封信。

X桑,一位伟大的科学家,想出了一个计划来估计 虫洞 和 退出单元格 使用以下步骤:

  1. X-san会在另一个空间的每个单元中放置一个空调装置,并为每个单元设置一个整数温度。
  2. X-san 将重复以下测量:
    • 选择一项 虫洞 并通过它进入另一个空间。
    • 在另一个空间内执行预定的运动,并在完成运动后测量电池的温度。

需要注意的是,由于测量设备的限制,测量的温度会存在误差。

设置温度时必须小心。空调机组可以维持每个单元内的温度,但如果相邻单元之间存在显着的温差,则会消耗大量的能量。
此外,测量异空间的温度也需要能量,测量的次数越多,移动的时间越长,需要的能量就越多。

作为出色的助手,你的任务是制定一个计划,让 X-san 能够估算出 虫洞 在另一个空间中以尽可能少的能量进行通信。 揭开其中的谜团 虫洞 通信并为人类的未来铺平道路。


问题陈述

存在一个 L \times L 网格,其中单元格位于 i- 第行 ( 0 \leq i \lt L )从顶部和 j- 第列 ( 0 \leq j \lt L ) 从左边开始表示为 (i, j)。 网格的顶部和底部以及左右边缘以环面形状连接。 换句话说, (0, j) 毗邻 (L-1, j) 垂直,以及 (i, 0) 毗邻 (i, L-1) 水平。 网格中的
有 N 退出单元格 ,它们的坐标表示为 (Y_0, X_0), (Y_1, X_1), \ldots, (Y_{N-1}, X_{N-1}).
存在一个排列 A=(A_0,A_1,\ldots,A_{N-1}) 的整数 0,1,\ldots,N-1。 这种排列表明,当输入 i-th 虫洞,将通过 A_i-th 退出单元格。 的价值观 A 是隐藏的,这个问题的目的是估计它们。

估算过程通过以下步骤实现: 放置, 测量,和 答案,按顺序执行。

放置

在 放置 步骤,分配一个整数值,范围为 0 to 1000 (含)到网格中的每个单元格。
为单元格分配的值 (i, j) 表示为 P_{i,j} (0 \leq P_{i,j} \leq 1000).
安置成本 计算为每个单元格及其所有方向(上、下、左、右)上的相邻单元格的指定值之间的差值的平方和。

安置成本 = \sum_{i=0}^{L-1} \sum_{j=0}^{L-1} ((P_{i,j} - P_{(i+1)\%L,j})^2 + (P_{i,j} - P_{i,(j+1)\%L})^2)

测量

执行以下操作 测量 0次或多次,但不超过10,000次:

  • 指定整数 i, y,和 x.
    • i 代表索引 虫洞.
  • 让 (Y_{A_i}, X_{A_i}) 是起始坐标。移动 y 细胞下降并且 x 单元格右侧 (Y_{A_i}, X_{A_i}),导致单元格 (r, c)。 如果 y or x 是负数,表示向上移动 |y| 单元格或向左移动 分别为 |x| 细胞。
    • 换句话说, r \equiv Y_{A_i}+y \pmod L, c \equiv X_{A_i}+x \pmod L (0 \leq r,c \lt L) .
    • 注意之间的对应关系 虫洞 和 退出单元格 未知,因此不清楚是哪个 退出单元格 开始运动。 (Y_{A_i}, X_{A_i}) 是未知值。
  • 让 f(\sigma) 是从均值正态分布中采样值的函数 0 和标准差 \sigma.
  • 测量值如下 \mathrm{max}(0, \mathrm{min}(1000, \mathrm{round}(P_{r,c} + f(S)))).
    • 在这里, S 是作为输入给出的正整数
    • 请注意,真实值 P_{r, c} 未知。

每个 测量 产生的费用为 100 * (10 + |y| + |x|).
所有费用的总和 测量 被称为 测量成本.
允许执行 测量 重复在同一位置。每个 测量 每次都会提供新的采样值。

答案

输出估计值 A as E_0, E_1, \ldots , E_{N-1}.


评分

让 W 表示错误答案的数量 N,即 i 其中 A_i \ne E_i,则评价值如下。
评价值= \lceil (10^{14} * 0.8^W / (\mathrm{placement\_cost} + \mathrm{measurement\_cost} + 10^{5})) \rceil
在这里, \lceil x \rceil 表示大于或等于的最小整数 x.


对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}),其中 YOUR 是您的评估值,MAX 是在该测试用例上获得的所有竞争对手中的最大评估值。提交的分数是相对分数的总和。

最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您提交的测试用例产生非法输出或超出了某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MAX 计算之外。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:3000
    • 对于系统测试,每个系统将有 100 个数据输入 S.
    • 我们将发布 种子.txt (sha256=2154215b63e063812cf2bb0ee2370c5193ae4682a3f7ce260e82a52a07663206) 比赛结束后。

关于相关评价体系

在临时/系统测试中,将仅使用收到除以下结果之外的最后提交的结果来计算排名 CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MAX。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的评估值的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或确保有足够的执行时间。


输入和输出

注意:此问题是交互式的。阅读下面的解释,并与判断程序进行相应的沟通。

首先,问题参数将从标准输入以以下格式提供。

\(
L ~ N ~ S \\
Y_0 ~ X_0 \\
\vdots \\
Y_{N-1} ~ X_{N-1} \)
  • 第一行有3个整数 L,N,S 以空格分隔。
    • L 表示网格的大小,满足 10 \le L \le 50.
    • N 代表数量 退出单元格 并满足 60 \le N \le 100.
    • S 表示计算测量值时使用的标准偏差,满足 S \in \{i^2 | 1 \leq i \leq 30\}。在这里, i 是一个整数。
  • 以下 N 行包含的坐标 退出单元格.
    • 每行包含两个以空格分隔的整数 Y_i 和 X_i,代表坐标 i-th 退出单元格 is (Y_i, X_i).
    • 整数满足 0 \leq Y_i \lt L, 0 \leq X_i \lt L.
    • 坐标彼此不同,并按字典顺序给出。

收到上述输入后,执行 放置 步骤。输出每个单元格的值 P_{i, j} 按以下格式转换为标准输出。

\(
P_{0,0} ~ \cdots ~ P_{0,L-1} \\
\vdots \\
P_{L-1,0} ~ \cdots ~ P_{L-1,L-1}\)
  • 输出 L 行,每行包含 L 由空格分隔的整数。
  • P_{i, j} 必须是整数并且满足 0 \le P_{i, j} \le 1000.
  • 如果不满足这些条件,结果将为 WA.
  • 输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交内容可能会被判定为 TLE.

接下来,继续 测量 步骤。可以重复测量 0 to 10000 次。
输出相关参数 测量 按以下格式步骤到标准输出:

\(
i ~ y ~ x\)
  • 在一行中,输出三个整数 i,y,x 以空格分隔。
    • i 代表索引 虫洞.
    • y, x 表示从 退出单元格 对应于 i-th 虫洞.
    • i, y, x 必须满足 0 \leq i \lt N, -L \lt y, x \lt L。否则,结果将是 WA.
  • 输出后面必须跟有新行,并且您必须刷新标准输出。否则,提交的内容可能会被判定为 TLE.

然后,从 测量 将从标准输入中以以下格式提供:

\(
m\)
  • 在一行中,有一个整数 m.
    • m 表示测量值计算如下 \mathrm{max}(0, \mathrm{min}(1000, \mathrm{round}(P_{r,c} + f(S)))).
  • 如果输出无效, m 将是 -1。在这种情况下,请终止该程序。如果不这样做,结果是不确定的。
  • 如果值 P 期间输出 放置 步骤无效, -1 将在第一次期间返回 测量

完成时 测量 并提供答案,输出之间的对应关系 虫洞 和 退出单元格 以以下格式输出到标准输出:

\(
-1 ~ -1 ~ -1 \\
E_{0} \\
\vdots \\
E_{N-1}\)
  • 第一行,输出三个整数 -1 ~ -1 ~ -1 以空格分隔。
    • 这代表了结束 测量
  • 关于以下内容 N 行,输出的值 E,估计值 A,以换行符分隔。
    • E_{i} 表示 i-th 虫洞 估计对应于 E_{i}-th 退出单元格
    • If E 不满足 0 \le E_{i} \lt N,结果将是 WA.
    • 您可以多次输出相同的数字。
  • 输出后面必须跟有新行,并且您必须刷新标准输出。否则,提交的内容可能会被判定为 TLE.

输入生成

  • L, N, S 是通过从所有可能值中均匀随机选择一个值来生成的。
  • Y_{i}, X_{i} 是通过从 L \times L 网格并按字典顺序对它们进行排序
  • A_{i} 是通过从整数的所有可能排列中均匀随机选择一种排列来生成的 0,1,\ldots,N-1

工具

请注意,在比赛结束之前禁止共享可视化结果。

工具中使用的输入格式

本地测试器的输入文件使用以下格式。

\(
L ~ N ~ S \\
Y_0 ~ X_0 \\
\vdots \\
Y_{N-1} ~ X_{N-1} \\
A_{0} \\
\vdots \\
A_{N-1} \\
f_{0} \\
\vdots \\
f_{9999}\)

f_{i} 表示一个整数,表示与 的值相加的误差 P 在 i第一次测量。

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


I/O 示例

输入 输出 说明
3 3 1
0 0
0 1
2 1
请注意,此输入用于解释目的,因此不满足输入的所有限制。
有 退出单元格 at (0,0), (0,1),和 (2,1) 在 3 \times 3 网格。
4 1 2
1 2 1
2 9 2
作为初始输出,执行 放置 步骤。设置值 P_{i, j} 对应于每个单元格。
0 0 0
接下来,继续 测量 步骤。 在这个 测量,第 0 个 指定了 虫洞 ,并且没有从 退出单元格.
8
测量值 8 。
1 1 1
如下 测量,指定第 1 个 虫洞 并定位向下移动获得的位置 1 单元格和右侧 1 单元格 退出单元格.
1
测量值 1 。
2 1 1
执行相同的操作 测量 作为第二个的前一个 再次获得 虫洞.
1
测量值 1 。
-1 -1 -1
2
0
0
完成 测量 并提供 答案.
第 0 个 虫洞 估计对应第2个 退出单元格 位于 (2, 1)。 第一和第二 虫洞 无法确定,因此两者都对应于第 0 个 退出单元格.