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

typedef unsigned int elem ;
typedef unsigned long long  set  ;

#define SIZE (8*sizeof(set))

set singleton(elem i) {
  return ((set)1) << i ;
}

set add(set s, elem i) {
  return s | singleton(i) ;
}

int card(set s) {
  int r=0 ;
  elem i ;
  for (i = 0 ; i < SIZE ; i++) {
    set msk = singleton(i) ;
    if (s & msk) r++ ;
  }
  return r ;
}

void pset(FILE *fp, set s) {
  elem i ;
  putc('{',fp) ;
  for (i = 0 ; i < SIZE ; i++) {
    set msk = singleton(i) ;
    if (s & msk) {
      fprintf(fp,"%u, ", i) ;
    }
  }
  putc('}',fp) ;
}

typedef struct node {
  unsigned int count ;
  set p,m ;
  struct node *l,*r ;
} node ;

void dump(FILE *fp, node *p) {
  if (p == NULL) {
    fprintf(fp, "NULL") ;
  } else if (p->m == 0) {
    fprintf(fp,"LEAF [%u] %llu", p->count, p->p) ;
  } else {
    fprintf(fp, "Node [%u] (%llu, %llu, " , p->count, p->p, p->m) ;
    dump(fp, p->l) ;
    fprintf(fp,", ") ;
    dump(fp, p->r) ;
    fprintf(fp,")") ;
  }
}

node *free_list = NULL ;

void free_node(node *p) {
  p->l = free_list ;
  free_list = p ;
}

void decr(node *p) {
  if (p != NULL) {
    if (--p->count == 0) {
      if (p->m != 0) {
        decr(p->l) ;
        decr(p->r) ;
      }
      free_node(p) ;
    }
  }
}

void incr(node *p) {
  if (p != NULL) p->count++ ;
}

unsigned long long again = 0 ;
unsigned long long all = 0 ;

node *alloc_node() {
  node *r ;
  all++ ;
  if (free_list != NULL) {
    r = free_list ;
    free_list = free_list->l ;
    again++ ;
  } else {
    r = (node *)malloc(sizeof(node)) ;
    if (r == NULL) {
      fprintf(stderr, "Plus de mémoire") ; 
      exit(2) ;
    }
  }
  r->count = 0 ;
  return r ;
}

void psets(FILE *fp,node *p) {
  if (p == NULL) {
    ;
  } else if (p->m == 0) {
    pset(fp, p->p) ;
  } else {
    psets(fp, p->l) ;
    fprintf(fp,", ") ;
    psets(fp, p->r) ;
  }
}

void psets_card(FILE *fp,node *p,int c) {
  if (p == NULL) {
    ;
  } else if (p->m == 0) {
    if (card(p->p) == c) {
      putc(' ', fp) ;
      pset(fp, p->p) ;
    }
  } else {
    psets_card(fp, p->l,c) ;
    psets_card(fp, p->r, c) ;
  }
}



node *leaf(set s) {
  node *r = alloc_node() ;
  r->p = s ;
  r->m = 0 ;
  return r ;
}




node *branch(set p, set m, node *l, node *r) {
  node *rr = alloc_node() ;
  rr->p = p ; rr->m = m ;
  rr->l = l ; incr(l) ;
  rr->r = r ; incr(r) ;
  return rr ;
}

int zero_bit(set k, set m) {
  return (k & m) == 0 ;
}


int mem(set k, node *p) {
  if(p == NULL)
    return 0 ;
  else if (p->m == 0)
    return p->p == k ;
  else {
    if (zero_bit(k, p->m)) {
      return mem(k, p->l) ;
    } else {
      return mem(k, p->r) ;
    }
  }
    
}

set lowest_bit(set x) {
  return x & (-x) ;
}

set branching_bit(set p0, set p1) {
  return lowest_bit(p0 ^ p1) ;
}

set mask(set p, set m) {
  return p & (m-1) ;
}

node *join(set p0, node *t0, set p1, node *t1) {
  set m = branching_bit(p0, p1) ;
  if (zero_bit(p0, m))
    return branch(mask(p0,m), m, t0, t1) ;
  else
    return branch(mask(p0,m), m, t1, t0) ;
}

int match_prefix(set k, set p, set m) {
  return mask(k,m) == p ;
}

node *ins(set k, node *p) {
  if (p == 0)
    return leaf(k) ;
  incr(p) ;
  if (p->m == 0) {
    if (p->p == k)
      return p ;
    else
      return join(k, leaf(k), p->p, p) ;
  } else {
    node *r ; 
    if (match_prefix(k,p->p,p->m)) {
      if (zero_bit(k,p->m))
        r = branch(p->p, p->m, ins(k,p->l), p->r) ;
      else
        r = branch(p->p, p->m, p->l, ins(k,p->r)) ;
    } else
      r = join(k, leaf(k), p->p, p) ;
    decr(p) ;
    return r ;
  }
}

node *adds(node *r, set s) {
  return ins(s, r) ;
}

#define NMAX 32 
node *chain[NMAX] ;

set merge_sets(elem n, set s1, set s2) {
  return s1 | s2 | singleton(n) ;
}

node *merge1(elem n, set s, node *p, node *r) {
  if (p->m == 0) {
    return adds(r, merge_sets(n, s, p->p)) ;
  } else {
    r = merge1(n, s, p->l, r) ;
    return merge1(n, s, p->r, r) ;
  }
}
node *merge(elem n, node *p1, node *p2, node *r) {
  if (p1->m == 0)
    return merge1(n, p1->p, p2, r) ;
  else {
    r = merge(n, p1->l, p2, r) ;
    return merge(n, p1->r, p2, r) ;
  }
}

int mincard(node *p, int r) {
  if (p->m == 0) {
    int c = card(p->p) ;
    return c < r ? c : r ;
  } else {
    return mincard(p->l, mincard(p->r, r)) ;
  }
}

void final_dump(FILE *fp, node *p, elem n) {
  int c = mincard(p, n) ;
  fprintf(fp, "%d (%d):", n, c) ;
  psets_card(fp, p, c) ;
  putc('\n',fp) ;
  fflush(fp) ;
  /*
  fprintf(stderr, "*********\n") ;
  fprintf(stderr, "%d (%d):", n, c) ;
  dump(stderr, p) ;
  putc('\n',stderr) ;
  fflush(stderr) ;
  */
}

void zyva(int n) {
  elem i  ;
  set s = 0 ;
  s = add(s,1) ;
  chain[1] = leaf(s) ; incr(chain[1]) ;
  final_dump(stdout, chain[1], 1) ;
  for (i = 2 ; i <= n ; i++) {
    int p ;
    node *r = NULL ;
    for (p = 1 ; i-p >= p ; p++) {
      r = merge(i, chain[p], chain[i-p], r) ;
    }
    incr(r) ;
    chain[i] = r ;
    final_dump(stdout, r, i) ;
  }
}

int main(int argc, char **argv) {
  zyva(atoi(argv[1])) ;
  printf("Allocation: %4.2f\n", (100.0 * again) / all) ;
  return 0 ;
}