Cod sursa(job #260342)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 16 februarie 2009 22:25:44
Problema Patrate2 Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>   
#include <string.h>
  
#define Lmax 1024   
#define BASE 10   
  
  
//formula este (2^n*n)*n   
//unde n<=100   
int n;   
int sol[Lmax],sol1[Lmax];   
  
void citire()//citesc numarul   
{   
    freopen("patrate2.in","rt",stdin);   
    scanf("%d\n", &n);   
}   
  
void init(int H[], unsigned long X) //initializez vectorul H cu un scalar   
{   
  H[0]=0;   
    while(X)    
     {   
      ++H[0];      
      H[H[0]]=X%BASE;      
      X/=BASE;      
     }      
}   
  
  
void mul2(int A[])//inmultire cu 2   
{   
    int i, t;   
  
    for (i=1,t=0;i<=A[0] || t;++i,t/=BASE)   
        A[i]=(t+=2*A[i])%BASE;   
    A[0]=i-1;   
}   
  
  
void mul(int A[], int B[])//inmultire   
{   
      int i, j, t, C[Lmax];   
      memset(C, 0, sizeof(C));   
      for (i = 1; i <= A[0]; i++)   
      {   
              for (t=0, j=1; j <= B[0] || t; j++, t/=BASE)   
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%BASE;   
              if (i + j - 2 > C[0]) C[0] = i + j - 2;   
      }   
      memcpy(A, C, sizeof(C));   
} 
  
void scrie(int A[])//afisez vectorul   
{   
    int i;   
       
    freopen("patrate2.out", "w", stdout);   
    for (i = A[0]; i; --i)
		printf("%d", A[i]);
}   
  
  
void solve()   
{   
    int i;   
//in sol1 l-am initializat pe n   
    init(sol1,n);   
    sol[0]=sol[1]=1;   
    for (i=1;i<=n*n;++i)   
        mul2(sol);//2^n*n   
    mul(sol,sol1);//inmultesc pe 2^n*n cu n   
    scrie(sol);//afisez rezultatul   
}   
  
int main()   
{   
  
    citire();   
    solve();   
    return 0;   
}