ladybug.cpp

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
#define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
 
const int INF = 1<<29;
typedef long long ll;
///////////////////////////////////////////////////////////////////////////
 
const int NA = 5, MAX = 1000;
const int PLUS = 0, MINUS = 1, MULT = 2, DIV = 3, EQU = 4;
int oper_ind(char c)
{
  switch(c)
  {
    case '+': return PLUS;
    case '-': return MINUS;
    case '*': return MULT;
    case '/': return DIV;
    case '=': return EQU;
  }
  DEBUG("AAAAAAAAAAAAAAAA");
  return -1;
}
 
bool numbers[10];
bool opers[5];
 
int step;
int visited[MAX][MAX][6][3];
int dp[MAX][MAX][6][3];
 
char available[100];
int N;
 
struct State
{
  int disp, value, oper, state;
  State(int _d, int _v, int _o, int _s):
    disp(_d), value(_v), oper(_o), state(_s) {}
 
  bool is_visited() const
  {
    return visited[disp][value][oper][state] == step;
  }
 
  void visit(int val) const
  {
    visited[disp][value][oper][state] = step;
    dp[disp][value][oper][state] = val;
  }
 
  int get_val() const
  {
    return dp[disp][value][oper][state];
  }
 
  bool is_valid() const
  {
    return disp >= 0 && disp < MAX && value >= 0 && value < MAX;
  }
 
  string str() const
  {
    ostringstream os;
    os << "Disp: " << disp << " Value: " << value << " Oper: " << oper << " State: " << state;
    return os.str();
  }
};
 
queue<State> manage;
int update(const State & s, int val)
{
  if (s.is_visited())
    return -1;
  s.visit(val);
  manage.push(s);
  if (s.disp == N)
    return val;
  return -1;
}
 
int eval(int a, int oper, int b)
{
  if (oper == PLUS) return a+b;
  if (oper == MINUS) return a-b;
  if (oper == MULT) return a*b;
  if (oper == DIV) return b?a/b:-1;
  DEBUG("AAAAAAAAAAAAAAAAAAAAA");
  return -1;
}
 
int main()
{
  while (scanf("%s %d", available, &N) == 2)
  {
    if (!N) { printf("0\n"); continue; }
 
    ++step;
    memset(numbers, 0, sizeof(numbers));
    memset(opers, 0, sizeof(opers));
    int len = strlen(available);
    REP(i, len)
    {
      if (available[i] >= '0' && available[i] <= '9')
	numbers[available[i]-'0'] = true;
      else
	opers[oper_ind(available[i])] = true;
    }
 
    manage = queue<State>();
    update(State(0, 0, NA, 0), 0);
    int result = -1;
    while (!manage.empty())
    {
      State s = manage.front();
      manage.pop();
      int val = s.get_val();
      if (s.state == 0)
      {
	// press num
	REP(i, 10)
	{
	  if (!numbers[i]) continue;
	  State s2 = s;
	  s2.disp = i;
	  s2.state = 1;
	  if ((result = update(s2, val+1)) != -1) goto FOUND;
	}
	// press op
	REP(i, NA)
	{
	  if (!opers[i]) continue;
	  State s2 = s;
	  s2.oper = i;
	  s2.state = 2;
	  if ((result = update(s2, val+1)) != -1) goto FOUND;
	}
      }
      else if (s.state == 1)
      {
	// press numb
	REP(i, 10)
	{
	  if (!numbers[i]) continue;
	  State s2 = s;
	  s2.disp = 10*s2.disp+i;
	  if (!s2.is_valid()) continue;
	  if ((result = update(s2, val+1)) != -1) goto FOUND;
	}
	// press op
	REP(i, NA)
	{
	  if (!opers[i]) continue;
	  State s2 = s;
	  if (s2.oper != EQU && s2.oper != NA)
	    s2.disp = eval(s2.value, s2.oper, s2.disp);
	  s2.oper = i;
	  s2.value = s2.disp;
	  s2.state = 2;
	  if (!s2.is_valid()) continue;
	  if ((result = update(s2, val+1)) != -1) goto FOUND;
	}
      }
      else
      {
	// press numb
	REP(i, 10)
	{
	  if (!numbers[i]) continue;
	  State s2 = s;
	  s2.disp = i;
	  s2.state = 1;
	  if ((result = update(s2, val+1)) != -1) goto FOUND;
	}
	// press op
	REP(i, NA)
	{
	  if (!opers[i]) continue;
	  State s2 = s;
	  if (i == EQU && s2.oper != EQU)
	    s2.disp = eval(s2.value, s2.oper, s2.disp);
	  s2.oper = i;
	  s2.value = s2.disp;
	  if (!s2.is_valid()) continue;
	  if ((result = update(s2, val+1)) != -1) goto FOUND;
	}
      }
    }
 
FOUND:
    if (result == -1)
      printf("impossible\n");
    else
      printf("%d\n", result);
  }
 
  return 0;
}