← 返回题目列表

Codeforces · 1004/D

D. 索尼娅和矩阵

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

由于 Sonya 刚刚学习了矩阵的基础知识,她决定稍微玩一下它们。

索尼娅想象了一种新型矩阵,她称之为菱形矩阵。这些矩阵恰好有一个零,而所有其他单元都具有到包含零的单元的曼哈顿距离。数量相等的细胞呈菱形,这就是索尼娅如此称呼这种类型的原因。

两个像元 ($$$x_1$$$, $$$y_1$$$) 和 ($$$x_2$$$, $$$y_2$$$) 之间的曼哈顿距离定义为 $$$|x_1 - x_2| + |y_1 - y_2|$$$。例如,像元 $$$(5, 2)$$$ 和 $$$(7, 1)$$$ 之间的曼哈顿距离等于 $$$|5-7|+|2-1|=3$$$。

菱形矩阵的示例。

请注意,菱形矩阵由 $$$n$$$、$$$m$$$ 以及包含零的单元格的坐标唯一定义。

她画了一个 $$$n\times m$$$ 菱形矩阵。她认为,如果她只以某种任意顺序(即 $$$n\cdot m$$$ 数字的序列)为您提供该矩阵的元素,您就无法重新创建该矩阵。请注意,Sonya 不会给您 $$$n$$$ 和 $$$m$$$,因此您只能使用此矩阵中的数字序列。

编写一个程序,找到这样一个 $$$n\times m$$$ 菱形矩阵,其元素与序列中的元素按某种顺序相同。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^6$$$) — 矩阵中的单元格数量。

第二行包含 $$$t$$$ 整数 $$$a_1, a_2, \ldots, a_t$$$ ($$$0\leq a_i< t$$$) - 单元格中的值以任意顺序排列。

输出

在第一行中,打印两个正整数 $$$n$$$ 和 $$$m$$$ ($$$n \times m = t$$$) — 矩阵的大小。

在第二行中,打印两个整数 $$$x$$$ 和 $$$y$$$ ($$$1\leq x\leq n$$$, $$$1\leq y\leq m$$$)——$$0$$$ 所在单元格所在的行号和列号。

如果有多个可能的答案,请打印其中任何一个。如果无解,则打印单个整数 $$$-1$$$。

示例

输入 #1

20
1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4

输出 #1

4 5
2 2

输入 #2

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

输出 #2

3 6
2 3

输入 #3

6
2 1 0 2 1 2

输出 #3

-1

注意

您可以在图例中看到第一个示例的解决方案。您还可以选择单元格 $$$(2, 2)$$$ 作为 $$$0$$$ 所在的单元格。您还可以选择 $$$5\times 4$$$ 矩阵,在 $$$(4, 2)$$$ 处为零。

在第二个示例中,有一个 $$$3\times 6$$$ 矩阵,其中零位于 $$$(2, 3)$$$ 处。

在第三个示例中,不存在解。