Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Sum of polynomials P70952

Statement

html

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