← 返回题目列表

AtCoder · rco_contest_2019_qual_b

B. 农民X的收获计划

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

問題文

X 已经开了一个家庭菜园,正在制定照料和收获蔬菜的计划。

X 的花园是 N 行 N 由分区列组成,并且i 行 j 质量在栏里 有 A_{i,j} 蔬菜。每个地块只能收获一次蔬菜。

X最多可以执行以下操作之一: 可以执行 M 次。每项操作均在一块尚未收获蔬菜的地块上进行。如果您指定一块已经收获蔬菜的地块,则不会执行任何操作。

  • (1)护理:检查所选地块内的蔬菜质量。 1 增加。
  • (2)収穫:从选定的地块和周围的地块收获蔬菜。为了收获,必须满足以下条件:
    • 检查所选地块内的蔬菜质量。 比方说 K。
    • 从选定的地块来看,“尚未收获的品质”K通过仅追踪包含蔬菜的地块来垂直和水平连接的一组地块。 比方说 S 。 ( S 包括所选部分本身。 )
    • S 中包含的分区是 K 或更多, 在S 中包含的所有地块中收获蔬菜。 如果小于
    • S 中包含的分区是 K ,则不执行任何操作。

请制定计划,使 X 收获的蔬菜的总体质量尽可能高。

每个测试用例和该问题的分数计算如下:

  • 在一个测试用例中,分数是 X 收获的蔬菜质量的总和。
  • 总共有 50 个。每个测试的得分总和,就是本题的得分。

入力

输入是按以下格式从标准输入给出的。

\(\begin{array}{lll}
    N ~ M & & \\
    A_{ 0,0 } & \ldots & A_{ 0,N-1 } \\
    \vdots & \ddots & \vdots \\
    A_{ N-1,0 } & \ldots & A_{ N-1,N-1 }
  \end{array}\)
  • N 是代表花园大小的整数, 满足N = 50 。 由于是
  • M 是一个整数,表示允许的最大操作数,M = 2500 。 由于是
  • A_{i,j} 是 您也可以写 i 行 j 代表该列部分中蔬菜质量的整数。1 ≤ A_{i,j} ≤ 9 。 由于是

出力

每行一次操作,最多 请输出 M 行。 列出

\(\begin{array}{lll}
    \mathit{op}_0 & r_0 & c_0 \\
    \mathit{op}_1 & r_1 & c_1 \\
    \vdots & & \\
  \end{array}\)

\(\mathit{op}_i\) 是 如果你想做 护理如果你这样做1,収穫如果你想 输出2,然后输出要操作的分区(r_i 行 c_i 列)以空格分隔。

关于测试的生成

每个用例均由测试用例生成器生成。
测试用例生成器从 \([1, 9]\) 范围内的整数均匀随机生成 \(A_{i,j}\)。
测试用例生成器可从页面底部的链接获取。


入力例1

3 9
5 5 5
1 5 9
5 9 1

出力例1

2 0 0
1 1 0
1 1 0
1 1 0
1 1 0
2 0 0
2 2 2
1 2 1
庭 説明 分数
这是输入花园。此样本数量有限 不满足 N=50, M=2500 。 0
第一次操作 (2 0 0),然后 查看自 (0,0) 看到从 S 中包含的部分是 (0,0), (0,1), (0,2), (1,1) 可以得到第 4因此,不满足采收条件。 与(1,1) 对角相邻的部分 请注意,它不包含在 (2,0) 是 您也可以写 S 中。 0
以下四个操作(1 1 0重复4次) (1,0) 蔬菜质量 将其更改为 1 减去 5 。 0
下一步操作 (2 0 0),然后 查看自 (0,0) 看到从 S 中包含的部分是 (0,0), (0,1), (0,2), (1,0), (1,1), (2,0) 可以得到第 6 因此,满足采收条件。 包含在 S 中 6 质量 收获 5 蔬菜。 在 30
下一步操作 (2 2 2),然后 查看自 (2,2) 收获蔬菜。质量是 1 蔬菜也可以单独收获。 31
上次操作 (1 2 1),然后 查看自 (2,1) 蔬菜质量 将其更改为 9 减去 10 。 A_{i,j} 是 您也可以写 1 以上 9 以下整数表示蔬菜的品质。 通过执行护理它可以是大于或等于 10 的整数。 31

生成器和测试器以及样本输入数据

测试用例生成器、测试器和示例输入数据由以下链接提供。

发电机测试仪样本输入数据


展示台

我们准备了一个可视化工具,可以计算分数并可视化输入和输出文件的结果。

  • 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。特别是,已经确认它不能在 Internet Explorer 上运行。
  • 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
  • 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。

还可以通过以下链接获取该可视化工具。链接中还包含有关如何使用它的说明。

展示台

观察仪主体
输入文件
输出文件
fps
分数增量
分数 本实验的
操作
另存为图像