Cod sursa(job #466660)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 27 iunie 2010 12:55:59
Problema Prod Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 2.38 kb
#include<cstdio>
typedef int Huge[1001];
Huge C,AP,BP;
int max,f[11],a[11];
void prod(Huge Rez,Huge X,Huge Y)
{
    for(int i=1;i<=X[0];i++)
        for(int j=1;j<=Y[0];j++)
            Rez[i+j-1]+=X[i]*Y[j];
    Rez[0]=X[0]+Y[0]-1;
    int poz=0;
    int T=0;
    while(++poz<=Rez[0])
    {
        Rez[poz]+=T;
        T=Rez[poz]/10;
        Rez[poz]%=10;
    }
    while(T)
        Rez[++Rez[0]]=T%10, T/=10;
}
void afis(Huge A)
{
    for(int i=A[0];i>0;i--)
        printf("%d",A[i]);
    printf("\n");
}
void make()
{
    int ok=1;
    for(int i=1;i<10;i++)
        if(f[i]%2==0)
        {
            for(int j=1;j<=f[i]/2;j++)
                AP[++AP[0]]=BP[++BP[0]]=i;
        }
        else
        {
            if(ok==1)
            {
                for(int j=1;j<=f[i]/2;j++)
                    AP[++AP[0]]=BP[++BP[0]]=i;
                AP[++AP[0]]=i;
                ok=0;
            }
            else
            {
                for(int j=1;j<=f[i]/2;j++)
                    AP[++AP[0]]=BP[++BP[0]]=i;
                BP[++BP[0]]=i;
                ok=1;
            }
        }
    prod(C,AP,BP);
    afis(C);
}
char comp(Huge A,Huge B)
{
    if(A[0]<B[0])
        return '<';
    if(A[0]>B[0])
        return '>';
    for(int i=A[0];i>0;i--)
        if(A[i]>B[i])
            return '>';
        else if(A[i]<B[i])
            return '<';
    return '=';
}
void copy(Huge A,Huge B)
{
    A[0]=B[0];
    for(int i=1;i<=A[0];i++)
        A[i]=B[i];
}
void back(int poz)
{
    if(poz==10)
    {
        Huge A={0};
        Huge B={0};
        Huge T={0};
        for(int i=1;i<10;i++)
        {
            for(int j=1;j<=a[i];j++)
                A[++A[0]]=i;
            for(int j=1;j<=f[i]-a[i];j++)
                B[++B[0]]=i;
        }
        prod(T,A,B);
        if(comp(C,T)=='<')
        {
            copy(C,T);
            copy(AP,A);
            copy(BP,B);
        }
        return;
    }
    for(int i=0;i<=f[poz];i++)
    {
        a[poz]=i;
        back(poz+1);
        a[poz]=0;
    }
}
int main()
{
    freopen("prod.in","r",stdin);
    freopen("prod.out","w",stdout);
    for(int i=1;i<10;i++)
    {
        scanf("%d",&f[i]);
        if(max<f[i])
            max=f[i];
    }
    if(max>2)
        make();
    else
    {
        back(1);
        afis(C);
    }
    return 0;
}