Grille Magnifique!#12209

Grille Magnifique! (Corrigé)

Auteur du problème:	Hasan Saleh (MathModel)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution

Calculez la somme de chaque grille et colonne en $O (n^{2})$ \mathcal{O}(n^2) et mappez-les avec une $map$ , puis pour chaque diagonale, vérifiez toutes les sommes de sous-tableaux de chaque diagonale et vérifiez si elles ont déjà été calculées dans $map$ . Cela peut être fait avec une somme préfixe ou simplement en mettant à jour les sommes et en les stockant lors du calcul.

def solve():
    n=int(input())
    a = [[0]*n for _ in range(n)]
    mp={}
    for i in range(n):
        a[i]=list(map(int,input().split()))
    for i in range(n):
        sum,sum2=0,0
        for j in range(n):
            sum+=a[i][j]
            sum2+=a[j][i]
        mp[sum]=1
        mp[sum2]=1
    d1,d2=[],[]
    sd1,sd2=0,0
    for i in range(n):
        sd1+=a[i][i]
        sd2+=a[i][n-i-1]
        d1+=[sd1]
        d2+=[sd2]
    for i in range(n):
        for j in range(i,n):
            try:
                if(mp[d1[j]-d1[i]+a[i][i]]):
                    print("OUI")
                    return
            except:
                pass
            try:
                if(mp[d2[j]-d2[i]+a[i][n-i-1]]):
                    print("OUI")
                    return
            except:
                pass
    print("NON")
for _ in range(int(input())):
    solve()

Complexité $O (n^{2})$ \mathcal{O}(n^2)