#include <stdio.h>
#include <time.h>
#define MAX_N 30

unsigned int count[MAX_N+1];

void recur(int a, int b, int n){
  if(b)++count[n];
  if(n<MAX_N){
    recur(a+1,b,n+1);
    if(b+1<a)recur(a,b+1,n+1);
  }
}
int main()
{
  time_t t0,t1,t2;
  int a,b,i,n,p2,t,x;

  t0=clock();
  for(n=1;n<=MAX_N;++n){
    p2=1<<n; // equivalent to ipow(2,n)
    for(i=t=0;i<p2;++i){
      a=b=0;
      for(x=p2/2;x;x/=2){
        if(i&x)++a;
        else ++b;
        if(b>=a)break;
      }
      if(a>b)++t;
    }
    printf("%2d %9d\n",n,t-1);
  }
  t1=clock();
  printf("%f\n\n",(double)(t1-t0)/CLOCKS_PER_SEC);

  recur(1,0,1);
  for(i=1;i<=MAX_N;++i)
    printf("%2d %9u\n",i,count[i]);
  t2=clock();
  printf("%f\n",(double)(t2-t1)/CLOCKS_PER_SEC);

  return 0;
}