/* program to compute CELCS of costed binary sequences */
/* modified to output tree info */
/* restricted to integer costs (but easily modified) */
#include<stdio.h>
#include<math.h>
#define N 8 /* N is the period of the input sequence */
		/* and the maximum size of any arrays we need */

void celcs(int *s,int *cost, int l, int tsf, int lim, int c);
int min(int a, int b);

main()
{
  int i,k;
  char c;
  int s[N];
  int cost[N];
  
  /* input the initial sequence of N bits, setting all costs to 1 */
  for (i=0; i< N; i++)
    {
      c=getchar(); 
      if (c=='1')
	s[i]=1;
      else
	s[i]=0;
      cost[i]=1;
    }

  /* now run the celcs algorithm  */
  celcs(s,cost,N,0,N,0);

}

void celcs(int *s,int *cost, int l, int tsf, int lim, int c)
{
  int i;
  int L[N];
  int R[N];
  int B[N];
  int Lcost[N];
  int Bcost[N];
  int T=0;

  if (l >1)
    {
      /* calculate B(S) and L(S) */

      for (i=0;i < (l/2); i++)
	{
	  L[i]=s[i];
	  R[i]=s[i+(l/2)];
	  B[i]=L[i]^R[i];
	}

      /* calculate costs for B and L, and calculate T */

      for (i=0; i < (l/2); i++)
	{
	  Bcost[i]=min(cost[i],cost[i+(l/2)]);
	  T+=B[i]*Bcost[i];
	}
      
      for (i=0; i < (l/2); i++)
	{
	  if (B[i]==1)
	    {
	      if (cost[i] <= cost[i+(l/2)])
		{
		  L[i]=R[i];
		  Lcost[i]=cost[i+(l/2)]-cost[i];
		}
	      else
		{
		  Lcost[i]=cost[i]-cost[i+(l/2)];
		}
	    }
	  else
	    Lcost[i]=cost[i]+cost[i+(l/2)];
	}
      
	/* output the tree information - omit this if only need spectrum */
      printf("B(S):");
      for (i=0; i < l/2; i++)
	printf("%1d_%1d ",B[i],Bcost[i]);
      printf("\n");
      
      printf("L(S):");
      for (i=0; i < l/2; i++)
	printf("%1d_%1d ",L[i],Lcost[i]);
      printf("\n");

      printf("T: %d\n\n",T);
      
      
	/* the main decision point in the algorithm */      
      if (T > 0) 
	{
	  printf("CELCS(B(S),%d,%d,%d)\n",tsf,min(lim,tsf+T-1),c+(l/2));
	  celcs(B,Bcost,l/2,tsf,tsf+T-1,c+(l/2));
	}
      if (tsf + T <= lim)
	{
	  printf("CELCS(L(S),%d,%d,%d)\n",tsf+T,lim,c);
	  celcs(L,Lcost,l/2,tsf+T,lim,c);
	}
    }
  else
    {
	/* the case l=1 */
      printf("s[0]=%d,cost[0]=%d\n",s[0],cost[0]);
      if (s[0]==0)
	printf("CP: (%d,%d)\n",tsf,c);
      if ((s[0]==1) && (cost[0] > 0))
	printf("CP: (%d,%d)\n",tsf,c+1);
      if ((s[0]==1) && (tsf+cost[0] <= lim))
	printf("CP: (%d,%d)\n",tsf+cost[0],c);
      printf("\n");
    }
  return;
}


int min(int a, int b)
{
if (a < b)
  return(a);
else
  return(b);
}