cf Educational Codeforces Round 60 C. Magic Ship

原題：

C. Magic Ship

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

You a captain of a ship. Initially you are standing in a point (x1,y1) (obviously, all positions in the sea can be described by cartesian plane) and you want to travel to a point (x2,y2).

You know the weather forecast — the string s of length n, consisting only of letters U, D, L and R. The letter corresponds to a direction of wind. Moreover, the forecast is periodic, e.g. the first day wind blows to the side s1, the second day — s2, the n-th day — sn and (n+1)-th day — s1 again and so on.

Ship coordinates change the following way:

if wind blows the direction U, then the ship moves from (x,y) to (x,y+1);

if wind blows the direction D, then the ship moves from (x,y) to (x,y−1);

if wind blows the direction L, then the ship moves from (x,y) to (x−1,y);

if wind blows the direction R, then the ship moves from (x,y) to (x+1,y).

The ship can also either go one of the four directions or stay in place each day. If it goes then it’s exactly 1 unit of distance. Transpositions of the ship and the wind add up. If the ship stays in place, then only the direction of wind counts. For example, if wind blows the direction U and the ship moves the direction L, then from point (x,y) it will move to the point (x−1,y+1), and if it goes the direction U, then it will move to the point (x,y+2).

You task is to determine the minimal number of days required for the ship to reach the point (x2,y2).

Input

The first line contains two integers x1,y1 (0≤x1,y1≤10^9) — the initial coordinates of the ship.

The second line contains two integers x2,y2 (0≤x2,y2≤10^9) — the coordinates of the destination point.

It is guaranteed that the initial coordinates and destination point coordinates are different.

The third line contains a single integer n (1≤n≤10^5) — the length of the string s.

The fourth line contains the string s itself, consisting only of letters U, D, L and R.

Output

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

If it’s impossible then print “-1”.

Examples

input

0 0

4 6

3

UUU

output

5

input

0 3

0 0

3

UDD

output

3

input

0 0

0 1

1

L

output

-1

Note

In the first example the ship should perform the following sequence of moves: “RRRRU”. Then its coordinates will change accordingly: (0,0) → (1,1) → (2,2) → (3,3) → (4,4) → (4,6).

In the second example the ship should perform the following sequence of moves: “DD” (the third day it should stay in place). Then its coordinates will change accordingly: (0,3) → (0,3) → (0,1) → (0,0).

In the third example the ship can never reach the point (0,1).

中文：

有一艘小船起點在(x1,y1)，可以在每個機關時刻向上下左右四個方向移動一步，或者靜止不動。此外，給你一個字元串，表示目前時刻的風向，如果周遊到字元串的結尾，則重新回到字元串的開始端。風會把小船向一個方向吹動一步，如果風向與小船移動的方向相同，那麼小船可以在機關時刻移動兩步，其它同理，風向的字元串現在給你一個終點(x2,y2)，問你小船最少走多少步可以到終點，如果不能到終點輸出-1。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=100005;

ll x[maxn],y[maxn];
ll stx,sty,sex,sey;
int n;
string s;

int main()
{
	ios::sync_with_stdio(false);
    while(cin>>stx>>sty>>sex>>sey)
    {
        cin>>n>>s;
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for(int i=1;i<=n;i++)
        {
            if(s[i-1]=='L')
            {
                x[i]=x[i-1]-1;
                y[i]=y[i-1];
            }
            if(s[i-1]=='R')
            {
                x[i]=x[i-1]+1;
                y[i]=y[i-1];
            }
            if(s[i-1]=='U')
            {
                x[i]=x[i-1];
                y[i]=y[i-1]+1;
            }
            if(s[i-1]=='D')
            {
                x[i]=x[i-1];
                y[i]=y[i-1]-1;
            }
        }

        ll L=0,R=1e18,mid,cnt,rem,tx,ty,dist;
        while(R-L>1)
        {
            mid=(L+R)>>1;

            cnt=mid/n;
            rem=mid%n;

            tx=stx+x[rem]+cnt*x[n];
            ty=sty+y[rem]+cnt*y[n];


            dist = abs(tx-sex)+abs(ty-sey);


            if(dist<=mid)
                R=mid;
            else
                L=mid;
        }
        if(R>5e17)
            R=-1;
        cout<<R<<endl;
    }
	return 0;
}
           

解答：

拿到題目都分析，第一想法是找下簡單的規律，發現風向的字元串中向左與向右的風向可以抵消，同理上下。如果移動步數超過風向字元串的長度，可以先利用此規律計算小船可以移動到距離終點最近的點。但是鼓秋了半天沒搞出來，情況太複雜-_-|||

看了題解才知道，這題需要用二分處理，做法很巧妙，每次二分需要移動的步數k，那麼風吹動小船的次數也是k，先不考慮小船移動，僅看風向小船會達到哪一個位置(x3,y3)，然後判斷(x3,y3)距離終點(x2,y2)能否在k步走完即可。

回想一下這道題目還是蠻簡單的，沒考慮到問題題目的點，怪自己太生疏…~ _ ~|||