Zmicala Narcis: Pagină nouă: == 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. Elemente...

2024-01-03T13:04:47Z

Pagină nouă: == 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. Elemente...

New page

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

1323 - Matrice Rara - Revision history