AT_ahc048_a [AHC048A] Mixing on the Palette

高橋画伯は、新作の水彩画シリーズに取り組んでいる。 彼の作品は繊細な色使いが評価されており、色の調合には特にこだわっている。 あなたは高橋画伯のアシスタントとして、彼が求める色をその場で調合して提供するという重要な役目を担っている。 使用する絵の具は高価であるため、出来るだけ無駄なく色を作ることが求められる。 幸い、これから必要となる色のリストが事前に渡されている。 できるだけ正確に、かつできるだけ少ない無駄でそれらの色を順番通りに作成してほしい。

[problemUrl]: https://atcoder.jp/contests/ahc048/tasks/ahc048_a 颜料的颜色用青色（$C$）、品红（$M$）、黄色（$Y$）组成的三维向量 $(C,\ M,\ Y)$ 表示。这里，$0\leq C,\ M,\ Y\leq 1$。将颜色为 $p_1=(C_1,\ M_1,\ Y_1)$ 的颜料 $v_1$ 克，与颜色为 $p_2=(C_2,\ M_2,\ Y_2)$ 的颜料 $v_2$ 克混合时，会得到颜色为 $\frac{v_1\cdot p_1 + v_2\cdot p_2}{v_1 + v_2}$ 的颜料 $v_1 + v_2$ 克。 v₁ = 4 p₁ = (1, 0, 0) + v₂ = 6 p₂ = (0, 1, 0) = v₁ + v₂ = 10 p = (0.4, 0.6, 0) 你拥有 $K$ 种管装颜料，第 $i$ 支管的颜色为 $(C^{\mathrm{own}}_i,\ M^{\mathrm{own}}_i,\ Y^{\mathrm{own}}_i)$。每从一支管中取出 1 克颜料，需要花费 $D$ 的成本。你需要用这些管装颜料，依次调配出 $H$ 种颜色，每种各 1 克，并交给画家。第 $i$ 次需要调配的颜色为 $(C^{\mathrm{target}}_i,\ M^{\mathrm{target}}_i,\ Y^{\mathrm{target}}_i)$。调配顺序是固定的，不能更改。 调色用的调色板由 $N\times N$ 的格状格子组成。左上角格子的坐标为 $(0,\ 0)$，向下为 $i$，向右为 $j$，坐标为 $(i,\ j)$。 每个格子与上下左右相邻格子之间有可开合的隔板。这些隔板的初始状态可以自由设置。 当相邻格子之间的隔板打开时，这些格子称为**连通**。通过连通的格子可以到达的格子集合称为**井（well）**。通过隔板的开合，可以将多个井合并，或将一个井分割成多个井。 每个井最多只能放入一种颜色的颜料，且一个包含 $k$ 个格子的井最多能放 $k$ 克颜料。初始时所有井中都没有颜料。 你最多可以进行 $T$ 回合以下操作： 1. 任意选择一个格子和一支管，从该管中取 1 克颜料倒入该格子所在的井。若井的剩余容量为 $w$，则实际混入的是 $\min(w, 1)$ 克，其余 $1-\min(w, 1)$ 克立即废弃。 2. 任意选择一个格子，从该格子所在的井中取出 1 克颜料交给画家。若该井中颜料不足 1 克，则不能选择该格子。 3. 任意选择一个格子，从该格子所在的井中取出 1 克颜料并废弃。若不足 1 克，则全部废弃。 4. 选择相邻的两个格子 $s,\ t$，对它们之间的隔板进行开合操作。 - 若隔板打开导致两个井合并，颜料会混合成一种颜色。 - 若隔板关闭导致一个井分裂为两个，颜料按容量比例分配。即，分割前颜料量为 $v$，$s$ 侧容量为 $v_s$，$t$ 侧容量为 $v_t$，则 $s$ 侧剩余颜料为 $v\times\frac{v_s}{v_s+v_t}$，$t$ 侧为 $v\times\frac{v_t}{v_s+v_t}$。 操作 2 必须**恰好进行 $H$ 次**。少于或多于 $H$ 次都会判为 WA。 #### 关于计算误差 由于颜料量为分数值，操作 2 中“1 克以上”的判定难以精确。因此，评测程序用双精度浮点数（double）管理颜料量，操作 2 的可行性及取出量按内部值 $v$（克）如下处理： - **操作可行性判定** - 若 $v < 1 - 10^{-6}$，视为“少于 1 克”，不能执行操作 2。 - 若 $v \geq 1 - 10^{-6}$，视为“1 克以上”，可执行操作 2。 - **取出量的决定** - 若 $v \geq 1$，取出恰好 1 克。 - 若 $1 - 10^{-6} \leq v < 1$，则取出井中所有颜料。 此外，配布工具的实现与评测程序**完全一致**。

