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">

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>