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

# 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.")