CF632F.Magic Matrix

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You're given a matrix $A$ of size $n×n$ .

Let's call the matrix with nonnegative elements magic if it is symmetric (so $a_{ij}=a_{ji}$ ), $a_{ii}=0$ and $a_{ij}<=max(a_{ik},a_{jk})$ for all triples $i,j,k$ . Note that $i,j,k$ do not need to be distinct.

Determine if the matrix is magic.

As the input/output can reach very huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

输入格式

The first line contains integer $n$ ( $1<=n<=2500$ ) — the size of the matrix $A$ .

Each of the next $n$ lines contains $n$ integers $a_{ij}$ ( 0<=a_{ij}<10^{9} ) — the elements of the matrix $A$ .

Note that the given matrix not necessarily is symmetric and can be arbitrary.

输出格式

Print ''MAGIC" (without quotes) if the given matrix $A$ is magic. Otherwise print ''NOT MAGIC".

输入输出样例

输入#1
```
3
0 1 2
1 0 2
2 2 0
```
输出#1
```
MAGIC
```
输入#2
```
2
0 1
2 3
```
输出#2
```
NOT MAGIC
```

输入#3

输出#3

NOT MAGIC

首页