Cod sursa(job #67805)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 25 iunie 2007 17:22:04
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <string.h>

#define cmax 2024
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define BAZA 10

int n,A[cmax],sol[cmax],rez[cmax],B[cmax];
char s[cmax];

void dec()
{
    int i;
    for(i=1;!A[i];i++)
	A[i]=BAZA-1;
    A[i]--;
    if(!A[A[0]])
	A[0]--;
}

void inm(int x)
{
    int i,t=0;
    for(i=1;i<=sol[0]||t;i++)
    {
	sol[i]=sol[i]*x+t;
	t=sol[i]/BAZA;
	sol[i]%=BAZA;
    }
    sol[0]=i-1;
}

void afis(int sol[])
{
    int i;
    for(i=sol[0];i;i--)
	printf("%d",sol[i]);
    printf("\n");
}

int main()
{
    freopen("sarpe.in","r",stdin);
    freopen("sarpe.out","w",stdout);
    int i,j,t;
    scanf("%s",s);
    n=strlen(s);
    FOR(i,0,n)
	A[n-i]=s[i]-'0';
    A[0]=n;
	if(n==1&&A[1]==1)
	{
		printf("2\n");
		return 0;
	}

    //rez=sol=4*n;
    memcpy(sol,A,sizeof(A));
    inm(4);
    memcpy(rez,sol,sizeof(sol));

    //B=n-1
    dec();
    memcpy(B,A,sizeof(A));
    //A=n-2
    dec();
    //sol=2*(n-1)*(n-2)
    memset(sol,0,sizeof(sol));
    FOR(i,1,A[0]+1)
    {
	t=0;
	for(j=1;j<=B[0]||t;j++)
	{
	    sol[i+j-1]+=A[i]*B[j]+t;
	    t=sol[i+j-1]/BAZA;
	    sol[i+j-1]%=BAZA;
	}
	if(i+j-2>sol[0])
	    sol[0]=i+j-2;
    }
    inm(2);

    for(t=0,i=1;i<=sol[0]||i<=rez[0]||t;i++)
    {
	sol[i]+=rez[i]+t;
	t=sol[i]/BAZA;
	sol[i]%=BAZA;
    }
    sol[0]=i-1;

    afis(sol);

    return 0;
}