View source for 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 &les; n &les; 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 ==
<syntaxhighlight lang="python" line>

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')




</syntaxhighlight>