{
This program is also distributable under the GPL 2.0 or later,
It does the multiplication of 2 (two) polynomes
slovak comment follows :)

Nepouziva to mozno ten uplne najgenialnejsi algoritmus,
ale robi to to, co ma. Inak je ten program trochu dlhy, ale hlavna
myslienka je asi tak na 20 riadkov :)
}

program nasobenie_polynomov;

type pitem=^item;
     item=record
	e: integer;
        a: integer; {moze byt aj real, nothin' changes ;-)}
	next: pitem;
end;

var a, b, c: pitem;

{haluz - vytvorenie polynomu :)}
procedure init_p(var x: pitem; n, a1, a2, a3, a4: integer);
var f: pitem;
begin
        new(x);
        x^.e:=n;
        x^.a:=a1;
        x^.next:=nil;
        f:=x;

        if (n>0) then begin
        	new(x^.next);
                x:=x^.next;
        	x^.e:=n-1;
	        x^.a:=a2;
	        x^.next:=nil;
        end;

        if (n>1) then begin
        	new(x^.next);
                x:=x^.next;
        	x^.e:=n-2;
	        x^.a:=a3;
	        x^.next:=nil;
        end;

        if (n>2) then begin
        	new(x^.next);
                x:=x^.next;
        	x^.e:=n-3;
	        x^.a:=a4;
	        x^.next:=nil;
        end;
        x:=f;
end;

{haluz - vypisanie polynomu :)}
procedure print_p(x: pitem);
begin
	while (x<>nil) do begin
        	write(x^.a:2, '*x^', x^.e:2);
                if (x^.next<>nil) then
                	write(' + ');
                x:=x^.next;
        end;
        writeln;
end;

{scitanie 2 polynomov... 'Honzova metoda' :o) }
function p_plus_p(p, q: pitem):pitem;
var zac, act: pitem;
    e: integer;
begin
	zac:=nil;
        while (p<>nil) or (q<>nil) do begin
        	if zac=nil then begin
                	new(zac); act:=zac;
                end else begin
                	new(act^.next);
                        act:=act^.next;
                end;

                e:=0;
                if (p<>nil) and (p^.e>e) then
                	e:=p^.e;
                if (q<>nil) and (q^.e>e) then
                	e:=q^.e;
                act^.a:=0;
                act^.e:=e;
                if (p<>niL) and (p^.e=e) then begin
                	act^.a:=act^.a+p^.a;
                        p:=p^.next;
                end;
                if (q<>nil) and (q^.e=e) then begin
                	act^.a:=act^.a+q^.a;
                        q:=q^.next;
                end;
        end;
        p_plus_p:=zac;
        act^.next:=nil;
end;

{vrati kopiu polynomu a}
function copy_p(a: pitem):pitem;
var n, n1, nf: pitem;
begin
	new(n);
	n^:=a^;
        nf:=n;

	while (n^.next<>nil) do begin
        	n1:=n^.next;
                new(n^.next);
                n:=n^.next;
                n^:=n1^;
        end;
        copy_p:=nf;
end;

{vymaze polynom, hmm}
procedure destroy_p(a: pitem);
var n: pitem;
begin
	while (a<>nil) do begin
        	n:=a^.next;
                dispose(a);
		a:=n;
        end;
end;

{
nasobenie 2 polynomov, brute force postup (tipujem minimalne O(n^2), mozno aj O(n^3):
vynasobi cely polynom - postupne s b[0], b[1]...az...b[n], stale to scitava
a vysledok vrati...

asi by to slo aj rychlejsie,
ale snad mi z toho par bodov kvapne?! :o)
}
function p_times_p(a, b: pitem):pitem;
var rp, rp1, n, n1, n2: pitem;
begin
	n2:=b;

        {navratovy rP bude na zaciatku 0x^0}
        new(rp);
        rp^.e:=0;
        rp^.a:=0;
        rp^.next:=nil;

        while (n2<>nil) do begin
		n:=copy_p(a);
                n1:=n;
                {roznasobenie polynomu...}
                while (n1<>nil) do begin
                      n1^.a:=(n1^.a)*(n2^.a);
                      n1^.e:=(n1^.e)+(n2^.e);
                      n1:=n1^.next;
                end;
                rp1:=p_plus_p(rp, n);
                destroy_p(rp);
                rp:=rp1;
                rp1:=nil;

		destroy_p(n);
                n2:=n2^.next;
        end;

	p_times_p:=rp;
end;

{
mAkE
sOmE
dEmO
}
begin
	init_p(a, 3, 1, 2, 3, 4);
        init_p(b, 1, 1, 2, 0, 0);

        c:=p_times_p(a, b);

        print_p(a);
        writeln('*');
        print_p(b);
        writeln('=');
        print_p(c);
        writeln('-----------------------------------------------------');

        destroy_p(a);
        destroy_p(b);
        destroy_p(c);
end.