/* natsumi0.c - Don Yang (uguu.org)

   04/02/05
                                                                           */

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


#define TSIZE 46340  /* Maximum for signed multiply not to overflow 32bit */

typedef enum
{
   ExprSum,             /* n = a + b */
   ExprDifference,      /* n = a - b */
   ExprProduct,         /* n = a * b */
   ExprQuotient,        /* n = a / b */
   ExprK                /* n = K */

} ExprType;

typedef struct
{
   ExprType type;       /* Expression type, above */
   int length;          /* Number of K terms in expression */
   int optimal;         /* Generation which number was made optimal */
   int a, b;            /* Operands */

} Expr;

static Expr Table[TSIZE];
static int Optimal[TSIZE - 1], NOptimal;
static int K;

static void SetK(void);
static void InitTable(void);
static void UpdateEntry(int a, int b, int g);

static void Decompose(int n);
static void DecomposeSmall(int n);
static void DecomposeLarge(int n);

static void PrintExpr(int n);
static void PrintExprA(int a);
static void PrintExprB(int a);

int main(int argc, char **argv)
{
   int i, n;

   if( argc < 2 )
      return printf("%s <number> [...]\n", *argv);
   SetK();
   InitTable();

   for(i = 1; i < argc; i++)
   {
      printf("%d = ", n = atoi(argv[i]));
      if( n < 0 )
      {
         printf("-(");
         Decompose(-n);
         (void)putchar(')');
      }
      else
      {
         Decompose(n);
      }
      (void)putchar('\n');
   }

   return 0;
}


/* Initialize K based on file name (use __FILE__ in final version) */
static void SetK(void)
{
   #if 1
      char *key = "`_" "natsumi.c";
   #else
      char *key = "`_" "deepthought.c";
   #endif
   int x;

   for(x = 0; *key != '\0'; x += (int)*(key++));
   K = (x % 247) + 3;
}

/* Initialize table entries using dynamic programming.  Each table
   entry is assumed to be optimal, though in practice an infinitely
   large table is needed for all lower numbered entries to be optimal. */
static void InitTable(void)
{
   int a, b, g, i, j, o;

   /* Reset table entries */
   for(i = 0; i < TSIZE; i++)
   {
      Table[i].length = TSIZE;
      Table[i].optimal = TSIZE;
   }

   /* Zero */
   Table[0].type = ExprDifference;
   Table[0].length = 0;
   Table[0].a = K;
   Table[0].b = K;
   Table[0].optimal = 1;

   /* K */
   Table[K].type = ExprK;
   Table[K].length = 1;
   Table[K].a =
   Table[K].b = 0;
   Table[K].optimal = g = 0;
   Optimal[0] = K;
   NOptimal = o = 1;

   do
   {
      /* Expand from current set of optimal terms */
      g++;
      for(i = 0; i < o; i++)
      {
         a = Optimal[i];
         assert(a > 0 && a < TSIZE);
         for(j = 0; j < o; j++)
         {
            b = Optimal[j];
            assert(b > 0 && b < TSIZE);
            UpdateEntry(a, b, g);
         }
      }
   } while( (o = NOptimal) < TSIZE - 1 );
}

static void UpdateEntry(int a, int b, int g)
{
   int x;

   #define UPDATE_TABLE(t) \
      if( Table[x].length > Table[a].length + Table[b].length )   \
      {                                                           \
         assert(x > 0 && x < TSIZE);                              \
         Table[x].type = t;                                       \
         Table[x].a = a;                                          \
         Table[x].b = b;                                          \
         Table[x].length = Table[a].length + Table[b].length;     \
         if( Table[x].optimal == TSIZE )                          \
            Optimal[NOptimal++] = x;                              \
         Table[x].optimal = g;                                    \
      }
   if( (x = a * b) < TSIZE )
   {
      UPDATE_TABLE(ExprProduct);
   }
   if( (a % b) == 0 )
   {
      x = a / b;
      UPDATE_TABLE(ExprQuotient);
   }
   if( (x = a + b) < TSIZE )
   {
      UPDATE_TABLE(ExprSum);
   }
   if( (x = a - b) > 1 )
   {
      UPDATE_TABLE(ExprDifference);
   }
}


static void Decompose(int n)
{
   if( n < TSIZE )   DecomposeSmall(n);
   else              DecomposeLarge(n);
}

static void DecomposeSmall(int n)
{
   PrintExpr(n);
}

static void DecomposeLarge(int n)
{
   int i, j, a, b;

   if( n > (TSIZE - 1) * (TSIZE - 1) )
   {
      printf("%d*(", K);
      Decompose(n / K);
      (void)putchar(')');
      if( (n % K) != 0 )
      {
         printf("+(");
         PrintExpr(n % K);
         (void)putchar(')');
      }
   }
   else
   {
      a = n;
      b = 0;
      for(i = 2; i <= (j = n / i); i++)
      {
         if( j >= TSIZE )
            continue;
         if( a > Table[i].length + Table[j].length + Table[n % i].length )
         {
            a = Table[i].length + Table[j].length + Table[n % i].length;
            b = i;
         }
      }
      assert(b > 0);
      PrintExprA(b);
      (void)putchar('*');
      PrintExprB(n / b);
      if( (n % b) != 0 )
      {
         (void)putchar('+');
         PrintExpr(n % b);
      }
   }
}


static void PrintExpr(int n)
{
   assert(n >= 0 && n < TSIZE);
   switch( Table[n].type )
   {
      case ExprSum:             /* n = a + b */
         PrintExpr(Table[n].a);
         (void)putchar('+');
         PrintExpr(Table[n].b);
         break;
      case ExprDifference:      /* n = a - b */
         PrintExpr(Table[n].a);
         (void)putchar('-');
         PrintExprB(Table[n].b);
         break;
      case ExprProduct:         /* n = a * b */
         PrintExprA(Table[n].a);
         (void)putchar('*');
         PrintExprB(Table[n].b);
         break;
      case ExprQuotient:        /* n = a / b */
         PrintExprA(Table[n].a);
         (void)putchar('/');
         if( Table[n].b != K )
         {
            (void)putchar('(');
            PrintExpr(Table[n].b);
            (void)putchar(')');
         }
         else
         {
            PrintExpr(K);
         }
         break;
      case ExprK:               /* n = K */
         printf("%d", K);
         break;
      default:
         assert(0);
         break;
   }
}

static void PrintExprA(int a)
{
   if( Table[a].type != ExprK && Table[a].type != ExprProduct )
   {
      (void)putchar('(');
      PrintExpr(a);
      (void)putchar(')');
   }
   else
   {
      PrintExpr(a);
   }
}

static void PrintExprB(int a)
{
   if( Table[a].type != ExprK &&
       Table[a].type != ExprProduct &&
       Table[a].type != ExprQuotient )
   {
      (void)putchar('(');
      PrintExpr(a);
      (void)putchar(')');
   }
   else
   {
      PrintExpr(a);
   }
}