Advertisement
savrasov

numb

Aug 26th, 2017
421
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. void add(int &a)
  7. {
  8.     a = (a + 1) % 1000000;
  9. }
  10.  
  11. int main()
  12. {
  13.     int n, m, q[(int)4e6 + 5], h, t;
  14.     vector<int> a(4e5, 1e9);
  15.     cin >> n >> m;
  16.     a[n] = h = t = 0;
  17.     q[h] = n;
  18.     add(h);
  19.     for (;;)
  20.     {
  21.         for (; t != h; add(t))
  22.         {
  23.             int temp = q[t];
  24.             if (temp == m) return cout << a[m], 0;
  25.             if (temp * 2 < 1e5 && a[temp * 2] > a[temp] + 1)
  26.             {
  27.                 a[temp * 2] = a[temp] + 1;
  28.                 q[h] = temp * 2;
  29.                 add(h);
  30.             }
  31.             if (temp > 1 && a[temp - 1] > a[temp] + 1)
  32.             {
  33.                 a[temp - 1] = a[temp] + 1;
  34.                 q[h] = temp - 1;
  35.                 add(h);
  36.             }
  37.         }
  38.     }
  39.     return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement