Mehulcoder

PhonePe2020C

Oct 7th, 2020 (edited)
425
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Author: Mehul Chaturvedi
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. #define vll vector<long long>
  10. #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
  11.  
  12. /*
  13. * x and y are <= 1e12, that means the count of their parent+parent's parent + .... + root
  14. * is less than equal to log_N(1e12) <= 40. So we can store the ancestors of both the vertices
  15. * till, the root(0). And check what part is common from the end between both of them. If
  16. * we remove that common part then, the remaining elements' count will be the answer
  17.  
  18. * Also, it can easily be seen that the child of the node named i are : in+1, in+2...in+n
  19. * So the parent of the node j will be (j-1)/n. (0 based index)
  20. */
  21.  
  22. ll n, x, y;
  23. void solve() {
  24.     cin >> n >> x >> y;
  25.     x--; y--;
  26.  
  27.     if (x < y) swap(x, y);
  28.     //X is the greater one now
  29.  
  30.     ll parx = x;
  31.     ll pary = y;
  32.  
  33.     vll a, b;
  34.     bool flaga = 0, flagb = 0;
  35.     while (1) {
  36.         if (!flaga) {
  37.             a.push_back(parx);
  38.             if (parx == 0) flaga = 1;
  39.         }
  40.         if (!flagb) {
  41.             b.push_back(pary);
  42.             if (pary == 0) flagb = 1;
  43.         }
  44.  
  45.         parx = (parx - 1) / n;
  46.         pary = (pary - 1) / n;
  47.  
  48.         if (flaga && flagb) break;
  49.     }
  50.  
  51.  
  52.     ll i = a.size() - 1;
  53.     ll j = b.size() - 1;
  54.  
  55.     while (1) {
  56.         if (a[i] != b[j]) {
  57.             cout << i + j + 2 << '\n';
  58.             return;
  59.         }
  60.         i--;
  61.         j--;
  62.     }
  63.  
  64.     return;
  65.  
  66.  
  67. }
  68.  
  69. int main(int argc , char ** argv) {
  70.     ios_base::sync_with_stdio(false) ;
  71.     cin.tie(NULL) ;
  72.  
  73.     ll t = 1;
  74.     while (t--) {
  75.         solve();
  76.     }
  77.  
  78.     return 0 ;
  79. }
RAW Paste Data