Олимпиадный тренинг

Задача . F. Волшебная матрица


Задача

Темы: графы Деревья матрицы Перебор разделяй и властвуй *2400

Вам задана матрица 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".


Примеры
№Входные данныеВыходные данные
1 3
0 1 2
1 0 2
2 2 0 
MAGIC
2 2
0 1
2 3 
NOT MAGIC
3 4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0 
NOT MAGIC

time 5000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет