Cod sursa(job #486566)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 21 septembrie 2010 23:22:25
Problema Prod Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<fstream.h>
#define NMAX 1002

int fr[10], a[NMAX], b[NMAX], c[NMAX+NMAX], c1[NMAX+NMAX], d[NMAX], i, nc, j, na, nb, T, ii;

void invers1()
{
    int p=1, u=a[0],aux;
    while (p<u)
	{
		aux=a[p];
        a[p]=a[u];
        a[u]=aux;
        ++p;--u;
    }
}

void invers2()
{
	int p=1, u=b[0], aux;
	while (p<u)
	{
		aux=b[p];
		b[p]=b[u];
		b[u]=aux;
		++p;--u;
	}
}

void inmultire0()
{
	invers1();
	invers2();
	c[0]=a[0]+b[0]-1;
	for (i=1;i<=a[0]+b[0];) c[i++]=0;
	for (i=1;i<=a[0];i++)
		for (j=1;j<=b[0];j++)
			c[i+j-1]+=a[i]*b[j];
	for (i=1;i<=c[0];i++)
    { 
		T=(c[i]+=T)/10;
		c[i]%=10;
    }
	if (T) c[++c[0]]=T;
	invers1();
	invers2();
}

void inmultire1()
{
	invers1();
	invers2();
	c1[0]=a[0]+b[0]-1;
	for (i=1;i<=a[0]+b[0];) c1[i++]=0;
	for (i=1;i<=a[0];i++)
		for (j=1;j<=b[0];j++)
			c1[i+j-1]+=a[i]*b[j];
	T=0;
	for (i=1;i<=c1[0];i++)
    { 
		T=(c1[i]+=T)/10;
		c1[i]%=10;
    }
	if (T) c1[++c1[0]]=T;
	invers1();
	invers2();
}

int comp()
{
	if (c[0]==c1[0])
		{for (i=c[0]; i>0; --i)
			if (c1[i]<c[i]) return 0;
				else if (c1[i]>c[i]) return 1;}
	else if (c[0]>c1[0]) return 0;
				else return 1;
}

int main()
{
	ifstream f("prod.in");
	ofstream g("prod.out");
	
	for(i=1; i<10; ++i) f>>fr[i];
	
	for(i=9; i>0; --i)
		for(j=1; j<=fr[i]; ++j) d[++nc]=i;
	
	a[1]=d[1];a[0]=1;
	b[1]=d[2];b[0]=1;
	for(ii=3; ii<=nc; ++ii)
	{
		a[++a[0]]=d[ii];
		inmultire0();
		a[a[0]--]=0;
		b[++b[0]]=d[ii];
		inmultire1();
		b[b[0]--]=0;
		if (comp()==0) a[++a[0]]=d[ii];
			else b[++b[0]]=d[ii];
	}
	T=0;
	inmultire0();
	for(i=c[0]; i>0; --i) g<<c[i];
	g<<"\n";
	for(i=1; i<=a[0]; ++i) g<<a[i];
	g<<"\n";
	for(i=1; i<=b[0]; ++i) g<<b[i];
	g<<"\n";
	f.close();
	g.close();
	return 0;
}