PAT 1002

1002. A+B for Polynomials (25)

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

Input

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

For each test case you should output the sum 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 to 1 decimal place.

Sample Input

2 1 2.4 0 3.2 2 2 1.5 1 0.5 

Sample Output

3 2 1.5 1 2.9 0 3.2 

注意对相加后系数为0的处理。

代码

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int k1,k2;
 6     double d_arr1[10],d_arr2[10],d_arr3[20];
 7     int i_arr1[10],i_arr2[10],i_arr3[20];
 8     int i,j,k;
 9     while(scanf("%d",&k1) != EOF){
10         for(i=0;i<k1;++i)
11             scanf("%d%lf",&i_arr1[i],&d_arr1[i]);
12         scanf("%d",&k2);
13         for(i=0;i<k2;++i)
14             scanf("%d%lf",&i_arr2[i],&d_arr2[i]);
15         i = 0;
16         j = 0;
17         k = 0;
18         while(i < k1 && j < k2){
19             if (i_arr1[i] == i_arr2[j]){
20                 i_arr3[k] = i_arr1[i];
21                 d_arr3[k] = d_arr1[i++] + d_arr2[j++];
22                 if (d_arr3[k] != 0.0)
23                     ++k;
24             }
25             else if (i_arr1[i] > i_arr2[j]){
26                 i_arr3[k] = i_arr1[i];
27                 d_arr3[k++] = d_arr1[i++];
28             }
29             else{
30                 i_arr3[k] = i_arr2[j];
31                 d_arr3[k++] = d_arr2[j++];
32             }
33             
34         }
35         for (;i<k1;++i){
36             i_arr3[k] = i_arr1[i];
37             d_arr3[k++] = d_arr1[i];
38         }
39         for (;j<k2;++j){
40             i_arr3[k] = i_arr2[j];
41             d_arr3[k++] = d_arr2[j];
42         }
43         printf("%d",k);
44         for(i=0;i<k;++i){
45             printf(" %d %.1f",i_arr3[i],d_arr3[i]);
46         }
47         printf("
");
48     }
49     return 0;
50     
51 }