AT_masters2026_final_a Copy-Paste Painting (A)

高橋画伯は、画像編集ソフトを駆使して新作アートの制作に取り組んでいる。 作品作りでは、複数のレイヤーを使い分けながら、少しずつ絵を描き足したり、別のレイヤーの内容を回転して重ねたり、不要になったレイヤーを消したりできる。 目標となる画像をできるだけ少ない手数で完成させる手順を求めてほしい。

有 $K$ 层，每层包含 $N \times N$ 个像素。各层编号为 $0,\cdots,K-1$。左上角像素的坐标为 $(0,0)$，从此处向下移动 $i$ 个像素、向右移动 $j$ 个像素到达的像素坐标为 $(i,j)$。 有 $C$ 种可用颜色，编号为 $1,\cdots,C$。记 $c(k,i,j)$ 表示第 $k$ 层上坐标为 $(i,j)$ 的像素颜色。如果 $c(k,i,j)=0$，则该像素为透明。 目标图像由每个像素的颜色 $g_{i,j}$ 给出。当且仅当对于所有 $(i,j)$，$c(0,i,j)=g_{i,j}$ 时，目标图像被视为完成，其他层的状态无关紧要。 初始时所有层均为透明，即 $c(k,i,j)=0$ 对所有 $k,i,j$ 成立。你可以通过以下操作最多执行 $N^2$ 次来完成目标图像。 - $\mathrm{paint}(k,i,j,x)$ ：指定一层 $k\in\{0,\cdots,K-1\}$，一个像素 $(i,j)$，以及颜色 $x\in\{0,\cdots,C\}$，将 $c(k,i,j)$ 改为 $x$。**若 $x=0$，该像素重新变为透明。** - $\mathrm{copy}(k,h,r,\Delta i,\Delta j)$ ：指定层 $k,h\in\{0,\cdots,K-1\}$，整数 $r\in\{0,\cdots,3\}$，$\Delta i,\Delta j\in\{-N+1,\cdots,N-1\}$。令 $h'$ 表示 $h$ 层顺时针旋转 $90$ 度 $r$ 次后的新层。注意，$h$ 层本身不发生改变。将 $h'$ 的左上角像素与第 $k$ 层的 $(\Delta i,\Delta j)$ 对齐，然后叠加。即，用 $h'$ 所有非透明像素覆盖 $k$ 层对应位置的像素。更具体地说，对于所有 $c(h',i,j)\neq 0$，将 $c(k, \Delta i+i, \Delta j+j)$ 赋值为 $c(h',i,j)$。**若本操作会导致 $k$ 层的任何像素越界，则判为 WA。可以有 $k=h$。** - $\mathrm{clear}(k)$ ：将第 $k$ 层的所有像素变为透明。

输入从标准输入读取，格式如下： > $N$ $K$ $C$ $g_{0,0}$ $\cdots$ $g_{0,N-1}$ > $\vdots$ > $g_{N-1,0}$ $\cdots$ $g_{N-1,N-1}$ 输入满足以下约束条件： - 每层边长 $N$ 固定为 $N=32$。 - $K$ 是 $2$ 到 $5$（含）之间的整数，表示层数。 - $C$ 是 $2$ 到 $4$（含）之间的整数，表示颜色数。 - $g_{i,j}$ 是 $0$ 到 $C$（含）之间的整数，表示目标图像中 $(i,j)$ 的颜色。 - 不一定所有 $1,\cdots,C$ 出现在目标图像中。 - 目标图像中非透明像素的个数不少于 $N^2/2$。

请按操作顺序，每行输出一个操作，格式如下： - $\mathrm{paint}(k,i,j,x)$ > $0$ $k$ $i$ $j$ $x$ - $\mathrm{copy}(k,h,r,\Delta i,\Delta j)$ > $1$ $k$ $h$ $r$ $\Delta i$ $\Delta j$ - $\mathrm{clear}(k)$ > $2$ $k$

### 评分方式 记 $T$ 为操作数，$U$ 为目标图像中的非透明像素数量，即所有满足 $g_{i,j}\neq 0$ 的 $(i,j)$ 的数量。得分计算如下： \[ \mathrm{round}\left(10^6 \times \left(1+\log_2 \frac{U}{T}\right)\right) \] 本题分为两个子问题：A 和 B，区分标准为输入生成方式不同。每个子问题包括 150 个测试点，对该子问题的提交总分为所有测试点得分总和。若您的输出非法或某个测试点超时，则本次提交整体判为 WA 或 TLE，得分为零。 最终排名由两个子问题的最高得分之和决定，赛后不会有系统测试。如有多队得分相同，则排名并列，与提交时间无关。 ### 输入生成说明 定义 $\mathrm{rand}(L,U)$ 为在 $L$ 到 $U$（含）范围内均匀随机生成的整数。如果一层的所有非透明像素在四邻域下连通，称该层非透明像素为连通。 问题A的输入生成方式如下。 #### $N$，$K$，$C$ 的生成 $N$ 固定为 $32$。$K=\mathrm{rand}(2,5)$ 且 $C=\mathrm{rand}(2,4)$。 #### $g$ 的生成 首先生成 $K'=\mathrm{rand}(1,2K)$。准备 $K'$ 个透明层，记 $c(k,i,j)$ 表示第 $k$ 层上 $(i,j)$ 的颜色。设置 $c(0,N/2,N/2)=1$。再生成参数 $p=\mathrm{rand}(2,5)$。 重复以下操作，直到某一操作后，某层非透明像素数量首次达到或超过 $N^2/2$ 时结束，此时该层的像素即为 $g_{i,j}$。 每次迭代，以概率 $p/10$ 执行 paint 操作，概率 $1-p/10$ 执行 copy 操作。 **paint 操作：** 通过 $k=\mathrm{rand}(0,K'-1)$ 选择一层。若该层为透明，设 $(i,j)=(N/2,N/2)$；否则，$(i,j)=(\mathrm{rand}(0,N-1),\mathrm{rand}(0,N-1))$。令 $\mathrm{num}(x)$ 表示所有层中颜色为 $x$ 的像素数量。从使 $\mathrm{num}(x)$ 最小的颜色 $x\in\{1,\cdots,C\}$ 中均匀随机选择一个。暂时更新 $c(k,i,j)=x$，检查本层所有非透明像素是否连通。若不连通，丢弃本次尝试并重新生成 $(i,j)$。 **copy 操作：** 生成目标层 $k=\mathrm{rand}(0,K'-1)$。在已有非透明像素的层中随机选择一层 $h$。生成旋转次数 $r=\mathrm{rand}(0,3)$。让 $h'$ 为将 $h$ 顺时针旋转 $90$ 度 $r$ 次获得的新层。对于 $h'$ 的所有非透明像素，记最小/最大 $i$ 坐标为 $i_0,i_1$，最小/最大 $j$ 坐标为 $j_0,j_1$。生成平移量 $(\Delta i,\Delta j)=(\mathrm{rand}(-i_0,N-1-i_1),\mathrm{rand}(-j_0,N-1-j_1))$。暂时应用 $\mathrm{copy}(k,h,r,\Delta i,\Delta j)$ 操作，检查本层非透明像素是否连通。若不连通，丢弃本次操作重新选择 $h$，$k$ 仍然保持不变。 ### 关于问题 B **对于问题 B，每队可自制输入并通过提交进行替换。** 如何提交可参见 Problem C 页面。 每队可提交四个输入。系统将随机选取其中一个向全部队伍公开，其余三个用于评测。 **公开输入并开始评测将在比赛开始约 2 小时 20 分后进行，系统准备好后将公告通知参赛者。** 如某队未提交自定义输入，则默认随机生成上述流程的四份输入。 由于每队知道自己提交的输入内容，允许预先计算输出并将其嵌入到解题程序中。 Problem C 可多次提交，只记录自比赛开始 $120$ 分钟内、且最后一次 AC 的提交用于评测。 ### 工具（输入生成器与评分计算） - [本地版本](https://img.atcoder.jp/masters2026-final/aCVc95hT.zip)：需安装 [Rust 语言](https://www.rust-lang.org/) 环境。 - [Windows 预编译版](https://img.atcoder.jp/masters2026-final/aCVc95hT_windows.zip)：不熟悉 Rust 可用。 请注意，比赛期间禁止与团队之外成员分享可视化结果或讨论解题思路。 由 ChatGPT 5 翻译