#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Count the number of occurrences of abc. Return 1 if and only if the count
   is 1. */
int isvalid ( char *A, int n )
{
   int i, nocc, state;

   state = 0; nocc = 0;
   for (i=0; i<n; ++i) {
      if (A[i] == 'a') {                             /* Potential beginning */
         state = 1;
      } else if (A[i] == 'b') {                      /* Potential continuation */
         if (state == 1) state = 2; else state = 0;
      } else {                                       /* Potential completion */
         if (state == 2) state = 3; else state = 0;
      }
      if (state == 3) {                              /* Pattern found */
         ++nocc;
         state = 0;
      }
   }
   /* if (nocc == 1) printf("    %s\n", A); */
   return (nocc == 1) ? 1 : 0;
}

/* Exhaustive search: Iterative method */
int exhitr ( int n )
{
   char *A;
   int i, cnt = 0;

   A = (char *)malloc((n+1)*sizeof(char));
   A[n] = '\0';
   for (i=0; i<n; ++i) A[i] = 'a'; /* lexicographically smallest string */
   while (1) {
      /* Increment to the lexicograhically next string */
      i = n-1;
      while ((i >= 0) &&(A[i] == 'c')) { A[i] = 'a';  --i; }
      if (i<0) break; /* All strings generated */
      ++A[i];
      if (isvalid(A,n)) ++cnt;
   }
   free(A);
   return cnt;
}

/* Recursive exhaustive search: helper function */
void exhrechelper ( char *A, int n, int i, int *cnt )
{
   if (i < n) {
      A[i] = 'a'; exhrechelper(A,n,i+1,cnt);
      A[i] = 'b'; exhrechelper(A,n,i+1,cnt);
      A[i] = 'c'; exhrechelper(A,n,i+1,cnt);
      return;
   }
   *cnt += isvalid(A,n);
}

/* Recursive exhaustive search: Wrapper function */
int exhrec ( int n )
{
   char *A;
   int cnt = 0;

   A = (char *)malloc((n+1)*sizeof(char));
   A[n] = '\0';
   exhrechelper(A,n,0,&cnt);
   free(A);
   return cnt;
}

/* Returns n choose k */
int binomial ( int n, int k )
{
   int num = n, den = k;

   while (--k > 0) {
      --n;
      num *= n;
      den *= k;
   }
   return num / den;
}

int calculate ( int n )
{
   int *S, *threepower, i, k, cnt;

   if (n <= 2) return 0;

   S = (int *)malloc((n+1)*sizeof(int));           /* No occurrence of abc */
   threepower = (int *)malloc((n+1)*sizeof(int));  /* Powers of three */

   /* Initialize */
   S[0] = threepower[0] = 1;
   for (i=1; i<=n; ++i) S[i] = threepower[i] = 3 * threepower[i-1];

   /* Use inclusion-exclusion to update S[] entries */
   for (k=1; k<=n/3; ++k)
      if (k % 2 == 0)
         for (i=3*k; i<=n; ++i) S[i] += binomial(i-2*k,k) * threepower[i-3*k];
      else
         for (i=3*k; i<=n; ++i) S[i] -= binomial(i-2*k,k) * threepower[i-3*k];

   /* Linear-time formula for the desired count */
   for (i=cnt=0; i<=n-3; ++i) cnt += S[i] * S[n-i-3];

   free(S);
   free(threepower);

   return cnt;
}

int main ( int argc, char *argv[] )
{
   int n, cnt;
   clock_t c1, c2;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n = %d\n", n);

   printf("\n+++ Exhaustive search: Iterative\n");
   c1 = clock(); cnt = exhitr(n); c2 = clock();
   printf("    Count = %d, Time taken: %f sec\n", cnt, (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   printf("\n+++ Exhaustive search: Recursive\n");
   c1 = clock(); cnt = exhrec(n); c2 = clock();
   printf("    Count = %d, Time taken: %f sec\n", cnt, (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   printf("\n+++ Polynomial time calculations\n");
   c1 = clock(); cnt = calculate(n); c2 = clock();
   printf("    Count = %d, Time taken: %f sec\n", cnt, (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   exit(0);
}