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

/* Define a structure to store all expressions of n */
typedef struct {
   int n;           /* The number n */
   int nexpr;       /* The number of expressions for n */
   char **expr;     /* The expressions stored in an array of NULL-terminated strings */
   char *etype;     /* Type of the expressions: additive (+) or multiplicative (*) */
   int *ncomp;      /* Number of components (summands for additive, and factors for multiplicative) */
   int **cval;      /* The component values */
   int **cidx;      /* The index of the component expression in the list for the component */
} EXPR;

/* Combine two expressions for j and k to an expression for j op k */
int combineexpr ( char *str, int *cval, int *cidx, int n, EXPR *F, int j, int u, int k, int v, char op )
{
   char e1type, e2type, *tmp;
   int ncomp, ncomp1, ncomp2, *cval1, *cval2, *cidx1, *cidx2, i, w1, w2, src;
   int alloc1, alloc2;

   /* A temporary string for storing intermediate expressions */
   tmp = (char *)malloc(4 * n * sizeof(char));

   /* Types of the the u-th expression for j and v-th expression for k */
   e1type = F[j].etype[u]; e2type = F[k].etype[v];

   if (op == '+') { /* Set n = j + k, and store in the list for n if this is a new expression */
      if (e1type == '+') { /* The expression for j is additive, so use the summand list for j */
         ncomp1 = F[j].ncomp[u];
         cval1 = F[j].cval[u];
         cidx1 = F[j].cidx[u];
         alloc1 = 0;
      } else {             /* The expression for j is multiplicative, so a single summand is created for k */
         ncomp1 = 1;
         cval1 = (int *)malloc(sizeof(int)); cval1[0] = j;
         cidx1 = (int *)malloc(sizeof(int)); cidx1[0] = u;
         alloc1 = 1;
      }
      if (e2type == '+') { /* Likewise for k */
         ncomp2 = F[k].ncomp[v];
         cval2 = F[k].cval[v];
         cidx2 = F[k].cidx[v];
         alloc2 = 0;
      } else {
         ncomp2 = 1;
         cval2 = (int *)malloc(sizeof(int)); cval2[0] = k;
         cidx2 = (int *)malloc(sizeof(int)); cidx2[0] = v;
         alloc2 = 1;
      }

      /* Merge the summand lists for j and k. The summand list should be kept sorted,
         first with respect to summand values, and then with respect to the expression
         indices. */
      w1 = w2 = 0; ncomp = ncomp1 + ncomp2; i = 0; strcpy(str, "");
      while ((w1 < ncomp1) || (w2 < ncomp2)) {
         /* First find from where to take the next summand */
         if (w2 == ncomp2) src = 1;
         else if (w1 == ncomp1) src = 2;
         else if (cval1[w1] < cval2[w2]) src = 1;
         else if ((cval1[w1] == cval2[w2]) && (cidx1[w1] <= cidx2[w2])) src = 1;
         else src = 2;
         if (src == 1) { /* Read summand from the expression of j */
            sprintf(tmp, "%s%s%s", str, (strlen(str) == 0) ? "" : "+", F[cval1[w1]].expr[cidx1[w1]]);
            strcpy(str, tmp);
            cval[i] = cval1[w1]; cidx[i] = cidx1[w1];
            ++w1; ++i;
         } else {        /* Read summand from the expression of k */
            sprintf(tmp, "%s%s%s", str, (strlen(str) == 0) ? "" : "+", F[cval2[w2]].expr[cidx2[w2]]);
            strcpy(str, tmp);
            cval[i] = cval2[w2]; cidx[i] = cidx2[w2];
            ++w2; ++i;
         }
      }
   } else { /* Set n = j * k, and store in the list for n if this is a new expression */
      if (e1type == '*') { /* j is multiplicative, so the components are the factors of j */
         ncomp1 = F[j].ncomp[u];
         cval1 = F[j].cval[u];
         cidx1 = F[j].cidx[u];
         alloc1 = 0;
      } else {             /* j is additive, so a single new parenthesized factor is created */
         ncomp1 = 1;
         cval1 = (int *)malloc(sizeof(int)); cval1[0] = j;
         cidx1 = (int *)malloc(sizeof(int)); cidx1[0] = u;
         alloc1 = 1;
      }
      if (e2type == '*') { /* Likewise for k */
         ncomp2 = F[k].ncomp[v];
         cval2 = F[k].cval[v];
         cidx2 = F[k].cidx[v];
         alloc2 = 0;
      } else {
         ncomp2 = 1;
         cval2 = (int *)malloc(sizeof(int)); cval2[0] = k;
         cidx2 = (int *)malloc(sizeof(int)); cidx2[0] = v;
         alloc2 = 1;
      }

      /* Merge the components in sorted order again */
      w1 = w2 = 0; ncomp = ncomp1 + ncomp2; i = 0; strcpy(str, "");
      while ((w1 < ncomp1) || (w2 < ncomp2)) {
         if (w2 == ncomp2) src = 1;
         else if (w1 == ncomp1) src = 2;
         else if (cval1[w1] < cval2[w2]) src = 1;
         else if ((cval1[w1] == cval2[w2]) && (cidx1[w1] <= cidx2[w2])) src = 1;
         else src = 2;

         /* Copy factor from the appropriate source. Protect the factor by parentheses
            if and only if it is an additive expression. */
         if (src == 1) {
            if (strlen(str) == 0) {
               if ( (e1type == '+') || (F[cval1[w1]].etype[cidx1[w1]] == '+') )
                  sprintf(tmp, "(%s)", F[cval1[w1]].expr[cidx1[w1]]);
               else
                  sprintf(tmp, "%s", F[cval1[w1]].expr[cidx1[w1]]);
            } else {
               if ( (e1type == '+') || (F[cval1[w1]].etype[cidx1[w1]] == '+') )
                  sprintf(tmp, "%s*(%s)", str, F[cval1[w1]].expr[cidx1[w1]]);
               else
                  sprintf(tmp, "%s*%s", str, F[cval1[w1]].expr[cidx1[w1]]);
            }
            strcpy(str, tmp);
            cval[i] = cval1[w1]; cidx[i] = cidx1[w1];
            ++w1; ++i;
         } else {
            if (strlen(str) == 0) {
               if ( (e2type == '+') || (F[cval2[w2]].etype[cidx2[w2]] == '+') )
                  sprintf(tmp, "(%s)", F[cval2[w2]].expr[cidx2[w2]]);
               else
                  sprintf(tmp, "%s", F[cval2[w2]].expr[cidx2[w2]]);
            } else {
               if ( (e2type == '+') || (F[cval2[w2]].etype[cidx2[w2]] == '+') )
                  sprintf(tmp, "%s*(%s)", str, F[cval2[w2]].expr[cidx2[w2]]);
               else
                  sprintf(tmp, "%s*%s", str, F[cval2[w2]].expr[cidx2[w2]]);
            }
            strcpy(str, tmp);
            cval[i] = cval2[w2]; cidx[i] = cidx2[w2];
            ++w2; ++i;
         }
      }
   }
   free(tmp);
   if (alloc1) { free(cval1); free(cidx1); }
   if (alloc2) { free(cval2); free(cidx2); }
   return ncomp;
}

