問題文
八神酱的繁荣是金字塔。
八神酱厌倦了由球形石头制成的金字塔,所以这一次 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 。