#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

static int verbose = 0 ;
static int list = 0 ;
static unsigned char bound = 'a' ;
static int all = 0 ;


typedef unsigned int base ;

static base log2_plancher(base n) {
  base r = 0 ;
  while (n > 1) {
    r++ ;
    n /= 2 ;
  }
  return r ;
}

static base log2_plafond(base n) {
  base r = log2_plancher(n) ;
  if (n != (1 << r)) r++ ;
  return r ;
}

static base nu(base n) {
  int r = 0 ;
  while (n > 0) {
    if (n % 2 == 1) r++ ;
    n /= 2 ;
  }
  return r ;
}

static double log2(double x) {
  return log(x)/log(2) ;
}

static base borne(base n) {
  base bits = nu(n) ;
  if (bits < 17 || n < 327679) {
    return log2_plancher(n) + log2_plafond(bits) ;
  } else {
    return ceil(log2(n) + log2(bits) - 2.13) ;
  }
}

static void dump(FILE *fp, base *q) {
  base *p ;
  for (p = q ; *p ; p--)
    ;
  p++ ;
  fprintf(fp, "%u", *p) ;
  p++ ;
  for ( ; p <= q ; p++)
    fprintf(fp, " %u", *p) ;
  putc('\n', fp) ;
  fflush(fp) ;
}

/* Maximum frame size */
#define FRAME 1024

typedef struct stack {
  base *sp, *fp ; // fp is start of current frame, sp is next valid slot
  base frame[FRAME] ;
  struct stack *prev ;
} stack ;


#ifdef VERBOSE
static void dump_seen(FILE *fp, stack *p) {
  base *w ;
  for (w = p->fp  ; w < p->sp ; w++) {
    fprintf(fp, " %u", *w) ;
  }
}
#endif
static stack *cache = NULL ;

static stack *insert(stack *p, base x) {
  base *w ;

  if (p->sp >= p->frame + FRAME) {
    stack *r ;
#ifdef VERBOSE
    if (verbose > 1) {
      fprintf(stderr,"PUSH\n") ;
    }
#endif
    if (p->fp == p->frame) {
      fprintf(stderr, "Frame size is too small !!\n") ;
      exit(2) ;
    }
    if (cache == NULL) {
      r = malloc(sizeof(stack)) ;
      if (r == NULL) {
        fprintf(stderr, "Cannot malloc in insert") ;
        exit(2) ;
      }
    } else {
      r = cache ;
      cache = cache->prev ;
    }

    memmove(r->frame, p->fp, (p->sp - p->fp)*sizeof(base)) ;
    r->fp = r->frame ;
    r->sp = r->frame +  (p->sp - p->fp) ;
    r->prev = p ;
    p = r ;
  }

  for (w = p->fp  ; w < p->sp ; w++) {
    base y = *w ;
    if (y == x)
      return p ;
    else if (x > y) {
      memmove(w+1, w, (p->sp-w)*sizeof(base)) ;
      break ;
    }
  }
  *w = x ;
  p->sp++ ;
  return p ;
}

static stack *free_frame(stack *p) {
  if (p->fp == p->frame) {
    stack *r = p->prev ;
#ifdef VERBOSE
    if (verbose > 1) {
      fprintf(stderr,"POP\n") ;
    }
#endif
    p->prev = cache ;
    cache = p ;
    return r ;
  } else
    return p ;
}



static unsigned int
explore(base d, base n, base *q, stack *st, base *vert, base* slant) {
  if (d <= 1) {
    base *t, *tt ;
    for (t = q-1 ; ; t--) {
      base x = *t ;
      if (2*x < n)
        break ;
      for (tt = t ; ; tt--) {
        base s = x + *tt ;
        if (s < n) break ;
        if (s == n) {
#ifdef VERBOSE
          if (list) {
            *q = s ;
            dump(stdout,q) ;
          }
#endif
          return 1 ;
        }
      }
    }
    return 0 ;
  } else {
    base *save_fp = st->fp ;
    base *save_sp = st->sp ;
    base prev = *(q-1) ;
    unsigned int r=0 ;
    base low1 = prev+1, low2 = vert[d-1] ;
    base low0 = low1 < low2 ? low2 : low1 ;
    base low = low0 ;
    base high = 2*prev < n-1 ? 2*prev : n-1 ;
    base low3 = 0 ;
    base *t, *tt ;

    if (slant[d-2] > prev)
      low3 = slant[d-2] - prev ;
    if (low3 > low && ((n & ((1 << (d-1))-1)) != 0)) low = low3 ;
    st->fp = st->sp ;
#ifdef VERBOSE
    if (verbose > 1) {
      fprintf(stderr, "d=%u, ", d) ;
      dump(stderr,q-1) ;
    }
#endif
    for (t = q-1 ;  ; t--) {
      base x = *t ;
      base s ;

      if (2*x < low) break ;

      for (tt = t ; ; tt--) {
        s = x + *tt ;
        if (s <= high) break ;
      }
      while (s >= low) {
        st = insert(st, s) ;
        s = x + *--tt ;
      }
    }

#ifdef VERBOSE
    if (verbose > 1) {
      if (low == low1)
        fprintf(stderr,"*1* ") ;
      else if (low == low2)
        fprintf(stderr,"*2* ") ;
      else
        fprintf(stderr,"*3* ") ;
      fprintf(stderr, "%u - %u:", low, high) ;
      fprintf(stderr," %u (%.2f)", st->sp - st->fp, (100.0 * (st->sp - st->fp))/(high-low+1)) ;
      fprintf(stderr, " [%u, %u, %u]\n", low1, low2, low3) ;
    }
#endif
    tt = st->sp ;
    for (t = st->fp ; t < tt ; t++) {
      *q = *t ;
      r += explore(d-1, n, q+1, st, vert, slant) ;
      if (all && r)
        break ;
    }
    st = free_frame(st) ;
    st->fp = save_fp ;
    st->sp = save_sp ;
    return r ;
  }
}

