// gcc -O3 -o try16 try16.c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int m[1000], i;

int eq(int *g, int *d, int l){
 for(; l--; ) if(g[l] != d[l]) return 0;
 return 1;
}

int ispal(int x, int y){
 for(; x < y && m[x] == m[y]; x++, y--); 
 return x >= y;
}

int pp(){
 int x, y, z, w = 1;
 if(i > 1 && m[i-2]+m[i-1]+m[i] == 1) return 0;
 for(x = 1; (z = 2*x) <= i+1; x++){
  for(y = i-x; (y >= 0) && (m[y] == m[y+x]); y--);
  if(i-y >= z) return 0;
 }
 for(x = 0; x <= i; x++) for(y = x; y <= i && y-x < 32; y++) if(ispal(x, y)){
  for(z = 0; z < x && !eq(m+z, m+x, y-x+1); z++);
  if(z == x && ++w > 16) return 0;
 }
 return 1;
}

void main(int ac, char **av){
 for(*m = i = 0; i < 1000;) if(pp()) m[++i] = 0; else{
  while(m[i] == 2) if(!(--i)) goto here;
  m[i]++;
 }
 printf("a word of length 1000 has been obtained\n");
 return;
 here: printf("backtracking finishes\n");
}