← 返回题目列表

AtCoder · gw2015_i

I. 金字塔 - 立方体版

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

問題文

八神酱的繁荣是金字塔。

八神酱厌倦了由球形石头制成的金字塔,所以这一次 1 边长为 我决定使用 1 立方体形状的石头制作金字塔。 Iori-chan 决定按照以下步骤制作金字塔。 在纸上画出

  • N \times N 网格。每个正方形的 1 边长为 1 。i (1 ≦ i ≦ N) 行目 j (1 ≦ j ≦ N) 标记列中的方块 我们称之为 (i,j) 。
  • 每个方格都有石头 垂直堆叠至少 1 块。鳟鱼 (i,j) 有 堆叠 H_{i,j} 石头。
  • 广场 1 选择一项。正方形这个正方形 P 。
  • 一些石头(0 )。这时剩下的石头 质量 金字塔以 P 为中心 必须配置 。

然而,石头是质量 以 P 为中心形成金字塔的状态如下。

  • 质量 金字塔以 P 大众 (Pi,Pj)、马斯 (i,j) 上堆放的石头数量 如果我们称之为 S_{i,j}、S_{Pi,Pj} 它被转换为格式 T ,所有 以下公式适用于 i (1 ≦ i ≦ N), j (1 ≦ j ≦ N) 。然而, 让它代表Abs(x) 是 仅由 x 的绝对值。
    • S_{i,j} = Max(0, T - Max(Abs(Pi - i), Abs(Pj - j)))
    • S_{i,j} ≦ Min(Pi, Pj, N - Pi + 1, N - Pj + 1)

此时,质量 P 上堆放的石头数量 如果我们称之为 金字塔高度 。

全部 对于 i (1 ≦ i ≦ N), j (1 ≦ j ≦ N) ,质量 求创建以 (i,j) 为中心的金字塔时创建的金字塔的最大高度,并计算高度之和。


入力

输入由多个测试用例组成。

( 测试用例的生成方法有点不寻常,但这只是减少输入文件大小的措施,没有其他深层含义。 )

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

N Q
X A B C
H_{1,1} H_{1,2} ... H_{1,N}
H_{2,1} H_{2,2} ... H_{2,N}
:
H_{N,1} H_{N,2} ... H_{N,N}
  • 1 该行中有正方形。 1 表示边数的整数 N (1 ≦ N ≦ 500) 和一个表示测试用例数量的整数 Q (1 ≦ Q ≦ 10) 用空格分隔。
  • 2 行中,4 整数 X (0 ≦ X < C), A (0 ≦ A < C), B (0 ≦ B < C), C (N ≦ C ≦ 30,000) 用空格分隔。这些是在生成测试用例时用于生成随机数的整数。
  • 3 从线 N 行给出了每个方格中最初放置的棋子数量的信息。其中 i (1 ≦ i ≦ N) 行中,N 整数由空格分隔。其中 j (1 ≦ j ≦ N) 第一个整数 H_{i,j} (1 ≦ H_{i,j} ≦ N) 是质量 表示要堆叠在 (i,j) 上的石子数量。

出力

输出是 由 Q 行组成。其中 i 行中,i 输出测试用例的答案。还在输出末尾添加换行符。

源代码可以按照下面类似C语言的伪代码来编写。

int N, Q, X, A, B, C;
int H[500][500];
int Rand() {
  return X = (A * X + B) % C;
}
void Shuffle() {
  for (int i = 0; i < N*N; ++i) {
    int ai = Rand() % N;
    int aj = Rand() % N;
    int bi = Rand() % N;
    int bj = Rand() % N;
    if (ai == bi && aj == bj) continue;
    swap(H[ai][aj], H[bi][bj]);
  }
}
void main() {
  入力を読み込む
  for (int i = 0; i < Q; i++) {
    この時点でのN,Hに対する答えを計算し、出力
    if (i != Q-1) Shuffle();
  }
  return 0;
}

入力例1

5 3
0 7 3 101
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

出力例1

35
27
30

1 第二个测试用例如下。

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

此时,以每个正方形为中心的金字塔的最大高度如下。

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

这些的总和是 35 ,所以输出 1 在线 写在方格 35 。

2 第二个测试用例如下。

2 1 2 1 1
2 1 1 1 1
1 2 1 1 1
2 2 1 1 1
1 2 1 3 2

此时,以每个正方形为中心的金字塔的最大高度如下。

1 1 1 1 1
1 1 1 1 1
1 2 1 1 1
1 2 1 1 1
1 1 1 1 1

这些的总和是 27 ,所以输出 2 在线 写在方格 27 。

3 第二个测试用例如下。

1 1 1 2 1
2 1 1 2 1
1 1 3 1 1
1 2 2 2 2
2 1 1 1 1

此时,以每个正方形为中心的金字塔的最大高度如下。

1 1 1 1 1
1 1 1 2 1
1 1 2 1 1
1 2 2 2 1
1 1 1 1 1

这些的总和是 30 ,所以输出 3 在线 写在方格 30 。