Educational Codeforces Round 9 |
---|
Закончено |
Вам задана матрица A размера n × n.
Будем называть матрицу с неотрицательными элементами волшебной, если она симметрична (то есть aij = aji), aii = 0 и aij ≤ max(aik, ajk) для всех троек i, j, k. Заметим, что i, j, k не обязательно различны.
Определите является ли матрица волшебной.
Рекомендуется для ввода и вывода данных использовать функции scanf, printf в языке C++, поскольку они работают значительно быстрее чем cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.
В первой строке находится целое число n (1 ≤ n ≤ 2500) — размер матрицы A.
В каждой из следующих n строк находится n целых чисел aij (0 ≤ aij < 109) — элементы матрицы A.
Заметим, что заданная матрица не обязательно является симметричной и может быть произвольной.
Выведите ''MAGIC" (без кавычек) если матрица A является магической. В противном случае выведите ''NOT MAGIC".
3
0 1 2
1 0 2
2 2 0
MAGIC
2
0 1
2 3
NOT MAGIC
4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
NOT MAGIC
Название |
---|