Sum of polynomials P70952

Statement

thehtml

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

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−15x²+4x³ corresponds to the vector

||
||

12 ‍: ‍0

2 ‍: ‍1

−15 ‍: ‍2

4 ‍: ‍3

and the polynomial 666x−x⁷⁹+12x¹⁹¹ corresponds to the vector

||
||

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