Cod sursa(job #466730)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 27 iunie 2010 13:49:54
Problema Prod Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.69 kb
#include<cstdio>
#define infile "prod.in"
#define outfile "prod.out"
#define sigma 10
#define nmax 1013
#define lgmax 1000013

using namespace std;

int best[lgmax]; //solutia optima
int tryy[lgmax]; //aici incercam sa obtinem toate solutiile
int a[lgmax], b[lgmax]; //cele doua numere pe care facem back-ul
int apa[sigma], apb[sigma]; //pt a si b numarul de cifre din feicare cifra
int ap[sigma]; //ap[i]=numarul de cartonase cu cifra i
int n; //numarul total de cartonase

void prod(int a[], int b[], int c[])
{ //a=b*c
	int i,j,t;
	while(a[0]) a[a[0]--]=0;
	for(i=1;i<=b[0];++i)
		for(j=1;j<=c[0];++j)
			a[i+j-1]+=b[i]*c[j];
	for(i=1,t=0;i<=b[0]+c[0]||t;++i)
		a[i]=(t+=a[i])%10, t/=10;
	a[0]=i;
	while(!a[a[0]]) a[0]--;
}

void construct(int v[], int ap[])
{
	int i,j;
	while(v[0]) v[v[0]--]=0;
	for(i=1;i<10;++i)
		for(j=1;j<=ap[i];++j)
			v[++v[0]]=i;
}

int compar(int a[], int b[])
{
	int i;
	if(a[0]>b[0]) return 1;
	if(a[0]<b[0]) return 0;

	for(i=a[0];i>0;--i)
		if(a[i]>b[i]) return 1;
		else if(a[i]<b[i]) return 0;
	return 0;
}

void copyy(int a[], int b[])
{
	int i;
	for(i=0;i<=b[0];++i)
		a[i]=b[i];
}

void read()
{
	int i;
	for(i=1;i<10;i++)
		scanf("%d",&ap[i]);
}

void bk(int x)
{
	int i;
	if(!x)
	{ //inseamna ca avem numerele complete
		construct(a,apa);
		construct(b,apb);
		if(!a[0]||!b[0]) return;
		prod(tryy,a,b);
		if(compar(tryy,best))
			copyy(best,tryy);
		return;
	}
	for(i=0;i<=ap[x];++i)
	{
		apa[x]=i, apb[x]=ap[x]-i;
		bk(x-1);
	}
	apa[x]=apb[x]=0;
}

void write()
{
	int i;
	for(i=best[0];i>0;--i)
		printf("%d",best[i]);
	printf("\n");
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);

	read();
	bk(9);
	write();

	fclose(stdin);
	fclose(stdout);
	return 0;
}