#include <stdio.h>

int cnt = 0;
int catalan(int);

int main(){

  printf("\n\n-------------------------------------------------------------");
  printf("\n\nEficient.c\n\n");

  printf("----------------------[PROGRAM STARTED]----------------------\n\n");


  printf("\n-------------------------[Eficient]--------------------------\n\n");

  int n;
  printf("N\tEficiente(N)\tNº de Multiplicações\n");
  for(n = 0;n<13;n++){
      printf("%d\t%d\t\t%d\n",n,catalan(n),cnt);

  }

  printf("\n-----------------------[PROGRAM ENDED]-----------------------\n\n");

  return 0;
}

int catalan(int n){

  int i,j,mid;
  unsigned int tmp[n+1];

  tmp[0] = 1;

    for(i = 1 ; i <= n ; i++){
      tmp[i]=0;
      mid = i/2;
      for(j = 0 ; j < mid ; j++){
        tmp[i] += tmp[j] * tmp[i-j-1]<<1;
        cnt++;
      }

      if(i%2 != 0){
        tmp[i] += tmp[mid] * tmp[mid];
        cnt++;
      }
    }

  return tmp[n];
}