Go to diff to previous submission
#include <cstdio> #include <cstdlib> #include <cmath> #include <cctype> #include <climits> #include <cstring> #include <string> #include <algorithm> #include <deque> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <vector> #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define INF (int)1e9 #define EPS 1e-9 #define PI 3.14159265358979 using namespace std; typedef pair<int, int> ii; typedef long long ll; typedef unsigned long long ull; int stavy[1000*1000*3*6 + 10000]; bool enabled[100]; char str[100]; int R; struct State{ int value; int disp; int oper; int stav; int encode(){ return value+1000*disp+1000000*stav+3000000*oper; } void decode(int st){ value = st%1000; st/=1000; disp = st%1000; st/=1000; stav = st%3; st/=3; oper = st; } static int eval(int i, int op, int j){ switch(op){ case 1: return i+j; case 2: return i-j; case 3: return i*j; case 4: if(j==0) return -1; return i/j; } return -1; } bool valid(){ return disp>=0 && disp<1000 && value>=0 && value<1000; } void apply(int b){ switch(stav){ case 0: if(b<10){ stav = 1; disp = b; } else{ oper = b-9; stav = 2; } break; case 1: if(b<10){ disp = 10*disp+b; } else{ if(oper!=0 && oper!=5) disp = eval(value, oper,disp); oper = b-9; value = disp; stav = 2; } break; case 2: if(b<10){ disp = b; stav = 1; } else{ if(b==14&&oper!=5) disp = eval(value, oper,disp); oper = b-9; value = disp; } break; } } }; bool solve() { if (scanf("%s%d ",str, &R)<0) return false; for(int i=0;i<15;++i) enabled[i] = 0; for(char* p=str;*p;++p){ if(*p>='0'&&*p<='9'){ enabled[*p-'0'] = 1; } else if(*p=='=') enabled[14]=1; else if(*p=='+') enabled[10]=1; else if(*p=='-') enabled[11]=1; else if(*p=='*') enabled[12]=1; else if(*p=='/') enabled[13]=1; } for(int i=0;i<1000*1000*3*6;++i) stavy[i] = INF; State initial = (State){0,0,0,0}; stavy[initial.encode()]=0; queue<int> fronta; fronta.push(initial.encode()); while(!fronta.empty()){ State curr; int curri = fronta.front(); curr.decode(curri); if(curr.disp==R){ printf("%d\n",stavy[curri]); return true; } fronta.pop(); for(int i=0;i<15;++i){ if(!enabled[i]) continue; State next = curr; next.apply(i); if(next.valid()){ int nexti = next.encode(); if(stavy[nexti]==INF){ stavy[nexti] = stavy[curri]+1; fronta.push(nexti); } } } } printf("impossible\n"); return true; } int main() { while(solve()); return 0; }