static void compute_c(base *b, base n, base k) {
  base d ;
  base t = 0, m = n ;

  while (m % 2 == 0) {
    t++ ;
    m /= 2 ;
  }
  /* n = 2^t * m */
  /* d = k-i */
  
  for (d = 0 ; d <= t + 1 && d < k ; d++) {
    b[d] = (n + (1 << d) - 1) >> d ;
  }
  for ( ; d < k ; d++) {
    b[d] = ceil(n / (3.0 * (1U << (d-2)))) ;
  }
}

static void compute_a(base *b, base n, base k) {
  base d ;
  for (d = 0 ; d < k ; d++) {
    b[d] = (n + (1 << d) - 1) >> d ;
  }
}


static unsigned int chain(base k, base n) {
  base t[k+1] ;
  stack st ;

  st.prev = NULL ;
  st.fp = st.sp = &(st.frame[1]) ;
  t[0] = 0 ;
  t[1] = 1 ;
  if (bound == 'a') {
    base b[k+1] ;
    compute_a(b, n, k) ;
    return explore(k-1, n, t+2, &st, b, b) ;
  } else if (bound == 'c') {
    if (n % 5 == 0) {    
      base a[k] ;
      base c[k] ;
      compute_a(a, n, k) ;
      compute_c(c, n, k) ;
      return explore(k-1, n, t+2, &st, c, a) ;
    } else {
      base b[k] ;
      compute_c(b, n, k) ;
      return explore(k-1, n, t+2, &st, b, b) ;
    }
  } else {
    exit(3) ;
  }
}

static base usuel(base n) {
  if (n == 1) {
#ifdef VERBOSE
    if (list)
      printf(" %u", n) ;
#endif
    return 0 ;
  } else {
    base r = usuel(n/2) ;
#ifdef VERBOSE
    if (list) {
      printf(" %u", n & ~1) ;
      if (n % 2 == 1)
        printf(" %u", n) ;
    }
#endif
    return 1+ r + n % 2 ;
  }
}

static void zyva(base n) {
  base k = borne(n)+1 ;
  unsigned int r ;

  r = usuel(n) ;
#ifdef VERBOSE
  if (list)
    putchar('\n') ;
#endif
  printf("La technique usuelle donne %u multiplications\n", r) ;
  r = 0 ;
  do {
#ifdef VERBOSE    
    if (verbose) fprintf(stderr, "%u\n", k) ;
#endif
    r = chain(k,n) ;
    k++ ;
  } while (r == 0) ;
  printf("Il y a %u solution%s de taille %u\n", r, r > 1 ? "s" : "", k-2) ;
}

void zyva_all(base p) {
  unsigned int d[p+2] ;
  unsigned int c[p+2] ;
  base n = 1 << p ;
  base i ;
  for (i = 0 ; i <= p ; i++) {
    d[i] = c[i] = 0 ;
  }
  for (i = 2 ; i <= n ; i++) {
    base k = borne(i)+1 ;
    base r = 0 ;
    do {
      if (k-1 > p) break ;
      r = chain(k,i) ;
      k++ ;
    } while (r == 0) ;
    if (r > 0) {
      k -= 2  ;
      d[k]++ ;
      if (c[k] == 0) {
        c[k] = i ;
        printf("c[%u] = %u\n", k, c[k]) ;
      }
    }
  }
  for (i = 1 ; i <= p ; i++) {
    printf("d[%u] = %u\n", i, d[i]) ;
  }
}

int main(int argc, char **argv) {
  base n = 255 ;
  char *pgm = argv[0] ;

  while (--argc > 0) {
    char *p = (++argv)[0] ;
    if (*p == '-') {
      while (*++p != '\0') {
        if (*p == 'v')
          verbose++ ;
        else if (*p == 'V')
          verbose += 2 ;
        else if (*p == 'c')
          bound = 'c' ;
        else if (*p == 'l')
          list = 1 ;
        else if (*p == 'a')
          all = 1 ;
        else {
          fprintf(stderr,"usage: %s [-vVcla] [n]\n", pgm) ;
          fprintf(stderr, "  -v, donne des diagnostics\n") ;
          fprintf(stderr, "  -V, encore plus de diagnostics\n") ;
          fprintf(stderr, "  -c, optimisations de type c (a par défaut)\n") ;
          fprintf(stderr, "  -l, donne les chaînes d'addition\n") ;
          fprintf(stderr, "  -a, affiche les tableaux c et d de l'énoncé\n") ;
          exit(2) ;
        }
      }
    } else
      break ;
  }

  if (argc > 0) n = atoi(argv[0]) ;
  if (all)
    zyva_all(n) ;
  else
    zyva(n) ;
  return 0 ;
}