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 666x−x79+12x191 corresponds to the vector
0 | 1 | 2 |
666 : 1 | −1 : 79 | 12 : 191 |
The following declarations allow us to define polynomials as described:
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.
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