Cod sursa(job #2845)

Utilizator pocaituDavid si Goliat pocaitu Data 19 decembrie 2006 14:43:03
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<fstream.h>
int n, s[104][190],s1[104][190],i,j,k,sum[190],c[190],ic,ss[190],kk;
void add(int A[], int B[])
{int i, t = 0;
 for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
	 A[i] = (t += A[i] + B[i]) % 10;
 A[0] = i - 1;
}
void mul(int A[], int B[])
{
	  int i, j, t, C[190];
	  memset(C, 0, sizeof(C));
	  for (i = 1; i <= A[0]; i++)
	  {
			  for (t=0, j=1; j <= B[0] || t; j++, t/=10)
					  C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
			  if (i + j - 2 > C[0]) C[0] = i + j - 2;
	  }
	  memcpy(A, C, sizeof(C));
}
int main()
{ifstream f("race.in");
 //f>>n;
 n=100;
 s[1][1]=1;s[1][0]=1;c[0]=1;c[1]=1;
 for(k=2;k<=n;k++)
   {for(i=1;i<k;i++)
	  {ic=i;
	   while(ic>0)
		 {ss[++ss[0]]=ic%10;
		  ic/=10;}
	   mul(ss,s[i]);
	   add(s1[i],ss);
	   ic=i;
	   memset(ss,0,sizeof(ss));
	   while(ic>0)
		 {ss[++ss[0]]=ic%10;
		  ic/=10;}
	   add(ss,c);
	   mul(ss,s[i]);
	   add(s1[i+1],ss);
	   memset(ss,0,sizeof(ss));
	   }
   memcpy(s,s1,sizeof(s1));
	memset(s1,0,sizeof(s1));
	
    }
ofstream g("race.out");
for(i=1;i<=n;i++)
  add(sum,s[i]);
for(i=sum[0];i>=1;i--)
 g<<sum[i];

g.close();
return 0;
}