Advertisement
Shabdan

Untitled

Feb 18th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pii pair < int, int >
  5. #define fr first
  6. #define sc second
  7. #define int long long
  8.  
  9. using namespace std;
  10.  
  11. pii a, b;
  12. int n;
  13. string s;
  14. pii dif, cur;
  15.  
  16. ll dist(pii A, pii B) {
  17.     return abs(A.fr - B.fr) + abs(A.sc - B.sc);
  18. }
  19.  
  20. bool check(ll mid) {
  21.     ll x = mid / n;
  22.     ll ost = mid % n;
  23.     pii asd;
  24.     asd = {x * dif.fr, x * dif.sc};
  25.     for (int i = 0; i < ost; i++) {
  26.         if (s[i] == 'R') asd.fr++;
  27.         else if (s[i] == 'L') asd.fr--;
  28.         else if (s[i] == 'U') asd.sc++;
  29.         else asd.sc--;
  30.     }
  31.     return dist(b, asd) <= mid;
  32. }
  33.  
  34. main() {
  35.     scanf("%d %d", &a.fr, &a.sc);
  36.     scanf("%d %d", &b.fr, &b.sc);
  37.     b.fr -= a.fr;
  38.     b.sc -= a.sc;
  39.     a = {0, 0};
  40.     scanf("%d", &n);
  41.     cin >> s;
  42.     dif = {0, 0};
  43.     for (int i = 0; i < n; i++) {
  44.         if (s[i] == 'R') dif.fr++;
  45.         else if (s[i] == 'L') dif.fr--;
  46.         else if (s[i] == 'U') dif.sc++;
  47.         else dif.sc--;
  48.     }
  49.     ll l = 0;
  50.     ll r = 1e18;
  51.     while (r - l > 1) {
  52.         ll mid = (l + r) >> 1;
  53.         if (check(mid)) {
  54.             r = mid;
  55.         } else {
  56.             l = mid;
  57.         }
  58.     }
  59.     if (r == (ll)1e18) {
  60.         cout << -1;
  61.         return 0;
  62.     }
  63.     cout << r;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement