Sum of polynomials P70952


Statement
 

pdf   zip

thehtml

Here we consider sums of polynomials with integer coefficients. For instance, the sum of 12+2x−15x2+4x3 and −1−3x+15x2−2x4 is 11−x+4x3−2x4.

We represent the polynomials with vectors of pairs, with the coefficient and the exponent of a monomial, whenever the coefficient is not zero. The vector is sorted in increasing order by the exponents.

For instance, the polynomial 12+2x−15x2+4x3 corresponds to the vector

||
   0   1   2   3
||
||
  12 ‍: ‍0   2 ‍: ‍1 −15 ‍: ‍2   4 ‍: ‍3
||

and the polynomial 666xx79+12x191 corresponds to the vector

||
   0   1   2
||
||
  666 ‍: ‍1 −1 ‍: ‍79   12 ‍: ‍191
||

The following declarations allow us to define polynomials as described:

int coef; // coefficient int expo; // exponent }; typedef vector<Pair> Polynomial; // sorted by exponent

Using these definitions, implement the function

that returns the sum of two given polynomials p and q.

Observation

The main program is already implemented: do not modify it. First, it reads a number t. Afterwards, it reads t pairs of polynomials, adds them up and prints the result.

#include <vector> using namespace std; struct Pair { int coef; int expo; }; typedef vector<Pair> Polynomial; Polynomial sum(const Polynomial& p, const Polynomial& q) { } void read(Polynomial& p) { int n; cin >> n; p = Polynomial(n); char c; for (int i = 0; i < n; ++i) cin >> p[i].coef >> c >> p[i].expo; } void print(const Polynomial& 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) { Polynomial p, q; read(p); read(q); Polynomial r = sum(p, q); print(r); } }
Public test cases
  • Input

    10
    
    4 12:0 2:1 -15:2 4:3
    4 -1:0 -3:1 15:2 -2:4
    
    4 3:1 8:4 -3:7 5:8
    4 3:1 8:4 -3:7 5:8
    
    3 4:0 8:5 6:6
    2 3:0 -6:6
    
    2 3:0 -6:6
    3 4:0 8:5 6:6
    
    3 2:3 3:18 5:21
    3 2:3 -3:18 -5:21
    
    1 1:1000000000
    1 1000000000:1
    
    0
    0
    
    1 999:666
    0
    
    0
    1 999:666
    
    1 -999:666
    1 999:666
    

    Output

    4 11:0 -1:1 4:3 -2:4
    4 6:1 16:4 -6:7 10:8
    2 7:0 8:5
    2 7:0 8:5
    1 4:3
    2 1000000000:1 1:1000000000
    0
    1 999:666
    1 999:666
    0
    
  • Information
    Author
    Professors de P1
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++