codeforces 1073C. Vasya and Robot

56 阅读 0 评论 37 点赞

我是靠谱客的博主现代紫菜，最近开发中收集的这篇文章主要介绍codeforces 1073C. Vasya and Robot，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell (0,0)

. Robot can perform the following four kinds of operations:

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

Vasya also has got a sequence of n operations. Vasya wants to modify this sequence so after performing it the robot will end up in (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+1, where maxID is the maximum index of a changed operation, and minID is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices 2, 5 and 7 are changed, so the length of changed subsegment is 7−2+1=6. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is 1.If there are no changes, then the length of changed subsegment is 0.
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)
to (x,y), or tell him that it’s impossible.

Input

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

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

The third line contains two integers 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) to (x,y). If this change is impossible, print −1

Examples

Input

5
RURUU
-2 3

Output

Input

4
RULR
1 1

Output

Input

3
UUU
100 100

Output

-1

Note

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

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

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

给定一个字符串，字符串中每一元素表示在平面直角坐标系的一个移动，现在求一个最小连续区间，要求这个只在这个区间改动，就可使机器人从原点移动到指定位置。
首先考虑在什么情况下，无论如何改动这个字符串都不能到达指定位置

字符串长度小于从原点到指定位置的距离
字符串长度与从原点到指定位置的奇偶性不同
如给定长度为0，到达位置为(1,0)。这样一定不会到达指定位置，同理，对字符串和原点到指定位置同时加上一个偶数，仍然无法到达；同样，对于长度为1，到达位置为(2,0)时，也一定无法到达。由此可推知，若奇偶性不同，则一定无法到达指定位置

在除去这两种情况下，剩余的情况都一定有答案。鉴于其可能解时连续的整数，因此，可以用二分枚举所有可能，进而找出最小的连续区间长度。
应注意，当根据给定字符串移动就能到达指定位置，即最小区间为0时，应排除在二分枚举的情况之外。
当枚举长度为 x 时，考虑在 string 中所有长度为 x 的子串，是否存在一个子串可行。若存在，尝试缩短子串长度；若不存在，延长子串长度。

判断子串是否可行的方法：
设全集为给定字符串，沿着子串的补集移动，记这样移动到的点为 pos 。求 pos 到指定位置的距离，记为 d ，记子串的长度为 len。满足如下两种情况，则子串可行

d < len
d%2==len%2

详细说明见上

其次，考虑二分结束时，程序的输出，对于标记 inf ,sup 有两种可能

inf == sup
此时输出inf 或 sup 均可
inf+1 == sup
此时考虑如果进行下一次循环，
若fessible(mid) 为 true,sup=mid && mid==inf ,输出inf 或 sup均可
若fessible(mid) 为 false，说明最小区间长度为 inf 时不可行，故应输出sup

综上所述，应输出 sup

#include <iostream>
#include <climits>
#include <algorithm>
#include <utility>
#include <string>
#include <map>
#define rep(intdex,star,finish) for(int index=star;index<finish;index++)
#define drep(index,finish,star) for(int index=finish;index>=star;index--)
#define Pair pair<int,int>
#define Make(first,second) make_pair(first,second)
#define re return
using namespace std;
int len;
string step;
Pair aim;
//first X
second Y
inline int abs(int x);
inline int getDis(Pair &a,Pair &b);
inline bool check(int len,Pair &pos,Pair &aim);
inline void shift(Pair &pos,char direction,int addOrcancel);
bool fessible(int n);
int main(){
ios::sync_with_stdio(false);
cin>>len;
cin>>step;
cin>>aim.first>>aim.second;
Pair ini=Make(0,0);
if(!check(len,ini,aim)){
cout<<"-1"<<endl;
re 0;
}
for(int i=0;i<len;i++)
shift(ini,step[i],1);
if(ini.first==aim.first && ini.second==aim.second){
cout<<"0"<<endl;
re 0;
}
int inf=0,sup=len;
while(inf+1<sup){
int mid=inf+(sup-inf)/2;
if(fessible(mid))
sup=mid;
else
inf=mid;
}
cout<<sup<<endl;
re 0;
}
inline int abs(int x){
if(x<0)
re -x;
re x;
}
inline int getDis(Pair &a,Pair &b){
re abs(a.first-b.first)+abs(a.second-b.second);
}
inline bool check(int len,Pair &pos,Pair &aim){
int d=getDis(pos,aim);
if(len<d || d%2!=len%2)
re false;
re true;
}
void shift(Pair &pos,char direction,int addOrcancel){
switch(direction){
case 'U':
pos.second+=addOrcancel;
break;
case 'D':
pos.second-=addOrcancel;
break;
case 'L':
pos.first-=addOrcancel;
break;
case 'R':
pos.first+=addOrcancel;
break;
}
}
bool fessible(int n){
Pair pos=Make(0,0);
for(int i=n;i<len;i++)
shift(pos,step[i],1);
if(check(n,pos,aim))
re true;
int left=0,right=n;
while(right<len){
shift(pos,step[left],1);
shift(pos,step[right],-1);
if(check(n,pos,aim))
re true;
left++;
right++;
}
re false;
}