TREEPATH - Đường đi trên cây

Tác giả: hieult

Ngôn ngữ: C++

#include <cstdio>
#include <iostream>
//#include <conio.h>
#define base 100000000

using namespace std;

struct solon
{
     int so;
     long long a[500];
     solon(){}
     solon(long long x){
          so = 1;
          a[1] = x;
     }
};

solon tong (solon A,solon B)
{
      int du = 0;
      solon C;
      if(A.so<B.so)
      {
           C = A;
           A = B;
           B = C;
      }
      for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
      C.so = A.so;
      for(int i = 1;i<=A.so;i++)
      {
          C.a[i] = (A.a[i]+B.a[i]+du)%base;
          du = (A.a[i]+B.a[i]+du)/base;
      }
      if(du>0) {C.so++; C.a[C.so] = du;}
      return C;
}

solon tichnho(solon A,long long k,int chuso)
{
      solon C;
      long long du = 0;
      C.so = A.so+chuso;
      for(int i = 1;i<=chuso;i++)
           C.a[i] = 0;
      for(int i = chuso+1;i<=chuso+A.so;i++)
      {
           C.a[i] = (A.a[i-chuso]*k+du)%base;
           du = (A.a[i-chuso]*k+du)/base;
      }
      if(du>0) {C.so++; C.a[C.so] = du;}
      return C;
}

solon tich(solon A,solon B)
{
      solon C;
      C.so = 1; C.a[1] = 0;
      for(int i = 1;i<=B.so;i++)
      {
           C = tong(C,tichnho(A,B.a[i],i-1));
      }
      return C;
}

void print(solon A)
{
      printf("%lld",A.a[A.so]);
      for(int i = A.so-1;i>=1;i--)
          printf("%08lld",A.a[i]);
}

solon KQ,run,T,cong,the,nhanh;
char s[2222];

int main()
{
      scanf("%s",s);
      KQ = solon(1);
      run = solon(1);
      nhanh = solon(1);
      for(int i = 0;i<strlen(s);i++){
            if(s[i]=='L'){
                 run = tichnho(run,3,0);
                 KQ = tong(KQ,run);
            }
            else if(s[i]=='C'){
                 run = tong(tichnho(run,3,0),nhanh);
                 KQ = tong(KQ,run);
            }
            else if(s[i]=='R'){
                 run = tong(tichnho(run,3,0),tichnho(nhanh,2,0));
                 KQ = tong(KQ,run);            
            }
            else if(s[i]=='*'){
                 the = run;
                 run = tong(tichnho(run,9,0),tichnho(nhanh,3,0));
                 KQ = tong(tichnho(KQ,4,0),run);
                 run = tong(run,the);
                 nhanh = tichnho(nhanh,4,0);
            }
            
            //print(KQ);
            //printf("\n");
      }
      print(KQ);
      //getch();
}

Download