Cod sursa(job #466605)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 27 iunie 2010 11:51:11
Problema Prod Scor 10
Compilator c Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 2.18 kb
#include <stdio.h>
#include <string.h>
#define NMAX 22
#define LMAX 2005
#define ll long long
int A[LMAX],r,st1[LMAX],st2[LMAX],t1,t2,ap[NMAX];
ll nr1,nr2,rez;
int B[LMAX],C[LMAX];
void read()
{
    int i,j,x;
    for (i=1; i<=9; i++)
    {
        scanf("%d",&x);
        ap[i]=x;
        for (j=1; j<=x; j++)
            A[++r]=i;
    }
}
void solve()
{
    int i,j;
    for (i=1; i<(1<<r); i++)
    {
        t1=t2=0;
        nr1=nr2=0;
        for (j=1; j<=r; j++)
            if (i & 1<<(j-1))
                st1[++t1]=j;
            else
                st2[++t2]=j;
        for (j=t1; j>=1; j--)
            nr1=nr1*10+A[st1[j]];
       for (j=t2; j>=1; j--)
            nr2=nr2*10+A[st2[j]];
       if (nr1*nr2>rez)
            rez=nr1*nr2;
    }
}
void solve2()
{
    int i,j;
    for (i=1; i<=9; i++)
    {
        if (ap[i] % 2==0)
        {
            for (j=1; j<=ap[i]/2; j++)
            {
                B[++B[0]]=i;
                C[++C[0]]=i;
            }
        }
        else
        {
            if (C[0]<B[0])
            {
                for (j=1; j<=ap[i]/2+1; j++)
                    C[++C[0]]=i;
                for (j=1; j<=ap[i]/2; j++)
                    B[++B[0]]=i;
            }
            else
            {
                 for (j=1; j<=ap[i]/2+1; j++)
                     B[++B[0]]=i;
                 for (j=1; j<=ap[i]/2; j++)
                     C[++C[0]]=i;
            }
        }
    }
}

void mul(int A[], int B[])
{
      int i, j, t, D[LMAX];
      memset(D, 0, sizeof(D));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      D[i+j-1]=(t+=D[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > D[0]) D[0] = i + j - 2;
      }
      memcpy(A, D, sizeof(D));
}
void show()
{
    mul(B,C);
    int i;
    for (i=B[0]; i>=1; i--)
        printf("%d",B[i]);
    printf("\n");
}
int main()
{
    freopen("prod.in","r",stdin);
    freopen("prod.out","w",stdout);
    read();
    if (r<=16)
    {
        solve();
        printf("%lld\n",rez);
        return 0;
    }
    solve2();
    show();
    return 0;
}