Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-d.html
2009 ACM ICPC Asia Manila
October 22 – 23, 2009
Problem D: ‘Composition of Polynomials’
Input file: d.in
Output file: stdout
Execution time limit: 15 seconds
Given two polynomials, p(x) of degree M, and q(x) of degree N, both with integer coefficients, your problem is to write a computer program that prints the coefficients of the composition polynomial f(x) = p(q(x)).
For example, if p(x) = 2x^3 + 5x – 4 and q(x) = 3x^2 – 4x + 1, then f(x) = p(q(x)) = 2(3x^2 – 4x + 1)^3 + 5( 3x^2 – 4x + 1) – 4 = 54x^6 – 216x^5 + 342x^4 – 272x^3 + 129x^2 – 44x + 3
INPUT. Input shall consist of several data sets. Each data set will be given in three lines of input. The first line will give the values of M and N, separated by one or more spaces. The second line will give the coefficients of each term of p(x), separated by one or more spaces, and arranged in increasing powers of x. The third line will give the coefficients of each term of q(x), separated by one or more spaces, and arranged in increasing powers of x. Both M and N will be between 0 and 10, inclusive. Each coefficient will be small, in the range -20 to 20 inclusive, but a small value raised to 10th power is not guaranteed to be a small integer. Input for the next data set will immediately follow that of the previous data set. An input of M = 0 and N = 0 will signify the end of input data.
-4 5 0 2
1 -4 3
-7 0 2
5 3 2
For each data set, print one line of output of the form:“Data set N: <composition polynomial>
where N is the data set number, starting from 1, and <composition polynomial>
OUTPUT FOR SAMPLE INPUT
Data set 1: 54x^6–216x^5+342x^4–272x^3+129x^2–44x+3
Data set 2: 8x^4+24x^3+58x^2+60x+43
(Acknowledgment: This problem was contributed by Dr. Pablo Manalastas, Ateneo de Manila University).