← 返回题目列表

AtCoder · rco_contest_2019_final_b

B. 转动并对齐

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

問題文

拼图爱好者X正在尝试解开他自己设计的新拼图。

X设计的拼图是 N × N 左上、右上、左下和右下单元格的坐标分别为 (0,\ 0),\ (0,\ N-1),\ (N-1,\ 0),\ (N-1,\ N-1) 。
这里是GRITDO内一个单元的坐标 使用 (r,\ c) ,称为下文定义的领域之一。 如果

  • \(r < N/2\) 和 \(c < N/2\),则左上域。 如果使用
  • \(r < N/2\) 和 \(c \geq N/2\) ,则右上域。 如果使用
  • \(r \geq N/2\) 和 \(c < N/2\),则它是左下角的区域。 如果使用
  • \(r \geq N/2\)和\(c \geq N/2\),则它是右下域。
每个格子涂成四种颜色之一:红色、黄色、绿色或蓝色,每个格子涂成该颜色 N × N / 4 存在于单个单元中。

在这个拼图中,可以进行以下操作。

  • 选择格子内的某个小格子,然后将其内部顺时针旋转90度。


对上述操作最多进行 M 次,将格子的左上区域聚集红色、右上区域聚集黄色、左下区域聚集绿色、右下区域聚集蓝色,这是这个拼图的目标。

请替代擅长设计拼图但不擅长解谜的X,思考应该进行什么样的操作。

各测试用例的得分以及该问题的得分计算方式如下。

  • 单个测试用例的得分计算方式如下。
    • 在所有操作完成后的格子中,
      \({\it 左上角红色细胞数量}\ +\ \)\({\it 右上角黄色细胞数量}\ +\ \)\({\it 左下角绿色细胞数量}\ +\ \)\({\it 右下角蓝色细胞数量}\)
      会获得积分。
    • 如果所有红色细胞都在左上角,黄色细胞在右上方,绿色细胞在左下区域,蓝色细胞在右下角,这称为完全解,并加到分数 \(M - {\it 操作计数}\中)。
  • 总共 50 有些物品。 每个测试的总分即为该题目的总分。

入力

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

N M
c_{0,0} c_{0,1} \(\cdots\) c_{0,N-1}
\(\vdots\)
c_{N-1,0} c_{N-1,1} \(\cdots\) c_{N-1,N-1}
  • N 是表示 gritdo 垂直和水平长度的整数,N=20 感到满意。
  • M 表示操作的最大次数的整数,M=1000 感到满意。
  • c_{i,j} 是坐标 (i,\ j) 的单元格的初始状态的整数,对应关系为 0=红色, 1=黄色, 2=绿色, 3=蓝色。

出力

请将要进行的操作按顺序每行一个输出到标准输出。
在这里,r_{i},\ c_{i} 是子网格左上角第一个单元格的坐标 (r_{i},\ c_{i}) 表示,s_{i} 表示子网格的边长。

r_{0} c_{0} s_{0}
\(\vdots\)
r_{i} c_{i} s_{i}
\(\vdots\)

关于生成手刀刻

这个测试用例,是从完全解的状态中随机选择子网格,并按逆时针方向旋转 90 度进行 1000 次的操作。
也就是说,保证在 1000 次以内的操作可以得到完全解。


入力例1

4 1000
3 2 3 2
3 3 1 0
1 1 0 1
0 0 2 2

注意:此输入不符合作为测试用例的否定条件。

出力例1

0 0 3
0 1 3
1 1 2
0 0 4


每个网格从初始状态到最终操作后的可视化结果如下所示。

初期状態
操作 (0 0 3) 後
操作 (0 1 3) 後
操作 (1 1 2) 後
操作 (0 0 4) 後


由于我们获得了完整的解决方案,因此该样本的得分为 \(4 + 4 + 4 + 4 + (1000 - 4) = 1012\)。

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

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

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

提示:旋转子网格的过程是在测试器中完成的。 有実装。请参考一下。


展示台

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

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

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

展示台