EXPR findallexpr ( int n )
{
   EXPR E, *F;
   int i, j, k, l, s, u, v, w;
   char *str;
   int *cval, *cidx, ncomp;

   str = (char *)malloc(4 * n * sizeof(char));  /* For generated expressions */
   cval = (int *)malloc(n * sizeof(int));       /* Array of component values */
   cidx = (int *)malloc(n * sizeof(int));       /* Array of component indices */

   F = (EXPR *)malloc((n+1) * sizeof(EXPR));    /* F is an array of structures of type EXPR */

   /* 0 has no representation */
   F[0].n = 0;
   F[0].nexpr = 0;
   F[0].expr = NULL;
   F[0].etype = NULL;
   F[0].ncomp = NULL;
   F[0].cval = NULL;
   F[0].cidx = NULL;

   /* 1 has only one expression: 1 (additive) */
   F[1].n = 1;
   F[1].nexpr = 1;
   F[1].expr = (char **)malloc(sizeof(char *));
   F[1].expr[0] = (char *)malloc(2 * sizeof(char));
   strcpy(F[1].expr[0], "1");
   F[1].etype = (char *)malloc(sizeof(char));
   F[1].etype[0] = '+';
   F[1].ncomp = (int *)malloc(sizeof(int));
   F[1].ncomp[0] = 1;
   F[1].cval = (int **)malloc(sizeof(int *));
   F[1].cval[0] = (int *)malloc(sizeof(int));
   F[1].cval[0][0] = 1;
   F[1].cidx = (int **)malloc(sizeof(int *));
   F[1].cidx[0] = (int *)malloc(sizeof(int));
   F[1].cidx[0][0] = 0;

   /* Generate and store all expressions for i = 2, 3, ..., n */
   for (i=2; i<=n; ++i) {
      /* First compute an upper bound on the number of possible expressions for i */
      l = 0;
      for (j=1; j<=i/2; ++j) { /* Additive expressions */
         k = i - j;
         l += F[j].nexpr * F[k].nexpr;
      }
      s = (int)sqrt(i);
      for (j=2; j<=s; ++j) {  /* Multiplicative expressions */
         if (i % j == 0) {
            k = i / j;
            l += F[j].nexpr * F[k].nexpr;
         }
      }
      /* Initially allocate memory based on the upper bound l */
      F[i].n = i;
      F[i].nexpr = l;
      F[i].expr = (char **)malloc(l * sizeof(char *));
      F[i].etype = (char *)malloc(l * sizeof(char));
      F[i].ncomp = (int *)malloc(l * sizeof(int));
      F[i].cval = (int **)malloc(l * sizeof(int *));
      F[i].cidx = (int **)malloc(l * sizeof(int *));

      /* Now identify all different expressions */
      l = 0;
      for (j=1; j<=i/2; ++j) { /* Additive expressions */
         k = i - j;            /* i = k + j */
         for (u=0; u<F[j].nexpr; ++u) {      /* For each expression of j */
            for (v=0; v<F[k].nexpr; ++v) {   /* For each expression of k */
               /* Combine the expressions for j and k. Store thr string in
                  str, the components in cval, and the component indices in cidx */
               ncomp = combineexpr(str, cval, cidx, n, F, j, u, k, v, '+');

               /* Check whether this expression for i is aleady in the list for i */
               for (w=0; w<l; ++w) if (!strcmp(str,F[i].expr[w])) break;

               /* If it is a new expression, store it in the list for i */
               if (w == l) {
                  F[i].expr[l] = (char *)malloc((1 + strlen(str)) * sizeof(char));
                  strcpy(F[i].expr[l], str);
                  F[i].etype[l] = '+';
                  F[i].ncomp[l] = ncomp;
                  F[i].cval[l] = (int *)malloc(ncomp * sizeof(int));
                  F[i].cidx[l] = (int *)malloc(ncomp * sizeof(int));
                  for (w=0; w<ncomp; ++w) {
                     F[i].cval[l][w] = cval[w];
                     F[i].cidx[l][w] = cidx[w];
                  }
                  ++l;
               }
            }
         }
      }
      for (j=2; j<=s; ++j) {  /* Likewise generate all multiplicative expressions i = j * k */
         if (i % j == 0) {
            k = i / j;
            for (u=0; u<F[j].nexpr; ++u) {
               for (v=0; v<F[k].nexpr; ++v) {
                  ncomp = combineexpr(str, cval, cidx, n, F, j, u, k, v, '*');
                  for (w=0; w<l; ++w) if (!strcmp(str,F[i].expr[w])) break;
                  if (w == l) {
                     F[i].expr[l] = (char *)malloc((1 + strlen(str)) * sizeof(char));
                     strcpy(F[i].expr[l], str);
                     F[i].etype[l] = '*';
                     F[i].ncomp[l] = ncomp;
                     F[i].cval[l] = (int *)malloc(ncomp * sizeof(int));
                     F[i].cidx[l] = (int *)malloc(ncomp * sizeof(int));
                     for (w=0; w<ncomp; ++w) {
                        F[i].cval[l][w] = cval[w];
                        F[i].cidx[l][w] = cidx[w];
                     }
                     ++l;
                  }
               }
            }
         }
      }

      /* At this point, we know the exact value of the different number of expressions
         for i. Reallocate memory for the different arrays so as to take exactly the
         required space. */
      F[i].nexpr = l;
      F[i].expr = (char **)realloc(F[i].expr, l * sizeof(char *));
      F[i].etype = (char *)realloc(F[i].etype, l * sizeof(char));
      F[i].ncomp = (int *)realloc(F[i].ncomp, l * sizeof(int));
      F[i].cval = (int **)realloc(F[i].cval, l * sizeof(int *));
      F[i].cidx = (int **)realloc(F[i].cidx, l * sizeof(int *));
   }

   /* All expressions for 1, 2, 3, ..., n are generated. But we are interested
      only the expressions for n (the function is supposed to return only this).
      So copy F[n] to E. */
   E.n = n;
   E.nexpr = F[n].nexpr;
   E.expr = (char **)malloc(E.nexpr * sizeof(char *));
   E.etype = (char *)malloc(E.nexpr * sizeof(char));
   E.ncomp = (int *)malloc(E.nexpr * sizeof(int));
   E.cval = (int **)malloc(E.nexpr * sizeof(int *));
   E.cidx = (int **)malloc(E.nexpr * sizeof(int *));
   for (l=0; l<E.nexpr; ++l) {
      E.expr[l] = (char *)malloc((1 + strlen(F[n].expr[l])) * sizeof(char));
      strcpy(E.expr[l], F[n].expr[l]);
      E.etype[l] = F[n].etype[l];
      E.ncomp[l] = F[n].ncomp[l];
      E.cval[l] = (int *)malloc(E.ncomp[l] * sizeof(int));
      E.cidx[l] = (int *)malloc(E.ncomp[l] * sizeof(int));
      for (w=0; w<E.ncomp[l]; ++w) {
         E.cval[l][w] = F[n].cval[l][w];
         E.cidx[l][w] = F[n].cidx[l][w];
      }
   }

   /* E now stores the relevant return structure. So F can be completely freed. */
   for (i=1; i<=n; ++i) {
      for (l=0; l<F[i].nexpr; ++l) {
         free(F[i].expr[l]);
         free(F[i].cval[l]);
         free(F[i].cidx[l]);
      }
      free(F[i].expr);
      free(F[i].etype);
      free(F[i].ncomp);
      free(F[i].cval);
      free(F[i].cidx);
   }
   free(str);
   free(cval);
   free(cidx);

   return E;
}

