Vizualizare sursă pentru „1323 - Matrice Rara”

== Cerința ==
Se citesc două matrice rare și se cere să se calculeze suma lor.
O matrice '''A(n,m)''' se numește rară dacă majoritatea elementelor sale sunt egale cu zero (cel puţin jumătate). Datorită numărului mic de numere nenule, o matrice rară '''A(n,m)''', având '''k''' elemente nenule, poate fi memorată folosind un șir '''X''' conţinând '''k''' triplete de forma '''(linie, coloană , valoare)''', corespunzătoare valorilor nenule ale matricei. Elementele șirului '''X''' se memorează în ordine lexicografică după '''(linie,coloana)'''.
De exemplu matricea cu '''n = m = 3'''
: 1 0 2
: 0 0 5
: 0 2 0
se va memora sub forma sirului '''X''' continand '''4''' triplete : '''{(1,1,1) , (1,3,2) , (2,3,5) , (3,2,2)}'''.
== Date de intrare ==
Fișierul de intrare '''matrice_rarain.txt''' conține pe prima linie , dimensiunile celor două matrice '''n m''' – reprezentând numărul de linii şi coloane, şi '''N1 N2''', numărul de elemente nenule ale matricei '''A''', respectiv matricei '''B'''. Apoi următoarele '''N1''' linii vor conține triplete – elementele nenule ale matricei A în ordine lexicografică, iar ultimele N2 linii vor conține triplete reprezentând elementele nenule ale matricei '''B''', tot în ordine lexicografică .
== Date de ieșire ==
Fișierul de ieșire '''matrice_raraout.txt''' va conține pe prima linie numărul de elemente diferite de '''0''' din matricea sumă '''C''' şi apoi matricea în sine sub forma tripletelor în ordine lexicografică, câte unul pe o linie .
== Restricții și precizări ==
* '''1 ≤ n , m ≤ 1.000.000'''
* '''1 ≤ N1 , N2 ≤ 300.000'''
* '''-1.000.000.000 ≤ A[i][j], B[i][j] ≤ 1.000.000.000'''
== Exemplul 1 ==
; matrice_rarain.txt
: 5 6 3 3
: 1 1 2
: 3 4 3
: 4 6 1
: 1 2 3
: 3 4 -2
: 4 6 2
; matrice_raraout.txt
: Datele introduse corespund restricțiilor impuse.
: 4
: 1 1 2
: 1 2 3
: 3 4 1
: 4 6 3
== Exemplul 2 ==
; matrice_rarain.txt
: 1000001 6 3 3
: 1 1 2
: 3 4 3
: 4 6 1
: 1 2 3
: 3 4 -2
: 4 6 2
; matrice_raraout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 1323 - Matrice Rara
def validare(matrice_a1, matrice_b1):           # functia de validare a datelor de intrare
    for matrice in [matrice_a1, matrice_b1]:
        if len(matrice) > 1000000:
            raise ValueError

        for element in matrice:
            if element[2] < -1000000000 or element[2] > 1000000000:
                raise ValueError

    fisier_iesire.write("Datele introduse corespund restrictiilor impuse.\n")


def suma_matrici(matrice_a1, matrice_b1):                     # functia de rezolvare
    suma = {}
    for element in matrice_a1 + matrice_b1:
        if (element[0], element[1]) not in suma:
            suma[(element[0], element[1])] = 0
        suma[(element[0], element[1])] += element[2]

    matrice_suma1 = [(k[0], k[1], v) for k, v in suma.items() if v != 0]
    matrice_suma1.sort()

    return matrice_suma1


if __name__ == '__main__':
    fisier_intrare = open("matrice_rarain.txt", "r")         # declararea fisierelor
    fisier_iesire = open("matrice_raraout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        n, m, N1, N2 = map(int, fisier_intrare.readline().split())
        matrice_a = [list(map(int, fisier_intrare.readline().split())) for _ in range(N1)]
        matrice_b = [list(map(int, fisier_intrare.readline().split())) for _ in range(N2)]

        validare(matrice_a, matrice_b)                 # apelul functiei de validare

        matrice_suma = suma_matrici(matrice_a, matrice_b)               # apelul functiei de rezolvare
        fisier_iesire.write(f"{len(matrice_suma)}\n")
        for elem in matrice_suma:
            fisier_iesire.write(f"{elem[0]} {elem[1]} {elem[2]}\n")

    except ValueError:
        fisier_iesire.write("Datele introduse nu corespund restrictiilor impuse.")
    except IndexError:
        fisier_iesire.write("Datele introduse nu corespund restrictiilor impuse.")

</syntaxhighlight>