A - 山型足し算 /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 10000000000

問題文

NN 列のマス目 A が与えられます。一番左上のマスの位置を (0,0) と定義します。
このとき、左上のマスから下に i\ (0 ≦ i ≦ N-1) マス、右に j\ (0 ≦ j ≦ N-1) マス進んだマスの位置は (j,i) で表されます。
また,各マスに整数が書かれており、位置 (j,i) のマスに書かれている整数を A_{i,j} で表します。

ここで、マス目に対して全てのマスに書かれている整数が 0 である状態を「初期マス目」と定義します。
また、マス目 P に対する「山型足し算」 (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|) に書き換えます。

例として、88 列の初期マス目であるマス目 Q を考えます。
マス目 Q に対して、 3 回の山型足し算 (X,Y,H) = (1,2,5),(5,1,3),(6,6,2) を行った後のマス目を以下の図に示します。

図 山型足し算の例 (空白のマスは 0 を表す。)

与えられたマス目 A は、NN 列の初期マス目に対して、山型足し算を 1000 回行って生成されたマス目です。
あなたの目的は、マス目 A にできる限り近いマス目を生成する山型足し算の手順を求めることです。

具体的にはまず、NN 列の初期マス目であるマス目 B を用意します。
次に、あなたはマス目 B に対して山型足し算を最大 1000 回まで行うことができます。
そして、マス目 A とマス目 B を比較したとき を最小化する山型足し算の手順を求めることを目的とします。
さらに、マス目 A を生成するような山型足し算の手順が複数存在する場合には、山型足し算の回数を最小化することを目指してください。

採点方法

各テストケースの得点は以下のように計算される。

  • N マス、横 N マスの初期マス目に対し、あなたのプログラムが出力した山型足し算の手順に従い、マス目 B を生成する。
  • まず、基本点として 点が得られる。
  • マス目 A とマス目 B に書かれている整数が全てのマスで一致した場合、山型足し算の回数を Q とすると、ボーナス点として 1,000-Q 点が得られる。

問題全体の得点は以下のように計算される。

  • テストケースの数は、以下の入力例 1 を含む 50 ケースである。この 50 ケースの点数の和がプログラムの点数となる。
  • 全テストケースのステータスに「AC」以外が存在する場合には、「example_01」を除く全てのテストケースの点数は0点となるので注意せよ。

制約

  • N=100
  • 0 ≦ A_{i,j} ≦ 100,000
  • マス目 A は初期マス目に対して 1000 回の山型足し算を行うことで生成されたマス目である。

入力

入力は以下の形式で与えられる。

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 にできる限り近いマス目 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 回目の山型足し算で用いるパラメータ (X_i,Y_i,H_i) を表す整数をスペース区切りで出力せよ。

テストケースの生成方法

マス目 A は初期マス目に対して、1000 回の山型足し算を行うことで生成される。

各回の山型足し算で用いられるパラメータ (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 と出力ファイルの山型足し算手順から生成されるマス目 B を比較して、赤・白・青の3つの領域に色分けされます。
    それぞれについて、赤:一致、白:不足 ( A_{i,j} > B_{i,j} の場合のみ出現) 、青:過剰 ( A_{i,j} < B_{i,j} の場合のみ出現) を表します。
  • 高さ方向はデフォルトの縮尺を1/100にしています。縮尺は変更可能となっているため、見易い縮尺に調整してください。
入力ファイル:
出力ファイル:
高さの縮尺:/100

統計情報(高さいくつのピラミッドをそれぞれいくら使ったか)

(データを入力すると統計情報が表示されます)