Go to diff to previous submission
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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 && newval > 0) && 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 if(c1[j] != 0) 411 { 412 int newval = nval[q-2][i]/c1[j]; 413 if((newval < 1000 && newval > 0) && disp[newval]==-1) 414 { 415 disp[newval] = q+1; 416 nval[q].push_back(newval); 417 goon = true; 418 if(newval == n) 419 { 420 cout << q+1 << endl; 421 finished = true; 422 } 423 } 424 } 425 } 426 } 427 if(q-3 > 0) 428 { 429 count = nval[q-3].size(); 430 for(int i = 0; i < count; i++) 431 { 432 for(int j = 0; j < c2.size(); j++) 433 { 434 if(c2[j]!=0) 435 { 436 437 438 int newval = nval[q-3][i]/c2[j]; 439 if((newval < 1000 && newval > 0) && disp[newval]==-1) 440 { 441 disp[newval] = q+1; 442 nval[q].push_back(newval); 443 goon = true; 444 if(newval == n) 445 { 446 cout << q+1 << endl; 447 finished = true; 448 } 449 } 450 } 451 } 452 } 453 if(q - 4 > 0) 454 { 455 count = nval[q-4].size(); 456 for(int i = 0; i < count; i++) 457 { 458 for(int j = 0; j < c3.size(); j++) 459 { 460 if(c3[j] != 0) 461 { 462 463 int newval = nval[q-4][i]/c3[j]; 464 if((newval < 1000 && newval > 0) && disp[newval]==-1) 465 { 466 disp[newval] = q+1; 467 nval[q].push_back(newval); 468 goon = true; 469 if(newval == n) 470 { 471 cout << q+1 << endl; 472 finished = true; 473 } 474 } 475 } 476 } 477 } 478 } 479 } 480 } 481 482 q++; 483 } 484 485 if(!finished) 486 cout << "impossible" << endl; 487 } 488 489 return 0; 490 491 } 492
--- c4.s1303.cteam099.ladybug.cpp.0.ladybug.cpp +++ c4.s1320.cteam099.ladybug.cpp.0.ladybug.cpp @@ -152,5 +152,5 @@ { int newval = val+val; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q; @@ -167,5 +167,5 @@ { int newval = val*val; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q; @@ -182,5 +182,5 @@ { int newval = val/val; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q; @@ -208,5 +208,5 @@ { int newval = nval[q-2][i]+c1[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -229,5 +229,5 @@ { int newval = nval[q-3][i]+c2[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -250,5 +250,5 @@ { int newval = nval[q-4][i]+c3[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -275,5 +275,5 @@ { int newval = nval[q-2][i]-c1[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -296,5 +296,5 @@ { int newval = nval[q-3][i]-c2[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -317,5 +317,5 @@ { int newval = nval[q-4][i]-c3[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -342,5 +342,5 @@ { int newval = nval[q-2][i]*c1[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -363,5 +363,5 @@ { int newval = nval[q-3][i]*c2[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -384,5 +384,5 @@ { int newval = nval[q-4][i]*c3[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -408,6 +408,8 @@ for(int j = 0; j < c1.size(); j++) { + if(c1[j] != 0) + { int newval = nval[q-2][i]/c1[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -420,4 +422,5 @@ } } + } } } @@ -429,6 +432,10 @@ for(int j = 0; j < c2.size(); j++) { + if(c2[j]!=0) + { + + int newval = nval[q-3][i]/c2[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -441,4 +448,5 @@ } } + } } } @@ -450,6 +458,9 @@ for(int j = 0; j < c3.size(); j++) { + if(c3[j] != 0) + { + int newval = nval[q-4][i]/c3[j]; - if(newval < 1000 && disp[newval]==-1) + if((newval < 1000 && newval > 0) && disp[newval]==-1) { disp[newval] = q+1; @@ -462,4 +473,5 @@ } } + } } }