Source code for submission s1213

ololo.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <memory.h>
  6. #include <cstring>
  7. #include <string>
  8. #include <map>
  9.  
  10.  
  11. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  12. #define FI(i,b) FOR(i,0,b)
  13. #define V(t) vector < t >
  14. #define pb push_back
  15. #define MEMS(a,b) memset((a),(b),sizeof(a))
  16. #define U unsigned
  17. #define LL long long
  18. #define pnt pair<int,int>
  19. #define mp make_pair
  20.  
  21. using namespace std;
  22.  
  23.  
  24.  
  25. int opsCnt = 5;
  26. string ops="+-*/=N";
  27. int allowedOps[300];
  28. int wasMarker = 0;
  29. int allowedNums[22];
  30. int target;
  31.  
  32. int w[1000][1000][6][3];
  33.  
  34. struct state
  35. {
  36. int value,disp,op,st;
  37. state() { value = disp = 0; op = 5; st = 0; }
  38. state(int v, int d, int o):value(v),disp(d),op(o){};
  39. int getWas() { return w[value][disp][op][st]; }
  40. void setWas(int v) { w[value][disp][op][st] = v; }
  41.  
  42. int eval()
  43. {
  44. if (ops[op] == '+') return disp + value;
  45. if (ops[op] == '-') return disp - value;
  46. if (ops[op] == '/') return (value==0)?-1:(disp / value);
  47. return disp * value;
  48. }
  49.  
  50. };
  51.  
  52. // S - 0
  53. // N - 1
  54. // O - 2
  55.  
  56. int init()
  57. {
  58. FI(i,ops.size()) allowedOps[ops[i]] = 0;
  59. FI(i,10) allowedNums[i]=0;
  60. allowedOps['N'] = 1;
  61. ++wasMarker;
  62. }
  63.  
  64.  
  65.  
  66. int d[19000000];
  67. state q[19000000];
  68.  
  69.  
  70.  
  71.  
  72. int main()
  73. {
  74. char s[100];
  75. init();
  76. while (scanf("%s %d",s,&target)!=EOF)
  77. {
  78. FI(i,strlen(s))
  79. if (s[i]>='0' && s[i]<='9') allowedNums[s[i]-'0'] = 1;
  80. else allowedOps[s[i]] = 1;
  81.  
  82. state start;
  83. int lq = 0, rq = 1;
  84. d[0]=0;
  85. q[0]=start;
  86. int res = -1;
  87. while (lq < rq)
  88. {
  89. state cur = q[lq];
  90.  
  91. // printf("%d %d %c %d\n",cur.disp,cur.value,ops[cur.op],cur.st);
  92.  
  93. if (cur.disp == target) { res = d[lq]; break; }
  94. if (cur.st == 0)
  95. {
  96. FI(i,10) if (allowedNums[i])
  97. {
  98. state go = cur;
  99. go.disp = i;
  100. go.st = 1;
  101.  
  102. if (go.getWas() != wasMarker)
  103. {
  104. go.setWas(wasMarker);
  105. q[rq] = go;
  106. d[rq] = d[lq]+1;
  107. rq++;
  108. }
  109. }
  110.  
  111. FI(i,opsCnt) if (allowedOps[ops[i]])
  112. {
  113. state go = cur;
  114. go.op = i;
  115. go.st = 2;
  116.  
  117. if (go.getWas() != wasMarker)
  118. {
  119. go.setWas(wasMarker);
  120. q[rq] = go;
  121. d[rq] = d[lq]+1;
  122. rq++;
  123. }
  124. }
  125.  
  126. }
  127.  
  128.  
  129. else if (cur.st ==1)
  130. {
  131. FI(i,10) if (allowedNums[i])
  132. {
  133. state go = cur;
  134. go.st = 1;
  135. go.disp = go.disp*10+i;
  136. if (go.disp>999) continue;
  137.  
  138.  
  139. if (go.getWas() != wasMarker)
  140. {
  141. go.setWas(wasMarker);
  142. q[rq] = go;
  143. d[rq] = d[lq]+1;
  144. rq++;
  145. }
  146. }
  147. FI(i,opsCnt) if (allowedOps[ops[i]])
  148. {
  149. state go = cur;
  150. go.st = 2;
  151. if (ops[go.op] != '=' && ops[go.op]!='N')
  152. {
  153. go.disp = go.eval();
  154. if (go.disp < 0 || go.disp > 999) continue;
  155. }
  156. go.op = i;
  157. go.value = go.disp;
  158.  
  159.  
  160. if (go.getWas() != wasMarker)
  161. {
  162. go.setWas(wasMarker);
  163. q[rq] = go;
  164. d[rq] = d[lq]+1;
  165. rq++;
  166. }
  167. }
  168.  
  169. } else
  170. {
  171. FI(i,10) if (allowedNums[i])
  172. {
  173. state go = cur;
  174. go.disp = i;
  175. go.st = 1;
  176.  
  177. if (go.getWas() != wasMarker)
  178. {
  179. go.setWas(wasMarker);
  180. q[rq] = go;
  181. d[rq] = d[lq]+1;
  182. rq++;
  183. }
  184. }
  185. FI(i,opsCnt) if (allowedOps[ops[i]])
  186. {
  187. state go = cur;
  188. go.st = 2;
  189. if (ops[go.op] != '=' && ops[i] == '=')
  190. {
  191. go.disp = go.eval();
  192. if (go.disp < 0 || go.disp > 999) continue;
  193. }
  194. go.op = i;
  195. go.value = go.disp;
  196.  
  197.  
  198. if (go.getWas() != wasMarker)
  199. {
  200. go.setWas(wasMarker);
  201. q[rq] = go;
  202. d[rq] = d[lq]+1;
  203. rq++;
  204. }
  205. }
  206.  
  207. }
  208.  
  209. lq++;
  210. }
  211.  
  212. if (res==-1) printf("impossible\n");
  213. else printf("%d\n",res);
  214. init();
  215. }
  216. return 0;
  217. }