/* Count the number of ones in str */
int count1 ( char *str )
{
   char *t;
   int cnt;

   t = str; cnt = 0;
   while (1) {
      t = strchr(t, '1');
      if (t == NULL) break;
      ++cnt;
      ++t;
   }
   return cnt;
}

/* Bubble sorting the expressions */
void sortexpr ( EXPR E )
{
   int m, i, j, k;
   char *t, c;
   int *N1, *p;

   /* Precompte the counts of ones in different expressions */
   m = E.nexpr;
   N1 = (int *)malloc(m * sizeof(int));
   for (i=0; i<m; ++i) N1[i] = count1(E.expr[i]);

   /* Bubble sort */
   for (j=m-2; j>=0; --j) {
      for (i=0; i<=j; ++i) {
         /* First compare number of ones */
         if (N1[i] > N1[i+1]) continue;
         /* In case of a tie, compare the expression lengths */
         if ((N1[i] == N1[i+1]) && (strlen(E.expr[i]) >= strlen(E.expr[i+1]))) continue;

         /* Swap if the i-th and the (i+1)-th expressions are out of order */
         k = N1[i]; N1[i] = N1[i+1]; N1[i+1] = k;
         t = E.expr[i]; E.expr[i] = E.expr[i+1]; E.expr[i+1] = t;
         c = E.etype[i]; E.etype[i] = E.etype[i+1]; E.etype[i+1] = c;
         k = E.ncomp[i]; E.ncomp[i] = E.ncomp[i+1]; E.ncomp[i+1] = k;
         p = E.cval[i]; E.cval[i] = E.cval[i+1]; E.cval[i+1] = p;
         p = E.cidx[i]; E.cidx[i] = E.cval[i+1]; E.cidx[i+1] = p;
      }
   }

   free(N1);
}

void printallexpr ( EXPR E )
{
   int l, k;

   printf("%-3d", E.n);
   for (l=0; l<E.nexpr; ++l) {
      printf("%s = %s = ", (l) ? "   " : "", E.expr[l]);
      printf("%d", E.cval[l][0]);
      for (k=1; k<E.ncomp[l]; ++k) printf(" %c %d", E.etype[l], E.cval[l][k]);
      printf("\n");
   }
   printf("... %d expressions\n", E.nexpr);
}

int main ( int argc, char *argv[] )
{
   int n;
   EXPR E;

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("\nn = %d\n", n);

   E = findallexpr(n);
   printf("\n+++ Before sorting\n");
   printallexpr(E);

   sortexpr(E);
   printf("\n+++ After sorting\n");
   printallexpr(E);

   exit(0);
}