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_rara.in 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_rara.out 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

Exemplu

matrice_rara.in

matrice_rara.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Matrice_Rara:

//varianta de 20p
#include <fstream>

using namespace std ;

ifstream f ("matrice_rara.in") ;
ofstream g ("matrice_rara.out") ;

int c[2005][2005] ;
int n , m , p , q , N1 , N2 , N3 , c_linie , c_coloana ;

int main ()
{
 f >> n >> m >> N1 >> N2 ;
 for ( int cnt = 1 ; cnt <= N1 ; ++cnt )
    {
     int x , y , v ;
     f >> x >> y >> v ;
     c[x][y] = c[x][y] + v ;
     ++N3 ;
    }
 for ( int cnt = 1 ; cnt <= N2 ; ++cnt )
    {
     int x , y , v ;
     f >> x >> y >> v ;
     if ( c[x][y] == 0 )
        ++N3 ;
     c[x][y] = c[x][y] + v ;
     if ( c[x][y] == 0 )
        --N3 ;
    }
 c_linie = max ( n , p ) ;
 c_coloana = max ( m , q ) ;
 g << N3 << "\n" ;
 for ( int i = 1 ; i <= c_linie ; ++i )
    {
     for ( int j = 1 ; j <= c_coloana ; ++j )
        if ( c[i][j] != 0 )
            g << i << " " << j << " " << c[i][j] << "\n" ;
    }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1323 Matrice_Rara

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1323 Matrice_Rara de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1323 Matrice_Rara