输入通过标准输入按以下格式给出。 > $N$ $K$ $H$ $T$ $D$ $C_0^{\mathrm{own}}$ $M_0^{\mathrm{own}}$ $Y_0^{\mathrm{own}}$ > $\vdots$ > $C_{K-1}^{\mathrm{own}}$ $M_{K-1}^{\mathrm{own}}$ $Y_{K-1}^{\mathrm{own}}$ > $C_0^{\mathrm{target}}$ $M_0^{\mathrm{target}}$ $Y_0^{\mathrm{target}}$ > $\vdots$ > $C_{H-1}^{\mathrm{target}}$ $M_{H-1}^{\mathrm{target}}$ $Y_{H-1}^{\mathrm{target}}$ - 调色板大小 $N$ 在所有测试用例中均为 $N=20$。 - 管装颜料种类数 $K$ 满足 $4\leq K\leq 20$。 - 需要调配的颜色数 $H$ 在所有测试用例中均为 $H=1000$。 - 最大操作回合数 $T$ 满足 $4000\leq T\leq 64000$。 - 每取 1 克颜料的成本 $D$ 满足 $10\leq D\leq 10000$。

首先输出初始状态下隔板的配置，格式如下： > $v_{0,0}$ $\cdots$ $v_{0,N-2}$ > $\vdots$ > $v_{N-1,0}$ $\cdots$ $v_{N-1,N-2}$ > $h_{0,0}$ $\cdots$ $h_{0,N-1}$ > $\vdots$ > $h_{N-2,0}$ $\cdots$ $h_{N-2,N-1}$ - $v_{i,j}$ 表示格子 $(i,\ j)$ 与 $(i,\ j+1)$ 之间的纵向隔板状态。$v_{i,j}=0$ 表示隔板打开，$v_{i,j}=1$ 表示隔板关闭。 - $h_{i,j}$ 表示格子 $(i,\ j)$ 与 $(i+1,\ j)$ 之间的横向隔板状态。$h_{i,j}=0$ 表示隔板打开，$h_{i,j}=1$ 表示隔板关闭。 接下来，输出最多 $T$ 行操作。第 $t$ 行表示第 $t$ 回合的操作，格式如下： - 向格子 $(i,\ j)$ 所在井中，从管 $k$（$0\leq k\leq K-1$）加入 1 克颜料： > 1 $i$ $j$ $k$ - 从格子 $(i,\ j)$ 所在井中取出 1 克颜料交给画家： > 2 $i$ $j$ - 从格子 $(i,\ j)$ 所在井中取出 1 克颜料并废弃： > 3 $i$ $j$ - 对相邻格子 $(i_1,\ j_1)$ 和 $(i_2,\ j_2)$ 之间的隔板进行开合操作： > 4 $i_1$ $j_1$ $i_2$ $j_2$ [查看示例](https://img.atcoder.jp/ahc048/lI5DXOAV.html?lang=ja&seed=0&output=sample)

### 故事背景 高桥画伯正在创作新系列水彩画。他的作品以细腻的用色著称，对色彩调配尤为讲究。你作为高桥画伯的助手，肩负着现场为他调配所需颜色的重要任务。 由于颜料价格昂贵，要求尽量减少浪费。幸运的是，所需颜色的列表已提前给出。请尽可能准确且节省地按顺序调配这些颜色。 ### 得分 第 $i$ 次交给画家的颜料颜色为 $(C_i^\mathrm{made},\ M_i^\mathrm{made},\ Y_i^\mathrm{made})$ 时，误差 $E$ 定义为： \[ E = \sum_{i=0}^{H-1} \sqrt{(C^{\mathrm{target}}_i - C^{\mathrm{made}}_i)^2 + (M^{\mathrm{target}}_i - M^{\mathrm{made}}_i)^2 + (Y^{\mathrm{target}}_i - Y^{\mathrm{made}}_i)^2} \] 操作 1 的总次数为 $V$，则绝对分数为： \[ 1 + D \cdot (V - H) + \mathrm{round}(10^4 \times E) \] **绝对分数越小越好。** 每个测试用例的**相对评价分数**为 $ \mathrm{round}(10^9\times\ \frac{全体参赛者中最小绝对分数}{你的绝对分数}) $，所有测试用例的和即为你的得分。 最终排名将在赛后系统测试（更多输入）中根据得分决定。无论是暂定测试还是系统测试，若某些测试用例输出不合法或超时，则该用例的相对分数为 0，并且该用例不计入“全体参赛者中最小绝对分数”的计算。系统测试仅对**最后一次非 CE 提交**进行，因此请确保最终提交正确。 #### 测试用例数 - 暂定测试：50 个 - 系统测试：2000 个，赛后公开 [seeds.txt](https://img.atcoder.jp/ahc048/seeds.txt) (sha256=e93b5367e87f49c8fe325dbeb0f8daa331d23481c1eb533ff032c7978e39ae04) #### 相对评价系统说明 无论暂定还是系统测试，只有最后一次非 CE 提交计入排名。用于计算每个测试用例“全体参赛者中最小绝对分数”的也是当前排名表中的最后提交。 排名表显示的是相对评价分数，每次新提交都会重新计算。提交列表中显示的分数是所有测试用例的绝对分数之和，不显示相对分数。若想知道历史提交在当前排名下的相对分数，需要重新提交。输出不合法或超时时，提交列表分数为 0，但排名表会显示所有通过用例的相对分数之和。 #### 关于运行时间 运行时间会有一定波动。系统测试时由于并发执行较多，运行时间比暂定测试略长（约多几个百分点）。因此，接近时间限制的提交在系统测试中可能 TLE。建议在程序中自行计时并提前终止，或留出充足时间余量。 ### 输入生成方法 - $\mathrm{rand}(L,U)$：生成 $L$ 到 $U$ 之间的整数，均匀分布。 - $\mathrm{rand\_double}(L,U)$：生成 $L$ 到 $U$ 之间的实数，均匀分布。 #### $N$, $K$, $H$, $T$, $D$ 的生成 - $N=20$ - $K=\mathrm{rand}(4,20)$ - $H=1000$ - $T=\mathrm{round}(4000\times\ 2^{\mathrm{rand\_double}(0,4)})$ - $D=\mathrm{round}(10^{\mathrm{rand\_double}(1,4)})$ #### 管装颜料 $(C^{\mathrm{own}},\ M^{\mathrm{own}},\ Y^{\mathrm{own}})$ 的生成 对每个 $i$ 独立生成： - $C_i^{\mathrm{own}}=\mathrm{rand}(0,10^5)\times 10^{-5}$ - $M_i^{\mathrm{own}}=\mathrm{rand}(0,10^5)\times 10^{-5}$ - $Y_i^{\mathrm{own}}=\mathrm{rand}(0,10^5)\times 10^{-5}$ #### 目标颜色 $(C^{\mathrm{target}},\ M^{\mathrm{target}},\ Y^{\mathrm{target}})$ 的生成 对每个 $i$，按以下步骤独立生成： 1. 生成 $K$ 个值 $x_0,\dots,x_{K-1}$，其中 $x_k = -\ln\ \mathrm{rand\_double}(0,1)$，$\ln$ 为自然对数。 2. 归一化：$x_k' = x_k / \sum_{j=0}^{K-1} x_j$。 3. 目标颜色各分量如下： \[ C_i^{\mathrm{target}} = \mathrm{round}\left(10^5 \times \sum_{k=0}^{K-1} x_k' C_k^{\mathrm{own}}\right) \times 10^{-5} \] \[ M_i^{\mathrm{target}} = \mathrm{round}\left(10^5 \times \sum_{k=0}^{K-1} x_k' M_k^{\mathrm{own}}\right) \times 10^{-5} \] \[ Y_i^{\mathrm{target}} = \mathrm{round}\left(10^5 \times \sum_{k=0}^{K-1} x_k' Y_k^{\mathrm{own}}\right) \times 10^{-5} \] ### 工具（输入生成器与可视化器） - [网页版](https://img.atcoder.jp/ahc048/lI5DXOAV.html?lang=ja)：比本地版更高性能，支持动画显示。 - [本地版](https://img.atcoder.jp/ahc048/lI5DXOAV.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的二进制](https://img.atcoder.jp/ahc048/lI5DXOAV_windows.zip)：如不便安装 Rust，可直接使用。 比赛期间，禁止分享可视化结果、讨论解法或思路。请注意遵守。 由 ChatGPT 4.1 翻译