4024 - Matprod

Cerinţa

Se consideră o matrice pătratică A=(ai,j)de ordin n, elementele sale fiind cifre în baza 10. Pentru fiecare element ai,j al matricei definim drumul de la elementul a1,1 la elementul ai,j ca fiind format din elementele: a1,1, a2,1, …, ai,1, ai,2, ai,3, …, ai,j. Pentru fiecare element ai,j al matricei, se cere să se calculeze suma produselor oricăror două elemente situate pe drumul de la elementul a1,1 la elementul ai,j.

Date de intrare

Fișierul de intrare matprod.in conține pe prima linie numărul n, iar pe următoarele n linii câte n cifre separate prin spaţiu, reprezentând elementele matricei A.

Date de ieşire

Dacă datele sunt introduse corect,în fişierul de ieşire matprod.out se va afișa :"Datele sunt introduse corect.",apoi pe un rând va conţine pe primele n linii câte n numere naturale separate prin spaţiu, reprezentând suma cerută pentru fiecare element al matricei.În cazul contrar,se va afișa pe ecran "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

• 2 ⩽ n ⩽ 1000
• elementele matricei A sunt cifre

Exemplu

matprod.in

3

1 2 3

4 5 0

9 3 7

matprod.out

Datele sunt introduse corect.

0 2 11

4 29 29

49 91 210

Explicație

De exemplu, pentru elementul a3,2, drumul este format din 1, 4, 9, 3, iar suma este 1•4+1•9+1•3+4•9+4•3+9•3=91.

Rezolvare

def validare_matrice(matrice):
    n = len(matrice)
    # Verificăm dacă matricea este patratică și dacă fiecare element este un numar întreg pozitiv
    for i in range(n):
        if len(matrice[i]) != n:
            return False
        for j in range(n):
            if not matrice[i][j].isdigit():
                return False
            matrice[i][j] = int(matrice[i][j])
    return True


def calculeaza_suma_produselor(matrice):
    n = len(matrice)
    # Inițializăm două matrici pentru a calcula sumele și produsele
    s = [[0 for j in range(n)] for i in range(n)]
    b = [[0 for j in range(n)] for i in range(n)]

    # Calculăm sumele parțiale ale matricei
    s[0][0] = matrice[0][0]
    for i in range(1, n):
        s[i][0] = s[i-1][0] + matrice[i][0]
    for j in range(1, n):
        s[0][j] = s[0][j-1] + matrice[0][j]
    for i in range(1, n):
        for j in range(1, n):
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + matrice[i][j]

    # Calculăm suma produselor pentru fiecare element al matricei
    b[0][0] = 0
    for i in range(1, n):
        b[i][0] = b[i-1][0] + s[i-1][0] * matrice[i][0]
    for j in range(1, n):
        b[0][j] = b[0][j-1] + s[0][j-1] * matrice[0][j]
    for i in range(1, n):
        for j in range(1, n):
            b[i][j] = b[i][j-1] + (s[i][j-1] - s[i-1][j-1] + s[i-1][0]) * matrice[i][j]

    return b


if __name__ == '__main__':
    # Citim datele de intrare din fișier
    with open('matprod.in', 'r') as f:
        n = int(f.readline())
        matrice = [f.readline().split() for _ in range(n)]

    # Validăm matricea
    if not validare_matrice(matrice):
        # Dacă matricea nu este validă, afișăm o eroare in fișierul de ieșire și ieșim din program
        with open('matprod.out', 'w') as f:
            f.write("Datele nu corespund restricțiilor impuse.")
    else:
        # Daca matricea este validă, calculăm suma produselor și o afisam în fișierul de ieșire
        rezultat = calculeaza_suma_produselor(matrice)

        with open('matprod.out', 'w') as f:
            f.write("Datele sunt introduse corect.\n")
            for i in range(n):
                f.write(' '.join(str(x) for x in rezultat[i]) + '\n')