| ABBYY Cup 2.0 - Hard |
|---|
| Закончено |
Умный Бобер из ABBYY очень любит различные головоломки. Одной из самых его любимых головоломок являются магические квадраты. Совсем недавно ему пришла в голову идея по автоматизации решения данной головоломки. Бобер решил обратиться с этой задачей к участникам ABBYY Cup'а.
Магический квадрат представляет собой матрицу размера n × n. Элементами этой матрицы являются целые числа. Сумма чисел в каждой из строк матрицы равна некоторому числу s. Сумма чисел в каждом из столбцов матрицы также равна числу s. Кроме этого, сумма элементов на главной диагонали равна s и сумма элементов на побочной диагонали равна s. Примеры магических квадратов приведены на следующем рисунке:
Магические квадраты Вам дан набор из n2 целых чисел ai. Требуется расположить эти числа в квадратной матрице размера n × n таким образом, чтобы они образовывали магический квадрат. Заметим, что каждое число должно встречаться в матрице ровно столько раз, сколько раз оно встречается в исходном наборе.
Гарантируется, что решение существует!
Первая строка входных данных содержит единственное целое число n. Следующая строка содержит n2 целых чисел ai ( - 108 ≤ ai ≤ 108), разделенных единичными пробелами.
Ограничения на входные данные для получения 20 баллов:
- 1 ≤ n ≤ 3
Ограничения на входные данные для получения 50 баллов:
- 1 ≤ n ≤ 4
- Гарантируется, что среди ai не более 9 различных чисел.
Ограничения на входные данные для получения 100 баллов:
- 1 ≤ n ≤ 4
Первая строка выходных данных должна содержать целое число s. В следующих n строках выведите по n целых чисел, разделенных пробелами и описывающих полученный магический квадрат. В выведенном магическом квадрате сумма в строках, столбцах и диагоналях должна быть равна s. Если решений несколько, разрешается выводить любое.
3
1 2 3 4 5 6 7 8 9
15
2 7 6
9 5 1
4 3 8
3
1 0 -1 0 2 -1 -2 0 1
0
1 0 -1
-2 0 2
1 0 -1
2
5 5 5 5
10
5 5
5 5
