P16373 [IATI 2026] Vision

企业号星舰（由 Sashka 担任新任舰长）正在宇宙中航行，宇宙是一个无限的二维扇区网格。在每个扇区 $(X, Y)$（$X$ 是行号（向下方向递增），$Y$ 是列号（向右方向递增）） 中，都有一个视觉强度为 $V_{X, Y}$ 的信标。当星舰位于该扇区时，会利用信标扫描所有满足 $X - V_{X, Y} \leq X' \leq X + V_{X, Y}$ 且 $Y - V_{X, Y} \leq Y' \leq Y + V_{X, Y}$ 的扇区 $(X', Y')$。因此，可见的扇区构成一个边长为 $2V_{X, Y} + 1$ 的正方形。对于其中的每个扇区，唯一能看到的信息就是该处信标的视觉强度，即 $V_{X', Y'}$（这是因为信标同时充当发射器和接收器）。扫描结束后，星舰会传送到这些可见扇区中的一个，因为信标同时也充当传送器。 不幸的是，信标有一个严重的缺陷：它们可能会翻转扫描结果的 $X$ 轴，或 $Y$ 轴，或两者同时翻转（即共有 $4$ 种可能的扫描取向）。注意，星舰会利用这个可能被翻转过的扫描结果来决定传送到哪个扇区，而传送过程也使用相同的取向，例如，若 $Y$ 轴被翻转，而星舰在扫描结果中向左侧（即 $Y$ 递减的方向）传送，实际上它将会向右移动。这意味着星舰确实会传送到扫描结果中所选的扇区。 此外，星舰没有任何记忆，因此它决定传送到哪里的策略必须**仅依赖**于信标产生的扫描结果。而且，星舰的策略必须是**确定性的**——若得到相同的扫描结果，它必须选择传送到扫描结果中的同一个扇区。 星舰起始于未知坐标，并且必须始终（无论它从哪里开始，也无论它遇到的扫描取向是什么）能够沿着 $X$ 和 $Y$ 增加的方向行进到任意远处（我们可以要求它最终到达某个扇区 $(X, Y)$ 使得 $X, Y \geq 10^{100}$）。然而，为了让这成为可能，星舰的行进策略和全宇宙视觉强度的布局都至关重要。 这就是你发挥作用的地方——你需要设计一个大小为 $N \times M$ 的矩形视觉强度**图案** $P$，该图案将在全宇宙中无限重复：$V_{X, Y} = P_{X \bmod N, Y \bmod M}$。你还需要为星舰设计行进策略，即一个函数，它接收信标产生的扫描结果，并选择接下来传送到这些扇区中的哪一个。 由于视觉强度更高的信标价格昂贵，你的目标是给出一个有效的解，同时尽可能降低你图案中的平均视觉强度，即 $P$ 中元素的平均值。 因为这个问题看起来相当有挑战性，你决定先从一个练习问题入手：在一维情况下的相同问题。在这个更简单的问题中，我们丢弃 $X$ 维度，只使用 $Y$ 维度。于是，你的图案只是一个长度为 $M$ 的序列，其重复方式为：$V_Y = P_{Y \bmod M}$。信标产生的扫描结果也仅仅是长度为 $2V_Y + 1$ 的序列（包含满足 $Y - V_{Y} \leq Y' \leq Y + V_{Y}$ 的所有扇区 $Y'$）。这里，扫描结果只有 $2$ 种可能的取向（正常或翻转），并且星舰必须能够到达 $Y \geq 10^{100}$。 你在一维情况和二维情况下的解将**分开评分**，并且即使其中一个情况没有有效解，你仍然可能从另一个情况获得分数。 ### 实现细节 你需要实现 4 个函数：`getVisionPattern1d`、`getMove1d`、`getVisionPattern2d` 和 `getMove2d`。前两个用于一维情况，后两个用于二维情况。在任意一次测试中，只会调用这两对函数中的一对，但为了程序合法（能够编译），你必须实现全部 4 个函数（即使其中一对的实现为空）。 ```cpp std::vector getVisionPattern1d() ``` 若该测试针对一维情况，此函数将被调用一次。它必须返回一个长度为 $M$ 的序列 $P$ —— 即将被重复的一维视觉强度图案。$M$ 及 $P$ 中的所有元素都必须在 $1$ 到 $60$ 之间。 ```cpp int getMove1d(std::vector v) ``` 若该测试针对一维情况，该函数将针对每种可能的扫描结果各调用一次。它接收一个由信标产生的扫描结果，其形式为一个长度为 $2V + 1$ 的序列（其中 $V$ 是序列中心扇区中信标的视觉强度）。它必须返回星舰应传送到的扇区在序列中的下标 $T$，满足 $0 \leq T < 2V + 1$。 ```cpp std::vector getVisionPattern2d() ``` 若该测试针对二维情况，此函数将被调用一次。它必须返回一个大小为 $N \times M$ 的矩形表 $P$ —— 即将被重复的二维视觉强度图案。$N$、$M$ 及 $P$ 中的所有元素都必须在 $1$ 到 $60$ 之间。 ```cpp std::pair getMove2d(std::vector v) ``` 若该测试针对二维情况，该函数将针对每种可能的扫描结果各调用一次。它接收一个由信标产生的扫描结果，其形式为一个大小为 $(2V+1) \times (2V+1)$ 的正方形表（其中 $V$ 是正方形中心扇区中信标的视觉强度）。它必须返回星舰应传送到的扇区在表中的行、列下标对 $(S, T)$，满足 $0 \leq S, T < 2V + 1$。 对于测试中给定的维度 $D$（$1$ 或 $2$），评测程序将检查你的程序是否产生了有效的图案——即是否对所有可能的扫描结果作出了合法的传送选择，以及你的解是否在任意起始坐标和任意扫描取向序列下都能正常工作。

