Go to diff to previous submission
#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 value - disp; if (ops[op] == '/') return (disp==0)?-1:(value / disp); 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; }
--- c4.s1213.cteam050.ladybug.cpp.0.ololo.cpp +++ c4.s1244.cteam050.ladybug.cpp.0.ololo.cpp @@ -43,6 +43,6 @@ { if (ops[op] == '+') return disp + value; - if (ops[op] == '-') return disp - value; - if (ops[op] == '/') return (value==0)?-1:(disp / value); + if (ops[op] == '-') return value - disp; + if (ops[op] == '/') return (disp==0)?-1:(value / disp); return disp * value; }