← 返回题目列表

AtCoder · xmascon20_a

A. 加减印章

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

配点 : 100 点

兔子是 它有一个矩形网格昨年呀 请注意,它可能是一昨年像这样,正在制作纪念 Xmas Contest 2020 的看板。

顺便说一下,去年用了很多种类的作为印章来玩……。

問題文

仅使用给定的印章至多 20\,000 次来制作符合下列区域地图的图像。如果满足后述的达成条件,也可以制作彩色图像。

131406f65c283f8139f6242ce0e06523.png

画布与印章

用于制作图像的画布宽度为 800 px,纵向 400 px,像素的位置是整数坐标的组合。 (x, y) (0 \le x < 800,0 \le y < 400)。x 注意坐标增大的方向是从左到右,y 注意,坐标增加的方向是从上到下。每个像素都有表示颜色的 R, G, B 可以得到第 3 元素。起初,画布的任何元素都是 R, G, B 的所有值 0 。

印章的大小为 s 和颜色信息 r, g, b 可以得到第 4 通过整数表示。1 使用至多次印章操作时,可以在画布的指定位置按下印章或从指定位置拉取印章。可以做到。

更详细地说,某个印章 (s, r, g, b) 在位置 (x_i, y_i) 上按下/拉动时,x_i \le x < x_i + s 和 y_i \le y < y_i + s 满足条件的所有像素 (x, y) 对于这些像素的 R, G, B 值各自 r, g, b 被加/减。操作的结果,如果某个像素的值 255 超过了 255 , 因为我在写0 低于了 0 。

達成条件

在区域图中,同一种颜色的像素 4 方向上连通的部分称为領域。为了使某个图像被认为是“沿着区域图”,需要满足以下条件:

  • 每个区域内的颜色在一定程度上是相同的。
  • 相邻的区域颜色在一定程度上是不同的。

从严格意义上来说,图像满足以下 2 满足以下任一条件即可:

  • 領域内条件:对于每个区域,区域内所有像素的 R 值的方差 700 要小于等于。同时,G 的方差与 B 的方差同样 700 要小于等于。
  • 隣接領域条件:某个区域的平均色为区域内所有像素的 R, G, B (按元素)平均值。在区域图中,相邻的 2 个区域的平均颜色分别满足 (R_1, G_1, B_1) 和 (R_2, G_2, B_2) ,然后(R_1 - R_2)^2 + (G_1 - G_2)^2 + (B_1 - B_2)^2 \ge 80^2 。

数据

为了解决这个问题所需的数据汇总在一个压缩文件中单击此处下载。zip 内包含如下文件。

  • stamps/map.png:表示区域图的图像。图像尺寸为横 800 px,纵向 400 px。
  • stamps/map.txt:与区域图对应的文本文件,为每个像素分配该区域的 ID。
    • 400 由若干行组成,每行包含 800 个整数。
  • stamps/stampset.txt: 可用印章的列表文本文件。
    • 1 行表示印章的种类数。 K 被写下。
    • 继续 K 每行中, 5 整数 给出了 k, s, r, g, b 被写入。 这意味着印章 ID 为 k 的印章由 (s, r, g, b) 表示。印章按印章 ID 的升序编写。
  • stamps/play.html: 可视化及手动操作工具。它还具有操作序列可视化和达成条件判定等功能,因此至少在提交前推荐使用。
    • 左下角有“加载印章操作”功能。这只会读取表示正确印章操作的行(因此,当输入符合下面描述的输出格式时,第一行会被简单跳过)。
  • stamps/play.js: 可视化及手动操作工具的源代码。

制約

以下列出了上述数据所满足条件的一些重要信息。

  • 图像大小为横 800 px,纵向 400 px。
  • 区域的数量为 30 ,区域 ID 为 0, \ldots, 29 。
  • 被赋予相同区域 ID 的像素集合在 4 方向上是连通的。
  • 印章的种类数量为 18 ,印章 ID 为 0, \ldots, 17 。
  • 对于每个印章,以下成立:
    • 7 \le s \le 50.
    • 0 \le r \le 40.
    • 0 \le g \le 40.
    • 0 \le b \le 40.

入力

本题没有提供输入。

出力

p
k_1 x_1 y_1 t_1
\vdots
k_p x_p y_p t_p

1 行表示印章操作的次数的整数 p (0 \le p \le 20\,000) 输出。

继续 p 行 i (1 \le i \le p) 行包含i 第几次的印章操作表示 4 整数 k_i, x_i, y_i, t_i 请以空格分隔输出。这表示在第i 次操作中,在位置 (x_i, y_i) 使用 ID 为 k_i 的印章。t_i = 1 的情况是按下印章的操作,t_i = -1 的情况表示拉取印章的操作。

印章必须至少在 1 个像素覆盖的位置使用。也就是说,ID k_i 的印章大小是 s 时,-s < x_i < 800 和 -s < y_i < 400 。


入力例 1


出力例 1

4
0 100 200 1
1 -10 5 1
2 799 300 -1
0 100 200 1

这是满足上述格式条件的输出示例(不过,因为该输出未满足达成条件,所以变成 WA )。