#include <stdio.h>

#define MAX 20

typedef struct {
    int coef;   // 계수
    int exp;    // 지수
} Term;

typedef struct {
    Term term[MAX];
    int count;          // 현재 항의 개수
} Polynomial;


/* 빈 다항식 만들기 */
Polynomial Zero(void)
{
    Polynomial p;
    p.count = 0;
    return p;
}


/* 다항식이 비어 있는지 검사 */
int IsZero(Polynomial p)
{
    return p.count == 0;
}


/* 현재 최고차항의 지수 */
int Lead_Exp(Polynomial p)
{
    return p.term[0].exp;
}


/* 현재 최고차항의 계수 */
int Coef(Polynomial p, int exp)
{
    return p.term[0].coef;
}


/* 두 지수 비교 */
int COMPARE(int a, int b)
{
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}


/* 다항식 마지막에 항 추가 */
Polynomial Attach(Polynomial p, int coef, int exp)
{
    p.term[p.count].coef = coef;
    p.term[p.count].exp = exp;
    p.count++;

    return p;
}


/* 현재 맨 앞 항 제거 */
Polynomial Remove(Polynomial p, int exp)
{
    int i;

    for (i = 0; i < p.count - 1; i++)
        p.term[i] = p.term[i + 1];

    p.count--;

    return p;
}


/* 다항식 덧셈 */
Polynomial Add(Polynomial a, Polynomial b)
{
    Polynomial d = Zero();
    int sum;

    while (!IsZero(a) && !IsZero(b)) {

        switch (COMPARE(Lead_Exp(a), Lead_Exp(b))) {

        case -1:
            d = Attach(d,
                       Coef(b, Lead_Exp(b)),
                       Lead_Exp(b));

            b = Remove(b, Lead_Exp(b));
            break;


        case 0:
            sum = Coef(a, Lead_Exp(a))
                + Coef(b, Lead_Exp(b));

            if (sum != 0)
                d = Attach(d, sum, Lead_Exp(a));

            a = Remove(a, Lead_Exp(a));
            b = Remove(b, Lead_Exp(b));
            break;


        case 1:
            d = Attach(d,
                       Coef(a, Lead_Exp(a)),
                       Lead_Exp(a));

            a = Remove(a, Lead_Exp(a));
            break;
        }
    }


    /* a에 남은 항 처리 */
    while (!IsZero(a)) {
        d = Attach(d,
                   Coef(a, Lead_Exp(a)),
                   Lead_Exp(a));

        a = Remove(a, Lead_Exp(a));
    }


    /* b에 남은 항 처리 */
    while (!IsZero(b)) {
        d = Attach(d,
                   Coef(b, Lead_Exp(b)),
                   Lead_Exp(b));

        b = Remove(b, Lead_Exp(b));
    }

    return d;
}


int main(void)
{
    Polynomial a = Zero();
    Polynomial b = Zero();
    Polynomial d;
    int i;

    /* A(x) = 2x^1000 + 1 */
    a = Attach(a, 2, 1000);
    a = Attach(a, 1, 0);

    /* B(x) = x^4 + 10x^3 + 3x^2 + 1 */
    b = Attach(b, 1, 4);
    b = Attach(b, 10, 3);
    b = Attach(b, 3, 2);
    b = Attach(b, 1, 0);

    d = Add(a, b);

    for (i = 0; i < d.count; i++)
        printf("%dx^%d ", d.term[i].coef, d.term[i].exp);

    return 0;
}