配点 : 10000000000 点
問題文
N 行 N 列网格
给出了 A 。左上角方块的位置
将其定义为 (0,0) 。
此时从左上角方块往下 i\ (0 ≦ i ≦ N-1) 向右方格 j\ (0 ≦ j ≦ N-1) 前进一格的格子位置是
由 (j,i) 代表。
另外,每个方格中写入一个整数,位置
写在方格 (j,i) 中的整数
由 A_{i,j} 代表。
这里,所有方格中写入的整数是 0 的状态被定义为“初始网格”。
另外,网格 P 的“V 形添加”
定义 (X,Y,H) 如下。
- 一、山体中心广场位置 (X,Y)\ (0 ≦ X,Y ≦ N-1) 和代表山的高度的整数 指定 H\ (1 ≦ H ≦ N) 。
- 之后,所有方块 重写为 P_{y,x} 该值应乘以 P_{y,x} + max(0, H - |x-X| - |y-Y|) 。
例如,8 行 8 作为该列的初始正方形的正方形
考虑 Q 。
广场
对于 Q , 3 雪佛龙添加
下图显示了 (X,Y,H) = (1,2,5),(5,1,3),(6,6,2) 之后的网格。
图 V 形添加示例(空白单元格为 代表 0 。 )
给定正方形 A 是
必须满足N 行 N 对列的初始方块执行 V 形加法。
这是通过执行 1000 次生成的网格。
你的目的是网格
目标是找到一个 V 形加法过程,生成尽可能接近 A 的网格。
具体来说,首先,
准备N 行 N 作为该列的初始正方形的正方形
考虑 B 。
接下来,你 B 的最大 V 形添加量
您最多可以执行 1000 次。
和网格 A 和网格
比较 B 时
目的是找到一种 V 形加法程序,最大限度地减少
。
此外,网格
如果存在多个产生 A 的 V 形添加步骤,则应尽量减少 V 形添加的数量。
採点方法
每个测试用例的分数计算如下。
- 縦 N 方形,水平 N 对于正方形的初始正方形,根据程序输出的V形加法过程将正方形相加。 生成 B 。
- 一、作为基本点
点。 - 广场 对于 A 和网格 比较 B 中写入的整数在所有方格中都匹配,则计算V形加法的次数。 Q 作为奖励积分, 1,000-Q 点。
整个问题的分数计算如下。
- 测试用例的数量是下面的输入示例。 包含 1 包括 50 情况就是这样。这个 50 案例分数的总和就是程序分数。
- 请注意,如果所有测试用例的状态不是“AC”,则除“example_01”之外的所有测试用例的分数将为 0 分。
制約
- N=100
- 0 ≦ A_{i,j} ≦ 100,000
- 广场 对于 A 是初始方块 这是通过执行 1000 次 V 形加法生成的正方形。 尽可能接近
入力
输入按以下格式给出。
A_{0,0} A_{0,1} ... A_{0,N-1}
A_{1,0} A_{1,1} ... A_{1,N-1}
:
A_{N-1,0} A_{N-1,1} ... A_{N-1,N-1}
出力
广场 对于 A 的正方形 按以下格式输出 V 形加法生成 B 的步骤。
Q X_1 Y_1 H_1 X_2 Y_2 H_2 : X_Q Y_Q H_Q
1 第一行显示了山形添加的数量。 Q\ (0≦Q≦1000) 。
1+i \ (1 ≦ i ≦ Q) 行中,i 第一个 V 形加法中使用的参数
输出代表 (X_i,Y_i,H_i) 的整数,并用空格分隔。
如何生成测试用例
广场 对于 A 是初始正方形, 它是通过执行1000 次 V 形加法生成的。
每轮 V 形添加中使用的参数 (X,Y,H) 的限制 使用
- X 是 [0,N-1] 范围内的均匀随机数进行随机选择。
- Y 是 [0,N-1] 范围内的均匀随机数进行随机选择。
- H 是 [1,N] 范围内的均匀随机数进行随机选择。
入出力例1
测试用例“example_01”对应于输入/输出示例 1。测试用例“example_01”也将被评分。
展示台
我们准备了一个可视化工具,可以可视化分数计算以及输入和输出文件的结果。
- 我们建议将此可视化工具与 chrome 一起使用。我们不保证它在其他环境下也能正常工作。我们已明确确认它不适用于 Internet Explorer。
- 您无法从此可视化工具提交答案。请在 AtCoder 上提交您的答案。
- 此可视化工具上计算的分数并不保证本次比赛的分数。请注意,我们不能保证因使用此可视化工具而造成的任何损坏。
如何操作和查看
- 左键单击旋转,右键移动,鼠标滚轮缩放。
- 输入文件网格 A 以及从输出文件中的 V 形添加过程生成的网格 B 进行比较并用颜色编码为三个区域:红色、白色和蓝色。
对于每个,红色:匹配,白色:缺失( 仅在 A_{i,j} > B_{i,j} 的情况下出现),蓝色:过量( A_{i,j} < B_{i,j} )。 - 高度方向的默认比例为 1/100。比例可以更改,因此请将其调整为易于看到的比例。
输出文件:
高度比例:/100
统计信息(每个不同高度的金字塔你花了多少钱?)