← 返回题目列表

AtCoder · future_contest_2018_qual_a

A. 雪佛龙添加

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

配点 : 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

单击此处获取输入/输出文件 (zip)

测试用例“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

统计信息(每个不同高度的金字塔你花了多少钱?)

(输入数据时将显示统计数据) 您将获得一个由