← 返回题目列表

AtCoder · joisc2009_pyramid

pyramid. 金字塔

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

以下是来自日本的官方日本新闻原版PDF,已完整保留并按原样染色。

貫きピラミッド (Pyramid) - 原题 PDF 第 1 页
原题PDF第3页
貫きピラミッド (Pyramid) - 原题 PDF 第 2 页
原题PDF第4页
可复制的 PDF 提取文本
Pyramid: 貫きピラミッド


input ファイル“pyramid.in”
output 標準出力
ソースファイルpyramid.c/pyramid.cpp
時間制限5 秒/ データ



 古代JOI 王国では,国王の墓として砂漠にピラミッドを作る風習があった.この国では,国

王が死ぬと,占いによって決められる「ある場所」に,占いによって決められる「ある高さ」の

ピラミッドを作ることになっている.

  JOI 王国の砂漠は東西幅がW,南北幅がH の長方形の形をしている.砂漠は1 × 1 の正方形

の区画に分かれており,各区画は0 ≦x < W, 0 ≦y < H を満たす整数x, y によって(x, y) と表

現される.区画(0, 0) は北西隅の区画であり,区画(x, y) は,区画(0, 0) から東にx,南にy 進

んだ地点に位置する区画である.

 さて,ピラミッドは次のようにして作られる.まず,占いによってピラミッドの中心の区画

(X, Y ) と高さh が決められる.それに従って,次の規則で砂漠内の各区画に石を積むことによっ

てピラミッドを建設する:

     区画(X, Y ) を中心とする高さh のピラミッドを作る場合,砂漠内の区画(x, y)

    にはmax{0, h −max{|X −x|, |Y −y|}} 個の石を積む.砂漠の外には石は一切積ま

   ない.

 たとえば,砂漠の大きさがW = 7, H = 6 であり,区画(2, 1) を中心とする高さ3 のピラミッ

ドを作った場合,各区画に積まれている石の数は以下のようになる.

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

 しかし,JOI 王国はそれほど広くはないため,ピラミッドは過去のピラミッドと「重なって」

作られることもある.すなわち,新たにピラミッドを作ろうとしてある区画にn 個の石を積む

ことになった場合に,その区画に既にn 個以上の石が積まれていた場合は,その区画には何も

しない.一方,その区画にまだn 個未満しか石が積まれていなかった場合は,その区画に積ま

れている石の数をn 個まで増やす.


                    貫きピラミッド–1/2

そのため,多数のピラミッドが作られた末の見た目は複雑となる.たとえば上図の状態で,さ

らに区画(4, 3) を中心とする高さ4 のピラミッドを作ると,各区画に積まれている石の数は以下

のようになる.

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

 さて,考古学者であるあなたは,一体どれほどの数の石がピラミッドの建設に用いられてい

るかを知りたくなった.

 全てのピラミッドの中心位置の区画と高さが与えられた時,それらを建設するのに必要な石

の数を求めるプログラムを書け.


Input. 入力ファイルpyramid.in の1 行目は3 つの整数W, H, N (1 ≦W, H ≦3000, 1 ≦

N ≦10 000) が書かれている.W, H はそれぞれ砂漠の横幅,縦幅を表す.また,N はピラミッ

ドの個数を表す.

  2 行目以降のi + 1 行目(1 ≦i ≦N) には,3 つの整数xi, yi, hi (0 ≦xi < W, 0 ≦yi < H, 1 ≦

hi ≦3000) が書かれている.これらは,i 番目のピラミッドの中心位置の区画が(xi, yi) であり,

高さがhi であることを表す.

Output. 出力は,標準出力に行うこと.全てのピラミッドを建設するのに必要な石の数を表

す1 つの整数を出力せよ.

採点基準採点用データのうち,配点の10% 分については,W, H ≦1000, N ≦5 を満たす.ま

た,配点の25%分については,W, H ≦500 かつ,全てのピラミッドの高さが100 以下である.

例1
 pyramid.in 標準出力
 7 6 2       81
 2 1 3
 4 3 4

例2
 pyramid.in   標準出力
 3000 3000 1     17999999500
 1500 1500 3000


                    貫きピラミッド–2/2