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

   04/06/05
                                                                           */

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


#define TSIZE 46340

typedef enum
{
   ExprK          = 1,
   ExprProduct    = 2,
   ExprQuotient   = 4,
   ExprSum        = 8,
   ExprDifference = 16

} ExprType;

static struct
{
   ExprType type;
   int length;
   int optimal;
   int a, b;

} Table[TSIZE];
static int Optimal[TSIZE - 1], NOptimal, K, i, j, a, b, g, x, o;

static void SetK(void);
static void InitTable(void);
static void UpdateEntry(void);
static void UpdateEntry0(ExprType t);

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

static void PrintExpr(int n);
static void PrintExprA(int n);
static void PrintExprB(int n);
static void PrintExprMask(int n, int mask);

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

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

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

   return 0;
}


static void SetK(void)
{
   #if 1
      char *key = "`_" "natsumi.c";
   #else
      char *key = "`_" "deepthought.c";
   #endif

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

static void InitTable(void)
{
   for(i = 0; i < TSIZE; i++)
   {
      Table[i].length = TSIZE;
      Table[i].optimal = TSIZE;
   }

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

   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
   {
      g++;
      for(i = 0; i < o; i++)
      {
         a = Optimal[i];
         for(j = 0; j < o; j++)
         {
            b = Optimal[j];
            UpdateEntry();
         }
      }
   } while( (o = NOptimal) < TSIZE - 1 );
}

static void UpdateEntry(void)
{
   if( (x = a * b) < TSIZE )
   {
      UpdateEntry0(ExprProduct);
   }
   if( (a % b) == 0 )
   {
      x = a / b;
      UpdateEntry0(ExprQuotient);
   }
   if( (x = a + b) < TSIZE )
   {
      UpdateEntry0(ExprSum);
   }
   if( (x = a - b) > 1 )
   {
      UpdateEntry0(ExprDifference);
   }
}

static void UpdateEntry0(ExprType t)
{
   if( Table[x].length > Table[a].length + Table[b].length )
   {
      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;
   }
}


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)
{
   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;
         }
      }
      PrintExprA(b);
      (void)putchar('*');
      PrintExprB(n / b);
      if( (n % b) != 0 )
      {
         (void)putchar('+');
         PrintExpr(n % b);
      }
   }
}


static void PrintExpr(int n)
{
   switch( Table[n].type )
   {
      case ExprSum:
         PrintExpr(Table[n].a);
         (void)putchar('+');
         PrintExpr(Table[n].b);
         break;
      case ExprDifference:
         PrintExpr(Table[n].a);
         (void)putchar('-');
         PrintExprB(Table[n].b);
         break;
      case ExprProduct:
         PrintExprA(Table[n].a);
         (void)putchar('*');
         PrintExprB(Table[n].b);
         break;
      case ExprQuotient:
         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:
         printf("%d", K);
         break;
      default:
         break;
   }
}

static void PrintExprA(int n)
{
   PrintExprMask(n, ExprK|ExprProduct);
}

static void PrintExprB(int n)
{
   PrintExprMask(n, ExprK|ExprProduct|ExprQuotient);
}

static void PrintExprMask(int n, int mask)
{
   if( (Table[n].type & mask) == 0 )
   {
      (void)putchar('(');
      PrintExpr(n);
      (void)putchar(')');
   }
   else
   {
      PrintExpr(n);
   }
}