ololo.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cstring>
#include <string>
#include <map>
 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FI(i,b) FOR(i,0,b)
#define V(t) vector < t >
#define pb push_back
#define MEMS(a,b) memset((a),(b),sizeof(a))
#define U unsigned
#define LL long long
#define pnt pair<int,int>
#define mp make_pair
 
using namespace std;
 
 
 
int opsCnt = 5;
string ops="+-*/=N";
int allowedOps[300];
int wasMarker = 0;
int allowedNums[22];
int target;
 
int w[1000][1000][6][3];
 
struct state
{
  int value,disp,op,st;
  state() { value = disp =  0; op = 5; st = 0; }
  state(int v, int d, int o):value(v),disp(d),op(o){};
  int getWas() { return w[value][disp][op][st]; }
  void setWas(int v) { w[value][disp][op][st] = v; }
 
  int eval()
  {
    if (ops[op] == '+') return disp + value;
    if (ops[op] == '-') return disp - value;
    if (ops[op] == '/') return (value==0)?-1:(disp / value);
    return disp * value;
  }
 
};
 
// S - 0
// N - 1
// O - 2
 
int init()
{
  FI(i,ops.size()) allowedOps[ops[i]] = 0;
  FI(i,10) allowedNums[i]=0;
  allowedOps['N'] = 1;
  ++wasMarker;
}
 
 
 
int d[19000000];
state q[19000000];
 
 
 
 
int main()
{
  char s[100];
  init();
  while (scanf("%s %d",s,&target)!=EOF)
  {
    FI(i,strlen(s))
    if (s[i]>='0' && s[i]<='9') allowedNums[s[i]-'0'] = 1;
    else allowedOps[s[i]] = 1;
 
    state start;
    int lq = 0, rq = 1;
    d[0]=0;
    q[0]=start;
    int res = -1;
    while (lq < rq)
    {
       state cur = q[lq];
 
      // printf("%d %d %c %d\n",cur.disp,cur.value,ops[cur.op],cur.st);
 
       if (cur.disp == target) { res = d[lq]; break; }
       if (cur.st == 0)
       {
	  FI(i,10) if (allowedNums[i])
	  {
	    state go = cur;
	    go.disp = i;
	    go.st = 1;
 
	    if (go.getWas() != wasMarker) 
	    {
	      go.setWas(wasMarker);
	      q[rq] = go;
	      d[rq] = d[lq]+1;
	      rq++;
	    }
	  }
 
	  FI(i,opsCnt) if (allowedOps[ops[i]])
	  {
	    state go = cur;
	    go.op = i;
	    go.st = 2;
 
	    if (go.getWas() != wasMarker) 
	    {
	      go.setWas(wasMarker);
	      q[rq] = go;
	      d[rq] = d[lq]+1;
	      rq++;
	    }
	  }
 
       }
 
 
       else if (cur.st ==1)
       {
	  FI(i,10) if (allowedNums[i])
	  {
	    state go = cur;
	    go.st = 1;
	    go.disp = go.disp*10+i;
	    if (go.disp>999) continue;
 
 
	    if (go.getWas() != wasMarker) 
	    {
	      go.setWas(wasMarker);
	      q[rq] = go;
	      d[rq] = d[lq]+1;
	      rq++;
	    }
	  }
	  FI(i,opsCnt) if (allowedOps[ops[i]])
	  {
	    state go = cur;
	    go.st = 2;
	    if (ops[go.op] != '=' && ops[go.op]!='N')
	    {
	      go.disp = go.eval();
	      if (go.disp < 0 || go.disp > 999) continue;
	    }
	    go.op = i;
	    go.value = go.disp;
 
 
	    if (go.getWas() != wasMarker) 
	    {
	      go.setWas(wasMarker);
	      q[rq] = go;
	      d[rq] = d[lq]+1;
	      rq++;
	    }
	  }
 
       } else
       {
	  FI(i,10) if (allowedNums[i])
	  {
	    state go = cur;
	    go.disp = i;
	    go.st = 1;
 
	    if (go.getWas() != wasMarker) 
	    {    	      
	      go.setWas(wasMarker);
	      q[rq] = go;
	      d[rq] = d[lq]+1;
	      rq++;
	    }
	  }
	  FI(i,opsCnt) if (allowedOps[ops[i]])
	  {
	    state go = cur;
	    go.st = 2;
	    if (ops[go.op] != '=' && ops[i] == '=')
	    {
	      go.disp = go.eval();
	      if (go.disp < 0 || go.disp > 999) continue;
	    }
	    go.op = i;
	    go.value = go.disp;
 
 
	    if (go.getWas() != wasMarker) 
	    {
	      go.setWas(wasMarker);
	      q[rq] = go;
	      d[rq] = d[lq]+1;
	      rq++;
	    }
	  }
 
       }
 
       lq++;
    }
 
    if (res==-1) printf("impossible\n");
    else printf("%d\n",res);
    init();
  }
  return 0;
}