Cod sursa(job #466783)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 27 iunie 2010 14:43:02
Problema Prod Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.95 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 2100

long n, sum, poz, comp, c1, c2;
long f[11], a[maxn], b[maxn], c[maxn];

void inm()
{
    for(long i=1; i<=a[0]; i++)
    {
        long t=0;
        long j;
        for(j=1; j<=b[0] || t; j++)
        {
            t=t+c[i+j-1]+a[i]*b[j];
            c[i+j-1]=t%10;
            t/=10;
        }
        c[0]=max(c[0], i+j-2);
    }
}

long getcif()
{
    while(f[poz]==0)
        --poz;
    f[poz]--;
    return poz;
}

int main()
{
    freopen("prod.in", "r", stdin);
    freopen("prod.out", "w", stdout);
    for(long i=1; i<=9; ++i)
    {
        scanf("%d", &f[i]);
        sum+=f[i];
    }
    poz=9;
    if(sum%2==0)
    {
        a[0]=b[0]=sum/2;
        a[a[0]]=getcif();
        b[b[0]]=getcif();
        if(a[a[0]]>b[b[0]])
            comp=1;
        else
        if(a[a[0]]<b[b[0]])
            comp=2;
        for(long i=sum/2-1; i; --i)
        {
            if(comp==2)
            {
                a[i]=getcif();
                b[i]=getcif();
            }
            else
            {
                b[i]=getcif();
                a[i]=getcif();
            }
            if(comp==0 && a[i]!=b[i])
            {
                if(a[i]>b[i])
                    comp=1;
                else
                    comp=2;
            }
        }
    }
    else
    {
        a[0]=sum/2+1;
        b[0]=sum/2;
        b[b[0]]=getcif();
        a[a[0]]=getcif();
        for(long i=sum/2; i>1; --i)
        {
            c1=getcif();
            c2=getcif();
            if(c1*b[i]+c2*a[i-1]<c2*b[i]+c2*a[i-1])
            {
                b[i-1]=c2;
                a[i]=c1;
            }
            else
            {
                a[i]=c2;
                b[i-1]=c1;
            }
        }
        a[1]=getcif();
    }
    inm();
    c[0]=1500;
    while(c[c[0]]==0)
        --c[0];
    for(long i=c[0]; i; --i)
    {
        printf("%d", c[i]);
    }
    printf("\n");
    return 0;
}