CodeForces - 1073C Vasya and Robot 好题+就差二分

122 阅读 0 评论 81 点赞

我是靠谱客的博主精明蜜粉，最近开发中收集的这篇文章主要介绍CodeForces - 1073C Vasya and Robot 好题+就差二分，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C. Vasya and Robot

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell (0,0)(0,0). Robot can perform the following four kinds of operations:

U — move from (x,y)(x,y) to (x,y+1)(x,y+1);
D — move from (x,y)(x,y) to (x,y−1)(x,y−1);
L — move from (x,y)(x,y) to (x−1,y)(x−1,y);
R — move from (x,y)(x,y) to (x+1,y)(x+1,y).

Vasya also has got a sequence of nn operations. Vasya wants to modify this sequence so after performing it the robot will end up in (x,y)(x,y).

Vasya wants to change the sequence so the length of changed subsegment is minimum possible. This length can be calculated as follows: maxID−minID+1maxID−minID+1, where maxIDmaxID is the maximum index of a changed operation, and minIDminID is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices 22, 55 and 77 are changed, so the length of changed subsegment is 7−2+1=67−2+1=6. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is 11.

If there are no changes, then the length of changed subsegment is 00. Changing an operation means replacing it with some operation (possibly the same); Vasya can't insert new operations into the sequence or remove them.

Help Vasya! Tell him the minimum length of subsegment that he needs to change so that the robot will go from (0,0)(0,0) to (x,y)(x,y), or tell him that it's impossible.

Input

The first line contains one integer number n (1≤n≤2⋅105)n (1≤n≤2⋅105) — the number of operations.

The second line contains the sequence of operations — a string of nn characters. Each character is either U, D, L or R.

The third line contains two integers x,y (−109≤x,y≤109)x,y (−109≤x,y≤109) — the coordinates of the cell where the robot should end its path.

Output

Print one integer — the minimum possible length of subsegment that can be changed so the resulting sequence of operations moves the robot from (0,0)(0,0) to (x,y)(x,y). If this change is impossible, print −1−1.

Examples

input

Copy

5
RURUU
-2 3

output

Copy

input

Copy

4
RULR
1 1

output

Copy

input

Copy

3
UUU
100 100

output

Copy

-1

Note

In the first example the sequence can be changed to LULUU. So the length of the changed subsegment is 3−1+1=33−1+1=3.

In the second example the given sequence already leads the robot to (x,y)(x,y), so the length of the changed subsegment is 00.

In the third example the robot can't end his path in the cell (x,y)(x,y).

这道题今日最佳，出的好，自己做的也不错，虽然最后也没A，但就差一个二分了。

题意：给你一个操作字符串，包含四个操作，修改字符串最短长度的区间能到从（0，0）到（x，y）。

分析：

这题最大的简便：x和y的累加量很好计算

1、明确一点，操作的先后顺序是不影响结果。

2、选定一个修改区间长度，区间里操作可以任意修改，因为题意要求最短区间长度，不是修改操作数量

3、我们一开始可以想到区间长度从len从0到n开始暴力枚举，我们可以先把长度为len的区间扣下来，计算剩下的累计值，这里需要一个前缀和的思想，假设区间长度为len，起点为i，终点为i+len-1，需要减去的就是t=a[i+len-1]-a[i-1],剩下的为t2=a[n]-t即可，然后t2与剩余的步数比较，如果满足t2==step，正好，但是，如果step<=t2,需要满足(len-step)%2==0，因为存在LR，转移的来回

4.然后二分是我没想到的，我以为这是一个递增的肯定从中间遍历，但是正因为它是递增的，所以才正好用二分。就差这一步啊。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
const int M=200005;
int n;
int x[M],y[M];
int ex,ey;
int cal(int len)
{
    for(int i=1;i+len<=n;i++)
    {
        int j=i+len;
        int t1=x[j]-x[i-1];
        int t2=y[j]-y[i-1];
        int tx=x[n]-t1;
        int ty=y[n]-t2;
        int step;
        //cout<<len<<" "<<i<<" "<<step<<endl;
        step=abs(tx-ex)+abs(ty-ey);
        if(len+1>=step&&(len+1-step)%2==0)
        {
            return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
      if(s[i]=='U')
        y[i+1]=1;
      else if(s[i]=='D')
        y[i+1]=-1;
      else if(s[i]=='R')
        x[i+1]=1;
      else if(s[i]=='L')
        x[i+1]=-1;
    }


    scanf("%d%d",&ex,&ey);
    int m=abs(ex)+abs(ey);
    if(n<m)
    {
        printf("-1");
        return 0;
    }


    for(int i=2;i<=n;i++)
    {
      y[i]=y[i]+y[i-1];
      x[i]=x[i]+x[i-1];
    }
    if(y[n]==ey&&x[n]==ex)
    {
        printf("0");
        return 0;
    }
    int ans=-1;
    int l=0,r=n-1;
    while(l<=r)
    {
       int mid=(l+r)/2;
       if(cal(mid))
       {
           ans=mid+1;
           r=mid-1;
       }
       else
       {
           l=mid+1;
       }
    }
    printf("%d",ans);
    return 0;
}