Un Pătrat Magic este un pătrat ce conține numerele de la 1 la n 2 în care sumele fiecăror linii, coloane și a celor două diagonale sunt egale. Această sumă se mai numește și constanta pătratului magic.

Cerința

Se dă un număr natural n, urmat de o matrice pătratică cu n * n elemente, numere naturale. Să se verifice dacă matricea dată este un pătrat magic.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n * n numere naturale, reprezentând elementele matricei.

Date de ieșire

Programul va afișa pe ecran true dacă matricea dată este un pătrat magic sau false dacă nu este.

Restricții și precizări

• 3 ≤ n ≤ 500
• cele n numere citite vor fi mai mici sau egale decât 250.000

Exemplu

Intrare

3
4 9 2 
3 5 7 
8 1 6 

Ieșire

true

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n , a[501][501] , sc1 = 0 , sc2 = 0 , f[250001] = {0};
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            cin >> a[i][j];
            f[a[i][j]]++;
            if(a[i][j] > n * n) {cout << "false";return 0;}
            if(f[a[i][j]] > 1) {cout << "false";return 0;}
            if(i == j) sc1 += a[i][j];
            if(i + j == n + 1) sc2 += a[i][j];
        }
    }
    for(int i = 1 ; i <= n * n ; i++)
        if(f[i] == 0) {cout << "false";return 0;}
    if(sc1 != sc2) cout << "false";
    else
    {
        for(int i = 1 ; i <= n ; i++)
        {
            int s = 0;
            for(int j = 1 ; j <= n ; j++)
                s += a[i][j];
            if(s != sc1)
            {
                cout << "false";
                return 0;
            }
        }
        for(int i = 1 ; i <= n ; i++)
        {
            int s = 0;
            for(int j = 1 ; j <= n ; j++)
                s += a[j][i];
            if(s != sc1)
            {
                cout << "false";
                return 0;
            }
        }
        cout << "true";
    }
    return 0;
}