Cod sursa(job #466643)

Utilizator rusu_raduRusu Radu rusu_radu Data 27 iunie 2010 12:33:58
Problema Prod Scor 100
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 3.55 kb
#include <cstdio>
#include <cassert>
#define Nmax 1205
#define InFile "prod.in"
#define OutFile "prod.out"
#define foreach(ind,start,fin) for (ind=start; ind<=fin; ind++)

using namespace std;

int v[10], l1, l2, ld1, ld2, lr, sum, lastpos;
int nr1[Nmax], nr2[Nmax], dif1[Nmax], dif2[Nmax], rez[Nmax];

int next_one();
void move (int [], int&);
void diferenta (int [], int, int [], int, int[], int &);
int comparare(int [], int , int [], int);
void write();
void inmultire (int A[], int la, int B[], int lb, int C[], int &lc);
void copy (int [], int&, int[], int);

int main()
{
    int i, k, cf1, cf2;
    lastpos=9;
    assert (freopen (InFile, "r", stdin));
    assert (freopen (OutFile, "w", stdout));
    foreach (i, 1, 9) scanf ("%d ", &v[i]), sum+=v[i];
    nr1[0]=next_one(); l1=1;
    nr2[0]=next_one(); l2=1;
    for (k=2; k<=sum/2; k++)
    {
        cf1=next_one();
        cf2=next_one();
        move (nr1, l1);
        move (nr2, l2);
        //caz 1
        nr1[0]=cf1;
        nr2[0]=cf2;
        diferenta (nr1, l1, nr2, l2, dif1, ld1);
        nr1[0]=cf2;
        nr2[0]=cf1;
        diferenta (nr1, l1, nr2, l2, dif2, ld2);
        if (comparare (dif1, ld1, dif2, ld2)<0)
            nr1[0]=cf1, nr2[0]=cf2;
        else
            nr1[0]=cf2, nr2[0]=cf1;
    }
    if (sum%2==0)
        inmultire (nr1, l1, nr2, l2, rez, lr);
    else
    {
        cf1=next_one();
        move (nr1, l1); nr1[0]=cf1;
        inmultire (nr1, l1, nr2, l2, dif1, ld1);
        foreach (i, 0, l1-1) nr1[i]=nr1[i+1];
        l1--;
        move (nr2, l2); nr2[0]=cf1;
        inmultire (nr1, l1, nr2, l2, dif2, ld2);
        if (comparare (dif1, ld1, dif2, ld2)>0)
            copy (rez, lr, dif1, ld1);
        else
            copy (rez, lr, dif2, ld2);
    }
    write();
    return 0;
}

int next_one()
{
    if (v[lastpos])
    {
        v[lastpos]--;
        return lastpos;
    }
    for (; !v[lastpos]; lastpos--);
    v[lastpos]--;
    return lastpos;
}

void move (int a[], int &la)
{
    int i;
    for (i=la; i>0; i--)
        a[i]=a[i-1];
    la++;
}

void diferenta (int A[], int la, int B[], int lb, int C[], int &lc)
{
    int i, z, t=0;
    foreach (i, 0, lb-1)
    {
        z=A[i]-B[i]+t;
        if (z<0)
        {
            z+=10; t=-1;
            C[i]=z;
        }
        else
        {
            C[i]=z; t=0;
        }
    }
    foreach (i, lb, la-1)
    {
        z=A[i]+t;
        if (z<0)
        {
            z+=10; t=-1;
            C[i]=z;
        }
        else
        {
            C[i]=z; t=0;
        }
    }
    lc=la;
    for (i=lc-1; i>=0&&C[i]<=0; i--, lc--);
}

int comparare (int A[], int la, int B[], int lb)
{
    int i;
    if (la>lb)
        return 1;
    if (la<lb)
        return -1;
    for (i=la-1; i>=0; i--)
        if (A[i]>B[i])
            return 1;
        else
            if (A[i]<B[i])
                return -1;
    return 0;
}

void inmultire (int A[], int la, int B[], int lb, int C[], int &lc)
{
    int i, j, t;
    foreach (i, 0, Nmax/2) C[i]=0;
    lc=la+lb-1;
    for (i=0; i<la; i++)
        for (j=0; j<lb; j++)
            C[i+j]+=A[i]*B[j];
    t=0;
    foreach (i, 0, lc-1)
    {
        C[i]+=t;
        t=C[i]/10;
        C[i]=C[i]%10;
    }
    if (t)
        C[lc++]=t;
}

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

void copy (int A[], int &la, int B[], int lb)
{
    int i;
    la=lb;
    foreach (i, 0, la) A[i]=B[i];
}