Source code for submission s1320

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  

Diff to submission s1303

--- 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 @@
                                     }
                                 }
+                                }
                             }
                         }