ladybug.cpp
1 #include <iostream>
2 #include <string>
3 #include <queue>
4 //#include <tuple>
5
6 #define uint unsigned int
7
8 using namespace std;
9
10 int main()
11 {
12 string chars;
13 int n;
14
15 while(cin >> chars >> n)
16 {
17 vector<int> c1;
18 int i = 0;
19 while((int)chars[i] >= 48 && (int)chars[i] <= 57)
20 {
21 c1.push_back((int)chars[i]-48);
22 i++;
23 }
24 bool plus = false, minus = false, krat = false, deleno = false, rovnasa = false;
25 while(i < chars.length())
26 {
27 switch(chars[i])
28 {
29 case '+':
30 plus = true;
31 break;
32 case '-':
33 minus = true;
34 break;
35 case '*':
36 krat = true;
37 break;
38 case '/':
39 deleno = true;
40 break;
41 case '=':
42 rovnasa = true;
43 }
44 i++;
45 }
46
47 vector<int> c2, c3;
48
49 {
50 int count = c1.size();
51 for(int i = 0; i < count; i++)
52 for(int j = 0; j < count; j++)
53 {
54 c2.push_back(c1[i]*10 + c1[j]);
55 }
56 for(int i = 0; i < count; i++)
57 for(int j = 0; j < count; j++)
58 for(int k = 0; k < count; k++)
59 {
60 c3.push_back(c1[i]*10 + c1[j] + c1[k]*100);
61 }
62 }
63
64 int disp[1000];
65 int valu[1000];
66 for(int i = 0; i < 1000; i++)
67 {
68 disp[i] = -1;
69 valu[i] = -1;
70 }
71 vector<vector<int> > nval;
72
73 if(n == 0)
74 {
75 cout << 0 << endl;
76 continue;
77 }
78 if(!plus && !minus && !krat && !deleno)
79 {
80 cout << "impossible" << endl;
81 continue;
82 }
83
84 bool done = false;
85
86 nval.push_back(vector<int>());
87 nval.push_back(vector<int>());
88 nval.push_back(vector<int>());
89 nval.push_back(vector<int>());
90
91 for(int i = 0; i < c1.size(); i++)
92 {
93 int val = c1[i];
94 if(val == n)
95 {
96 cout << 1 << endl;
97 done = true;
98 }
99 nval[1].push_back(val);
100 disp[val] = 1;
101 valu[val] = 1;
102 }
103
104 if(done) continue;
105
106 for(int i = 0; i < c2.size(); i++)
107 {
108 int val = c2[i];
109 if(val == n)
110 {
111 cout << 2 << endl;
112 done = true;
113 }
114 nval[2].push_back(val);
115 disp[val] = 2;
116 valu[val] = 2;
117 }
118
119 if(done) continue;
120
121 for(int i = 0; i < c3.size(); i++)
122 {
123 int val = c3[i];
124 if(val == n)
125 {
126 cout << 3 << endl;
127 done = true;
128 }
129 nval[3].push_back(val);
130 disp[val] = 3;
131 valu[val] = 3;
132 }
133
134 if(done) continue;
135
136 int q = 3;
137
138 bool goon = true;
139 bool finished = false;
140
141 while(goon && q < 500)
142 {
143 nval.push_back(vector<int>());
144 goon = false;
145 if(rovnasa)
146 {
147 int count = nval[q-2].size();
148 for(int i = 0; i < count; i++)
149 {
150 int val = nval[q-2][i];
151 if(plus)
152 {
153 int newval = val+val;
154 if(newval < 1000 && disp[newval]==-1)
155 {
156 disp[newval] = q;
157 nval[q].push_back(newval);
158 goon = true;
159 if(newval == n)
160 {
161 cout << q << endl;
162 finished = true;
163 }
164 }
165 }
166 if(krat)
167 {
168 int newval = val*val;
169 if(newval < 1000 && disp[newval]==-1)
170 {
171 disp[newval] = q;
172 nval[q].push_back(newval);
173 goon = true;
174 if(newval == n)
175 {
176 cout << q << endl;
177 finished = true;
178 }
179 }
180 }
181 if(deleno)
182 {
183 int newval = val/val;
184 if(newval < 1000 && disp[newval]==-1)
185 {
186 disp[newval] = q;
187 nval[q].push_back(newval);
188 goon = true;
189 if(newval == n)
190 {
191 cout << q << endl;
192 finished = true;
193 }
194 }
195 }
196 }
197 }
198
199 if(finished)
200 continue;
201
202 if(plus)
203 {
204 int count = nval[q-2].size();
205 for(int i = 0; i < count; i++)
206 {
207 for(int j = 0; j < c1.size(); j++)
208 {
209 int newval = nval[q-2][i]+c1[j];
210 if(newval < 1000 && disp[newval]==-1)
211 {
212 disp[newval] = q+1;
213 nval[q].push_back(newval);
214 goon = true;
215 if(newval == n)
216 {
217 cout << q+1 << endl;
218 finished = true;
219 }
220 }
221 }
222 }
223 if(q-3 > 0)
224 {
225 count = nval[q-3].size();
226 for(int i = 0; i < count; i++)
227 {
228 for(int j = 0; j < c2.size(); j++)
229 {
230 int newval = nval[q-3][i]+c2[j];
231 if(newval < 1000 && disp[newval]==-1)
232 {
233 disp[newval] = q+1;
234 nval[q].push_back(newval);
235 goon = true;
236 if(newval == n)
237 {
238 cout << q+1 << endl;
239 finished = true;
240 }
241 }
242 }
243 }
244 if(q - 4 > 0)
245 {
246 count = nval[q-4].size();
247 for(int i = 0; i < count; i++)
248 {
249 for(int j = 0; j < c3.size(); j++)
250 {
251 int newval = nval[q-4][i]+c3[j];
252 if(newval < 1000 && disp[newval]==-1)
253 {
254 disp[newval] = q+1;
255 nval[q].push_back(newval);
256 goon = true;
257 if(newval == n)
258 {
259 cout << q+1 << endl;
260 finished = true;
261 }
262 }
263 }
264 }
265 }
266 }
267 }
268
269 if(minus)
270 {
271 int count = nval[q-2].size();
272 for(int i = 0; i < count; i++)
273 {
274 for(int j = 0; j < c1.size(); j++)
275 {
276 int newval = nval[q-2][i]-c1[j];
277 if(newval < 1000 && disp[newval]==-1)
278 {
279 disp[newval] = q+1;
280 nval[q].push_back(newval);
281 goon = true;
282 if(newval == n)
283 {
284 cout << q+1 << endl;
285 finished = true;
286 }
287 }
288 }
289 }
290 if(q-3 > 0)
291 {
292 count = nval[q-3].size();
293 for(int i = 0; i < count; i++)
294 {
295 for(int j = 0; j < c2.size(); j++)
296 {
297 int newval = nval[q-3][i]-c2[j];
298 if(newval < 1000 && disp[newval]==-1)
299 {
300 disp[newval] = q+1;
301 nval[q].push_back(newval);
302 goon = true;
303 if(newval == n)
304 {
305 cout << q+1 << endl;
306 finished = true;
307 }
308 }
309 }
310 }
311 if(q - 4 > 0)
312 {
313 count = nval[q-4].size();
314 for(int i = 0; i < count; i++)
315 {
316 for(int j = 0; j < c3.size(); j++)
317 {
318 int newval = nval[q-4][i]-c3[j];
319 if(newval < 1000 && disp[newval]==-1)
320 {
321 disp[newval] = q+1;
322 nval[q].push_back(newval);
323 goon = true;
324 if(newval == n)
325 {
326 cout << q+1 << endl;
327 finished = true;
328 }
329 }
330 }
331 }
332 }
333 }
334 }
335
336 if(krat)
337 {
338 int count = nval[q-2].size();
339 for(int i = 0; i < count; i++)
340 {
341 for(int j = 0; j < c1.size(); j++)
342 {
343 int newval = nval[q-2][i]*c1[j];
344 if(newval < 1000 && disp[newval]==-1)
345 {
346 disp[newval] = q+1;
347 nval[q].push_back(newval);
348 goon = true;
349 if(newval == n)
350 {
351 cout << q+1 << endl;
352 finished = true;
353 }
354 }
355 }
356 }
357 if(q-3 > 0)
358 {
359 count = nval[q-3].size();
360 for(int i = 0; i < count; i++)
361 {
362 for(int j = 0; j < c2.size(); j++)
363 {
364 int newval = nval[q-3][i]*c2[j];
365 if(newval < 1000 && disp[newval]==-1)
366 {
367 disp[newval] = q+1;
368 nval[q].push_back(newval);
369 goon = true;
370 if(newval == n)
371 {
372 cout << q+1 << endl;
373 finished = true;
374 }
375 }
376 }
377 }
378 if(q - 4 > 0)
379 {
380 count = nval[q-4].size();
381 for(int i = 0; i < count; i++)
382 {
383 for(int j = 0; j < c3.size(); j++)
384 {
385 int newval = nval[q-4][i]*c3[j];
386 if(newval < 1000 && disp[newval]==-1)
387 {
388 disp[newval] = q+1;
389 nval[q].push_back(newval);
390 goon = true;
391 if(newval == n)
392 {
393 cout << q+1 << endl;
394 finished = true;
395 }
396 }
397 }
398 }
399 }
400 }
401 }
402
403 if(deleno)
404 {
405 int count = nval[q-2].size();
406 for(int i = 0; i < count; i++)
407 {
408 for(int j = 0; j < c1.size(); j++)
409 {
410 int newval = nval[q-2][i]/c1[j];
411 if(newval < 1000 && disp[newval]==-1)
412 {
413 disp[newval] = q+1;
414 nval[q].push_back(newval);
415 goon = true;
416 if(newval == n)
417 {
418 cout << q+1 << endl;
419 finished = true;
420 }
421 }
422 }
423 }
424 if(q-3 > 0)
425 {
426 count = nval[q-3].size();
427 for(int i = 0; i < count; i++)
428 {
429 for(int j = 0; j < c2.size(); j++)
430 {
431 int newval = nval[q-3][i]/c2[j];
432 if(newval < 1000 && disp[newval]==-1)
433 {
434 disp[newval] = q+1;
435 nval[q].push_back(newval);
436 goon = true;
437 if(newval == n)
438 {
439 cout << q+1 << endl;
440 finished = true;
441 }
442 }
443 }
444 }
445 if(q - 4 > 0)
446 {
447 count = nval[q-4].size();
448 for(int i = 0; i < count; i++)
449 {
450 for(int j = 0; j < c3.size(); j++)
451 {
452 int newval = nval[q-4][i]/c3[j];
453 if(newval < 1000 && disp[newval]==-1)
454 {
455 disp[newval] = q+1;
456 nval[q].push_back(newval);
457 goon = true;
458 if(newval == n)
459 {
460 cout << q+1 << endl;
461 finished = true;
462 }
463 }
464 }
465 }
466 }
467 }
468 }
469
470 q++;
471 }
472
473 if(!finished)
474 cout << "impossible" << endl;
475 }
476
477 return 0;
478
479 }
480