Suma de polinomis P70952

En aquest exercici considerem sumes de polinomis amb coeficients enters. Per exemple, la suma de $12+2x-15x^2+4x^3$ amb $-1-3x+15x^2-2x^4$ és $11-x+4x^3-2x^4$.

Representem els polinomis amb vectors de parells, cadascun amb el coeficient i l’exponent d’un monomi, sempre que el coeficient no sigui zero. El vector es troba ordenat segons els exponents, de petit a gran.

Per exemple, el polinomi $12+2x-15x^2+4x^3$ es correspon al vector

i el polinomi $666x-x^{79}+12x^{191}$ es correspon al vector

Les declaracions següents permeten definir polinomis tal com s’ha descrit:

    struct Parell {
        int coef;                           // coeficient
        int expo;                           // exponent
    };

    typedef vector<Parell> Polinomi;        // ordenat per exponent

Utilitzant aquestes definicions, implementeu la funció

    Polinomi suma(const Polinomi& p, const Polinomi& q); 

que retorna la suma de dos polinomis @p@ i @q@ donats.

Observació

El programa principal ja se us dóna implementat; no el canvieu. Aquest llegeix primer un natural @t@. Després llegeix @t@ parelles de polinomis, les suma i n’escriu el resultat.

#include <iostream>
#include <vector>
using namespace std;


struct Parell {
    int coef;
    int expo;
};


typedef vector<Parell> Polinomi;


Polinomi suma(const Polinomi& p, const Polinomi& q) {
}


void llegeix(Polinomi& p) {
    int n;
    cin >> n;
    p = Polinomi(n);
    char c;
    for (int i = 0; i < n; ++i) cin >> p[i].coef >> c >> p[i].expo;
}


void escriu(const Polinomi& p) {
    int n = p.size();
    cout << n;
    for (int i = 0; i < n; ++i) cout << " " << p[i].coef << ":" << p[i].expo;
    cout << endl;
}


int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        Polinomi p, q;
        llegeix(p);
        llegeix(q);
        Polinomi r = suma(p, q);
        escriu(r);
    }
}