Source code for submission s898

Go to diff to previous submission

ladybug.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cctype>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <algorithm>
  9. #include <deque>
  10. #include <list>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <vector>
  16.  
  17. #define FOR(I,A,B) for(int I = (A); I < (B); ++I)
  18.  
  19. #define INF (int)1e9
  20. #define EPS 1e-9
  21. #define PI 3.14159265358979
  22.  
  23. using namespace std;
  24.  
  25. typedef pair<int, int> ii;
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28.  
  29.  
  30. int stavy[1000*1000*3*6 + 10000];
  31. bool enabled[100];
  32.  
  33. char str[100];
  34. int R;
  35.  
  36. struct State{
  37. int value;
  38. int disp;
  39. int oper;
  40. int stav;
  41.  
  42. int encode(){
  43. return value+1000*disp+1000000*stav+3000000*oper;
  44. }
  45. void decode(int st){
  46. value = st%1000;
  47. st/=1000;
  48. disp = st%1000;
  49. st/=1000;
  50. stav = st%3;
  51. st/=3;
  52. oper = st;
  53. }
  54. static int eval(int i, int op, int j){
  55. switch(op){
  56. case 1:
  57. return i+j;
  58. case 2:
  59. return i-j;
  60. case 3:
  61. return i*j;
  62. case 4:
  63. if(j==0)
  64. return -1;
  65. return i/j;
  66. }
  67. return -1;
  68. }
  69.  
  70. bool valid(){
  71. return disp>=0 && disp<1000 && value>=0 && value<1000;
  72. }
  73.  
  74. void apply(int b){
  75. switch(stav){
  76. case 0:
  77. if(b<10){
  78. stav = 1;
  79. disp = b;
  80. }
  81. else{
  82. oper = b-9;
  83. stav = 2;
  84. }
  85. break;
  86. case 1:
  87. if(b<10){
  88. disp = 10*disp+b;
  89. }
  90. else{
  91. if(oper!=0 && oper!=5)
  92. disp = eval(value, oper,disp);
  93. oper = b-9;
  94. value = disp;
  95. stav = 2;
  96. }
  97. break;
  98. case 2:
  99. if(b<10){
  100. disp = b;
  101. stav = 1;
  102. }
  103. else{
  104. if(b==14&&oper!=5)
  105. disp = eval(value, oper,disp);
  106. oper = b-9;
  107. value = disp;
  108. }
  109. break;
  110. }
  111.  
  112. }
  113.  
  114. };
  115.  
  116. bool solve() {
  117. if (scanf("%s%d ",str, &R)<0) return false;
  118. for(int i=0;i<15;++i)
  119. enabled[i] = 0;
  120.  
  121.  
  122. for(char* p=str;*p;++p){
  123. if(*p>='0'&&*p<='9'){
  124. enabled[*p-'0'] = 1;
  125.  
  126. }
  127. else if(*p=='=')
  128. enabled[14]=1;
  129. else if(*p=='+')
  130. enabled[10]=1;
  131. else if(*p=='-')
  132. enabled[11]=1;
  133. else if(*p=='*')
  134. enabled[12]=1;
  135. else if(*p=='/')
  136. enabled[13]=1;
  137. }
  138.  
  139.  
  140. for(int i=0;i<1000*1000*3*6;++i)
  141. stavy[i] = INF;
  142.  
  143. State initial = (State){0,0,0,0};
  144. stavy[initial.encode()]=0;
  145. queue<int> fronta;
  146. fronta.push(initial.encode());
  147. while(!fronta.empty()){
  148. State curr;
  149. int curri = fronta.front();
  150. curr.decode(curri);
  151. if(curr.disp==R){
  152. printf("%d\n",stavy[curri]);
  153. return true;
  154. }
  155.  
  156. fronta.pop();
  157. for(int i=0;i<15;++i){
  158. if(!enabled[i])
  159. continue;
  160. State next = curr;
  161. next.apply(i);
  162. if(next.valid()){
  163. int nexti = next.encode();
  164. if(stavy[nexti]==INF){
  165. stavy[nexti] = stavy[curri]+1;
  166. fronta.push(nexti);
  167. }
  168. }
  169. }
  170. }
  171. printf("impossible\n");
  172.  
  173. return true;
  174. }
  175.  
  176. int main() {
  177. while(solve());
  178. return 0;
  179. }

Diff to submission s813

ladybug.cpp

--- c4.s813.cteam014.ladybug.cpp.0.ladybug.cpp
+++ c4.s898.cteam014.ladybug.cpp.0.ladybug.cpp
@@ -61,4 +61,6 @@
                                 return i*j;
                         case 4:
+                                if(j==0)
+                                        return -1;
                                 return i/j;
                 }