/*
 A.P.Selby June 2000
 (1) an atom, (2) +, (3) -, (4) *, (5) /
 st[i]=pointer into tr of i^th tree (i<sp)
 Canonical wrt commutative, associative, and a-(b-c)=a+c-b, a/(b/c)=ac/b type thing
 Also knows a-b(c-d)=a+b(d-c) type thing
 Doesn't know (a-b)(c-d)=(b-a)(d-c)
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NN 50
struct tree {int v,n,o,l,r,s;} tr[NN*2];
int tf,tg,ll[1000],nm[NN],nc,nt,st[NN],lt;
char rc[1000][15*NN+1],l[15*NN+1],tc[15*NN+1];

int cmp(int t0,int t1){
  int c;
  if(tr[t0].o==1&&tr[t1].o==1)return tr[t0].v-tr[t1].v;
  if(tr[t0].o!=tr[t1].o)return tr[t0].o-tr[t1].o;
  c=cmp(tr[t0].l,tr[t1].l);
  if(c!=0)return c;
  return cmp(tr[t0].r,tr[t1].r);
}
int gte(int t0,int t1){return cmp(t0,t1)>=0;}

void desc(char *l,int t){
  int o,o0,o1,b0,b1;
  char *l1;
  if(tr[t].o==1){sprintf(l,"%d",tr[t].v);return;}
  o=tr[t].o>>1;
  o0=tr[tr[t].l].o>>1;b0=(o==2&&o0==1);
  o1=tr[tr[t].r].o>>1;b1=(o==2&&o1==1);
  l1=l;
  if(b0)*(l1++)='('; desc(l1,tr[t].l);l1+=strlen(l1); if(b0)*(l1++)=')';
  *(l1++)="+-*/"[tr[t].o-2];
  if(b1)*(l1++)='('; desc(l1,tr[t].r);l1+=strlen(l1); if(b1)*(l1++)=')';
  *l1=0;
}

void fn(int sp,int tp,int nn){
  int i,j,n,o0,o1,s0,s1,t0,t1,v0,v1,le,le1,tos;
  nc++;
  if(sp==1){
    tos=tr[st[0]].v;n=tr[st[0]].n;
    if(sp==1&&tos>=0&&tos<1000&&n<ll[tos]){desc(rc[tos],st[0]);ll[tos]=n;}
    if(sp==1&&tf&&tos==tg){desc(l,st[0]);nt++;printf("%s\n",l);if(n<lt){strcpy(tc,l);lt=n;}}
  }
  for(i=0;i<nn;i++)if(i==0||nm[i-1]!=nm[i]){
    st[sp]=tp;tr[tp].v=nm[i];tr[tp].n=1;tr[tp].o=1;tr[tp].s=0;
    for(j=i;j<nn-1;j++)nm[j]=nm[j+1];
    fn(sp+1,tp+1,nn-1);
    for(j=nn-1;j>i;j--)nm[j]=nm[j-1];
    nm[i]=tr[tp].v;
  }
  if(sp>=2){
    t0=st[sp-2];t1=st[sp-1]; tr[tp].l=t0;tr[tp].r=t1; st[sp-2]=tp;
    tr[tp].n=tr[t0].n+tr[t1].n+1;
    o0=tr[t0].o;o1=tr[t1].o;
    s0=tr[t0].s;s1=tr[t1].s;
    v0=tr[t0].v;v1=tr[t1].v;
    le=gte(t0,t1);if(o0>1)le1=gte(tr[t0].r,t1);
    if(o0!=3&&(o1>>1)!=1&&((o0!=2&&le)||(o0==2&&le1))){tr[tp].v=v0+v1;tr[tp].o=2;tr[tp].s=s0&&s1;fn(sp-1,tp+1,nn);}
    if(!s1&&(o1>>1)!=1&&(o0!=3||le1)){tr[tp].v=v0-v1;tr[tp].o=3;tr[tp].s=1;fn(sp-1,tp+1,nn);}
    if(o0!=5&&(o1>>1)!=2&&((o0!=4&&le)||(o0==4&&le1))){tr[tp].v=v0*v1;tr[tp].o=4;tr[tp].s=s0||s1;fn(sp-1,tp+1,nn);}
    if((o1>>1)!=2&&(o0!=5||le1)&&v1!=0&&v0%v1==0){tr[tp].v=v0/v1;tr[tp].o=5;tr[tp].s=s0||s1;fn(sp-1,tp+1,nn);}
    st[sp-2]=t0;st[sp-1]=t1;
  }
}

int cmp1(const void *x,const void *y){return *(int*)x-*(int*)y;}

int main(int ac,char **av){
  int i,r,nn;
  if(ac==1){printf("Type, e.g., ngs 1 2 3 7 10 25 t867\nt867, the target, is optional\n");exit(1);}
  for(i=1,nn=0;i<ac;i++){
    if(av[i][0]=='t'){tg=atoi(av[i]+1);tf=1;continue;}
    if(nn>=NN){printf("Too many numbers (maximum %d)\n",NN);exit(1);}
    nm[nn++]=atoi(av[i]);
  }
  qsort(nm,nn,sizeof(int),cmp1);
  printf("Using ");for(i=0;i<nn;i++)printf("%d ",nm[i]);printf("\n");
  if(tf){printf("Target %d\n",tg);nt=0;lt=1000000;}
  for(i=0;i<1000;i++)ll[i]=1000000;
  nc=0;
  fn(0,0,nn);
  printf("%d nodes examined\n",nc);
  if(tf){
    printf("%d way%s of reaching target\n",nt,nt==1?"":"s");
    if(nt)printf("Simplest way %s\n",tc);
  }else
    for(i=0;i<1000;i++){
      printf("%3d: ",i);
      if(ll[i]==1000000)printf("UNREACHABLE\n"); else printf("%s\n",rc[i]);
    }
  printf("Can't reach: ");
  for(i=0,r=0;i<1000;i++)if(ll[i]==1000000)printf("%d ",i); else r++;
  printf("\n");
  printf("Number reachable = %d\nNumber unreachable = %d\n",r,1000-r);
  return 0;
}