1009. Product of Polynomials

1009. Product of Polynomials (25)

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < ... < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 
 6 int main()
 7 {
 8     double a[1010] = {}, b[1010] = {}, ans[2010] = {};
 9     int ka, kb, i, j, x, y, maxa, maxb;
10     scanf("%d", &ka);
11     scanf("%d", &x);
12     scanf("%lf", &a[x]);
13     maxa = x;
14     for(i = 1; i < ka; i++)
15     {
16         scanf("%d", &x);
17         scanf("%lf", &a[x]);
18     }
19     scanf("%d", &kb);
20     scanf("%d", &y);
21     scanf("%lf", &b[y]);
22     maxb = y;
23     for(i = 1; i < kb; i++)
24     {
25         scanf("%d", &y);
26         scanf("%lf", &b[y]);
27     }
28     int max = 0;
29     if(maxa > maxb)
30     {
31         for(i = maxa; i >= 0; i--)
32         {
33             for(j = maxb; j >= 0; j--)
34             {
35                 ans[i + j] += a[i] * b[j];
36                 if((i + j) > max)
37                 {
38                     max = i + j;
39                 }
40             }
41         }
42     }
43     else
44     {
45         for(i = maxb; i >= 0; i--)
46         {
47             for(j = maxa; j >= 0; j--)
48             {
49                 ans[i + j] += b[i] * a[j];
50                 if((i + j) > max)
51                 {
52                     max = i + j;
53                 }
54             }
55         }
56     }
57     int count = 0;
58     for(i = max; i >= 0; i--)
59     {
60         if(ans[i] != 0)
61             count++;
62     }
63     printf("%d", count);
64     for(i = max; i >= 0; i--)
65     {
66         if(ans[i] != 0)
67         {
68             printf(" %d %.1f", i, ans[i]);
69         }
70     }
71     printf("
");
72     return 0;
73 }