样例评测程序首先读入一个整数 $D$。然后它将调用你的全部相关函数：首先获取图案 $P$，然后缓存所有传送选择。之后，它将启动控制台交互，要求输入星舰的起始坐标。接着，它会打印当前状态：坐标和“原始”（未经翻转的）扫描结果。然后，它会要求输入本次使用的扫描取向（$0$ 表示无翻转，$1$ 表示翻转 $Y$ 轴，$2$ 表示翻转 $X$ 轴，$3$ 表示两轴都翻转）。最后，它会打印在所给取向下的扫描结果，以及星舰所选择的移动。星舰将被移动，此过程将不断重复。请注意，样例评测程序不会自动验证你的解是否正确。

无

### 样例图案 假设你的程序返回如下 $N=3$、$M=2$ 的图案： $$ \left[ \begin{array}{c c} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{array} \right] $$ 现在，我们来考察位于扇区 $(0, 1)$、视觉强度为 $2$ 的信标可能产生的扫描结果。该图案上有 $4$ 种可能的取向（其中一些会产生相同的扫描结果）： $$ \begin{array}{cc} \text{取向 $0$：无翻转} & \text{取向 $1$：$Y$ 轴翻转} \\ \left[ \begin{array}{ccccc} 4 & 3 & 4 & 3 & 4 \\ 6 & 5 & 6 & 5 & 6 \\ 2 & 1 & 2 & 1 & 2 \\ 4 & 3 & 4 & 3 & 4 \\ 6 & 5 & 6 & 5 & 6 \end{array} \right] & \left[ \begin{array}{ccccc} 4 & 3 & 4 & 3 & 4 \\ 6 & 5 & 6 & 5 & 6 \\ 2 & 1 & 2 & 1 & 2 \\ 4 & 3 & 4 & 3 & 4 \\ 6 & 5 & 6 & 5 & 6 \end{array} \right] \\ \\ \text{取向 $2$：$X$ 轴翻转} & \text{取向 $3$：两轴均翻转} \\ \left[ \begin{array}{ccccc} 6 & 5 & 6 & 5 & 6 \\ 4 & 3 & 4 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 \\ 6 & 5 & 6 & 5 & 6 \\ 4 & 3 & 4 & 3 & 4 \end{array} \right] & \left[ \begin{array}{ccccc} 6 & 5 & 6 & 5 & 6 \\ 4 & 3 & 4 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 \\ 6 & 5 & 6 & 5 & 6 \\ 4 & 3 & 4 & 3 & 4 \end{array} \right] \end{array} $$ 由于取向 $0$ 和 $1$ 产生的扫描结果相同，而星舰的策略又是确定性的，因此评测程序只会对它们调用一次 `getMove2d`。假设你的程序对该扫描结果返回移动 $(0, 1)$。在取向 $0$ 下，这意味着向左移动 $1$ 格并向上移动 $2$ 格；而在取向 $1$ 下，则意味着向右移动 $1$ 格并向上移动 $2$ 格。 ### 数据范围 - $1 \leq D \leq 2$ - $1 \leq N, M, V_{X, Y}, V_Y \leq 60$ ### 子任务与评分 | 子任务 | 分数 | D | $A^*$ | |:-------:|:------:|:-:|:-------:| | $1$ | $24$ | $1$ | $1.5$ | | $2$ | $76$ | $2$ | $1.125$ | 你在给定子任务上的得分（如果你的解在该子任务上正确）取决于你为它设计的图案 $P$ 的平均视觉强度。令该值为 $A$，子任务的目标值为 $A^*$。你的得分（占该子任务分数的比例）将为： $$1 - {\left(1 - \frac{A^* - 1}{\max{\left(A, A^*\right)} - 1}\right)}^{0.8}$$ 翻译由 DeepSeek V4 Pro 完成