Mehulcoder

PhonePe2020C

Oct 7th, 2020 (edited)
632
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×