AT_ahc057_a [AHC057A] Molecules

AtCoder研究所では、新しい分子の開発を行っている。 天才化学者である髙橋くんは、動き回る原子同士を好きなタイミングで結合させて、分子を作ることができる。 ただし、原子を結合するには距離に応じてエネルギーを消費してしまうので、できるだけ少ないエネルギーで決められた数の分子を作りたい。

在一个二维平面上，定义 $0 \leq x < L = 10^5$，$0 \leq y < L = 10^5$。该平面具有环面结构（[toroidal](https://en.wikipedia.org/wiki/Torus)），即左、右边界（$x = 0$ 和 $x = L$），以及上、下边界（$y = 0$ 和 $y = L$）都是连通的。任何坐标超出此范围时，都通过分别对 $x$ 和 $y$ 取 $L$ 的余数来归一化到 $0 \leq x, y < L$。例如，从 $(10000, 90000)$ 处移动 $(-20000, 30000)$ 后的位置为 $(90000, 20000)$。 在此平面上有 $N$ 个点。在时间 $t = 0$ 时，第 $i$ 个点（$0 \leq i < N$）的初始位置为 $(x_i, y_i)$（$0 \leq x_i, y_i < L$），初始速度为 $(vx_i, vy_i)$（$-100 \leq vx_i, vy_i \leq 100$）。在初始状态时，每个点都形成了独立的连通分量。 对于时间 $t = 0, 1, \ldots, T-1$，每一时刻依次进行以下两个阶段的处理：**1. 结合阶段（Bonding Phase）** 和 **2. 移动阶段（Movement Phase）**。 **1. 结合阶段（Bonding Phase）** 在时间 $t$ 时，可以**结合**属于不同连通分量的两个点。同一时间步内可以执行多次结合。 设点 $i$ 在时间 $t$ 的位置为 $(x_i, y_i)$，点 $j$ 在时间 $t$ 的位置为 $(x_j, y_j)$。将点 $i$ 和点 $j$ 结合在一起的**结合代价** $D$ 按照以下距离公式计算： \[ D = \mathrm{round}\left( \sqrt{ \bigl(\min(L - \Delta x,\, \Delta x)\bigr)^2 + \bigl(\min(L - \Delta y,\, \Delta y)\bigr)^2 } \right) \] \[ \Delta x = |x_i - x_j|,\quad \Delta y = |y_i - y_j| \] 当两个点结合后，其所在的连通分量的速度会根据动量守恒律进行更新。假如结合前，点 $i$ 属于连通分量 $A$ 且其速度为 $(vx_A, vy_A)$，点 $j$ 属于连通分量 $B$ 且其速度为 $(vx_B, vy_B)$。则结合后，所有属于 $A$ 和 $B$ 的点的速度 $(vx_{\text{new}}, vy_{\text{new}})$ 按如下方式更新： \[ (vx_{\text{new}}, vy_{\text{new}}) = \left( \frac{|A| \times vx_A + |B| \times vx_B}{|A| + |B|}, \frac{|A| \times vy_A + |B| \times vy_B}{|A| + |B|} \right) \] 其中，$|A|$ 和 $|B|$ 表示连通分量 $A$ 和 $B$ 的点数。结合后，所有属于该连通分量的点速度都将变为**相同的速度**。结合操作不会导致点的位置发生变化，并且同一时间步内结合的顺序不会影响最终的位置、结合代价或连通分量的速度。 坐标和速度可能变为小数，但所有计算均使用 double 精度浮点数进行。 **2. 移动阶段（Movement Phase）** 每个连通分量的所有点的位置同时进行更新。设第 $i$ 个点在时间 $t$ 的位置为 $(x_i, y_i)$，其所在连通分量的速度为 $(vx_i, vy_i)$，则在时间 $t+1$ 时点 $i$ 的新位置 $(x_i', y_i')$ 按如下公式更新： \[ (x_i', y_i') = \bigl((x_i + vx_i) \bmod L,\, (y_i + vy_i) \bmod L\bigr) \] 请规划结合操作，使得在时间 $T$ 时，连通分量的个数**恰好为 $M$**，且每个连通分量的大小**恰好为 $K$**，并最小化**总结合代价 $D$**。 #### 结合与移动示意 >  > > 上图演示了三个点结合成同一个连通分量的例子。首先将左下和右下的两个点结合，其速度变为向上移动。接着再与右上向右移动的点结合，速度变为右上移动。

输入通过标准输入给出，格式如下： >$N\ T\ M\ K\ L\ x_0\ y_0\ vx_0\ vy_0\ x_1\ y_1\ vx_1\ vy_1\ \vdots\ x_{N-1}\ y_{N-1}\ vx_{N-1}\ vy_{N-1}$ - 点的总数 $N = 300$。 - 总步数 $T = 1000$。 - 目标连通分量数 $M = 10$。 - 每个连通分量目标大小 $K = 30$。 - 空间的边长 $L = 10^5$。 - $(x_i, y_i)$ 表示第 $i$ 个点的初始位置，$0 \leq x_i, y_i < L$，均为整数。 - $(vx_i, vy_i)$ 表示第 $i$ 个点的初始速度，$-100 \leq vx_i, vy_i \leq 100$，均为整数。

输出恰好 $N - M$ 行，每行包含三个整数，表示在时间 $t$ 时，将第 $i$ 个点和第 $j$ 个点进行结合。输出顺序任意，判题时会按时间 $t$ 升序处理。 >$t\ i\ j$ 输出需满足以下要求： - $0 \leq t < T$ - $0 \leq i, j < N$ 且 $i \neq j$

### 评分方式 设所有结合操作的总代价为 $D_{\text{sum}}$，单个测试点的得分按下式计算，分数越高越好。 \[ \mathrm{Score} = \mathrm{round}\!\left(10^{6} \times \log_2\!\left( \frac{L \times (N - M)}{D_{\text{sum}} + 1} \right)\right) \] 如遇以下情况，判题结果为 WA： - 输出不合法 - 在时间 $T$ 时，连通分量数不是**恰好为 $M$**，或连通分量的大小不是**恰好为 $K$** - 如果指定结合的两个点已经属于同一连通分量 共有 $150$ 个测试点，提交的总得分为所有测试点得分之和。如果输出不合法或某些测试点超时，整个提交将被判为 WA 或 TLE，得分为零。比赛期间以历史最高分作为最终排名，赛后不再系统测试；分数相同的情况下，以得分并列排序，与提交时间无关。 ### 输入生成方式 $\mathrm{rand}(L, U)$：在 $L$ 到 $U$（闭区间）内等概率随机生成一个整数。 **初始位置的生成** 对于每个点 $i$，独立均匀生成 $x_i = \mathrm{rand}(0, L-1)$，$y_i = \mathrm{rand}(0, L-1)$。 **初始速度的生成** 对于每个点 $i$，独立均匀生成 $vx_i = \mathrm{rand}(-100, 100)$，$vy_i = \mathrm{rand}(-100, 100)$。 ### 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc057/BJTm8xSg.html?lang=zh)：动画效果较本地版更为强大。 - [本地版](https://img.atcoder.jp/ahc057/BJTm8xSg.zip)：需有 [Rust](https://www.rust-lang.org/) 语言编译环境。 - [Windows 预编译版](https://img.atcoder.jp/ahc057/BJTm8xSg_windows.zip)：如不熟悉 Rust 编译环境，可使用此工具。 请注意，比赛期间禁止分享可视化结果或讨论解题思路与方案。 由 ChatGPT 5 翻译