Cod sursa(job #466722)

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

using namespace std;

int best[lgmax]; //solutia optima
int a[lgmax], b[lgmax]; //cele doua numere pe care le inmultim
int ap[sigma]; //ap[i]=numarul de cartonase cu cifra i

inline void push(int v[], int x)
{
	v[++v[0]]=x;
}

void swap(int v[])
{
	int st=1, dr=v[0];
	int aux;
	while(st<dr)
		aux=v[st], v[st]=v[dr], v[dr]=aux, st++, dr--;
}

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 write_number(int v[])
{
	int i;
	for(i=v[0];i>0;i--)
		printf("%d",v[i]);
	printf("\n");
}

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

void solve()
{
	int i;
	char maxx=0;

	for(i=9;i>0;--i)
		{
			while(ap[i]>=3)
				push(a,i), push(b,i), ap[i]-=2;
			while(ap[i])
			{
				if(a[0]<b[0]) push(a,i);
				else if(a[0]>b[0]) push(b,i);
				else if(maxx=='a') push(b,i);
				else if(maxx=='b') push(a,i);
				else
				{
					push(a,i);
					if(ap[i]!=2) maxx='a';
				}
				ap[i]--;
			}
		}

	swap(a);
	swap(b);
	/*
	write_number(a);
	write_number(b);
	*/
	prod(best,a,b);
}

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();
	solve();
	write();

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