Source code for submission s813

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. 				return i/j;
  64. 		}
  65. 		return -1;
  66. 	}
  67.  
  68. 	bool valid(){
  69. 		return disp>=0 && disp<1000 && value>=0 && value<1000;
  70. 	}
  71.  
  72. 	void apply(int b){
  73. 		switch(stav){
  74. 			case 0:
  75. 				if(b<10){
  76. 					stav = 1;
  77. 					disp = b;
  78. 				}
  79. 				else{
  80. 					oper = b-9;
  81. 					stav = 2;
  82. 				}
  83. 				break;
  84. 			case 1:
  85. 				if(b<10){
  86. 					disp = 10*disp+b;
  87. 				}
  88. 				else{
  89. 					if(oper!=0 && oper!=5)
  90. 						disp = eval(value, oper,disp);
  91. 					oper = b-9;
  92. 					value = disp;
  93. 					stav = 2;
  94. 				}
  95. 				break;
  96. 			case 2:
  97. 				if(b<10){
  98. 					disp = b;
  99. 					stav = 1;
  100. 				}
  101. 				else{
  102. 					if(b==14&&oper!=5)
  103. 						disp = eval(value, oper,disp);
  104. 					oper = b-9;
  105. 					value = disp;
  106. 				}
  107. 				break;
  108. 		}
  109.  
  110. 	}
  111.  
  112. };
  113.  
  114. bool solve() {
  115. 		if (scanf("%s%d ",str, &R)<0) return false;
  116. 		for(int i=0;i<15;++i)
  117. 			enabled[i] = 0;
  118.  
  119.  
  120. 		for(char* p=str;*p;++p){
  121. 			if(*p>='0'&&*p<='9'){
  122. 				enabled[*p-'0'] = 1;
  123.  
  124. 			}
  125. 			else if(*p=='=')
  126. 				enabled[14]=1;
  127. 			else if(*p=='+')
  128. 				enabled[10]=1;
  129. 			else if(*p=='-')
  130. 				enabled[11]=1;
  131. 			else if(*p=='*')
  132. 				enabled[12]=1;
  133. 			else if(*p=='/')
  134. 				enabled[13]=1;
  135. 		}
  136.  
  137.  
  138. 		for(int i=0;i<1000*1000*3*6;++i)
  139. 			stavy[i] = INF;
  140.  
  141. 		State initial = (State){0,0,0,0};
  142. 		stavy[initial.encode()]=0;
  143. 		queue<int> fronta;
  144. 		fronta.push(initial.encode());
  145. 		while(!fronta.empty()){
  146. 			State curr;
  147. 			int curri = fronta.front();
  148. 			curr.decode(curri);
  149. 			if(curr.disp==R){
  150. 				printf("%d\n",stavy[curri]);
  151. 				return true;
  152. 			}
  153.  
  154. 			fronta.pop();
  155. 			for(int i=0;i<15;++i){
  156. 				if(!enabled[i])
  157. 					continue;
  158. 				State next = curr;
  159. 				next.apply(i);
  160. 				if(next.valid()){
  161. 					int nexti = next.encode();
  162. 					if(stavy[nexti]==INF){
  163. 						stavy[nexti] = stavy[curri]+1;
  164. 						fronta.push(nexti);
  165. 					}
  166. 				}
  167. 			}
  168. 		}
  169. 		printf("impossible\n");
  170.  
  171. 		return true;
  172. }
  173.  
  174. int main() {
  175. 		while(solve());
  176. 		return 0;
  177. }