Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

时间:2024-01-21 16:44:15

Problem   Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

Time Limit: 2000 mSec

Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic ShipProblem Description

Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

Input

Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic Ship

Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic ShipOutput

The only line should contain the minimal number of days required for the ship to reach the point (x2,y2)(x2,y2).

If it's impossible then print "-1".

Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic ShipSample Input

0 0
4 6
3
UUU

Educational Codeforces Round 60 (Rated for Div. 2) - C. Magic ShipSample Output

5

题解:第一感觉是bfs,然后大概背包一下之类的,但是数据范围不允许呀,做出这个题的关键点就是注意到运动独立性(呵呵),和如果在第x天能到,那么对于y >= x的都能到,因此就可以二分,固定了天数之后,风吹的距离就是固定的,并且可以用前缀和O(1)求,然后就是判断风吹到的点和目标点的哈密顿距离是否<=天数即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define REP(i, n) for (int i = 1; i <= (n); i++)
#define sqr(x) ((x) * (x)) const int maxn = + ;
const int maxm = + ;
const int maxs = + ; typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd; const LL unit = 1LL;
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const double inf = 1e15;
const double pi = acos(-1.0);
const int SIZE = + ;
const LL MOD = ; LL sx, sy, ex, ey;
LL x[maxn], y[maxn];
LL n;
string str; bool Judge(LL lim)
{
LL m = lim / n, remain = lim % n;
LL xx = sx + m * x[n] + x[remain];
LL yy = sy + m * y[n] + y[remain];
if (abs(xx - ex) + abs(yy - ey) <= lim)
return true;
return false;
} int main()
{
ios::sync_with_stdio(false);
cin.tie();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> sx >> sy >> ex >> ey;
cin >> n;
cin >> str;
LL len = str.size();
for (LL i = ; i < len; i++)
{
if (str[i] == 'U')
{
x[i + ] = x[i];
y[i + ] = y[i] + ;
}
else if (str[i] == 'D')
{
x[i + ] = x[i];
y[i + ] = y[i] - ;
}
else if (str[i] == 'L')
{
x[i + ] = x[i] - ;
y[i + ] = y[i];
}
else
{
x[i + ] = x[i] + ;
y[i + ] = y[i];
}
}
LL le = , ri = LLONG_MAX / ;
LL ans = -;
while (le <= ri)
{
LL mid = (le + ri) / ;
if (Judge(mid))
{
ri = mid - ;
ans = mid;
}
else
{
le = mid + ;
}
}
cout << ans << endl; return ;
}