← 返回题目列表

Codeforces · 711/B

B. 克里斯和魔方

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

编码员ZS和狒狒克里斯抵达乌代兰入口。入口处有一个n×n的魔法网格,里面填满了整数。 Chris 注意到网格中正好有一个单元格是空的,要进入 Udayland,他们需要在空单元格中填充一个正整数。

Chris 尝试填写随机数,但没有成功。 ZS 编码员意识到他们需要填写一个正整数,以便网格中的数字形成一个幻方。这意味着他必须填写一个正整数,以便网格的每一行 ($$\sum_{r,i}a_{r,i}$$)、网格的每一列 ($$\sum_{i,c}a_{i,c}$$) 以及网格的两条长对角线(主对角线 — $$\sum_{i}a_{i,i}$$ 和次对角线 — $$\sum_{i}a_{i,n-i+1}$$) 相等。

Chris 不知道要填写什么数字,你能帮 Chris 找到正确的正整数来填写或者判断不可能吗?

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 500) — 魔法网格的行数和列数。

接下来有 ​​n 行,每行包含 n 个整数。其中第i个中的第j个数字表示ai,j(1≤ai,j≤109或ai,j=0),魔格第i行j列的数字。如果对应的单元格为空,则ai,j将等于0。否则,ai,j为正。

保证恰好存在一对整数 i, j (1 ≤ i, j ≤ n) 使得 ai, j = 0。

输出

输出一个整数,即正整数 x (1 ≤ x ≤ 1018),该正整数 x (1 ≤ x ≤ 1018) 应该被填充到空单元格中,使整个网格成为一个幻方。如果这样的正整数x不存在,则输出-1。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

3
4 0 2
3 5 7
8 1 6

输出 #1

9

输入 #2

4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1

输出 #2

1

输入 #3

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

输出 #3

-1

注意

在第一个示例案例中,我们可以将 9 填充到空单元格中,使生成的网格成为幻方。确实,

每行的数字总和为:

4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.

每列中的数字总和为:

4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.

两条对角线上的数字之和为:

4 + 5 + 6 = 2 + 5 + 8 = 15.

在第三个示例案例中,不可能在空方格中填充数字以使生成的网格成为幻方。