任意门：

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) 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 $\mathrm{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: $\mathrm{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 $\mathrm{00.\; Changing\; an\; operation\; means\; replacing\; it\; with\; some\; operation\; (possibly\; the\; same);\; Vasya\; can\text{'}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\text{'}s\; impossible.$

Input

The first line contains one integer number $\mathrm{n (1\le n\le 2\cdot 105)n (1\le n\le 2\cdot 105) —\; the\; number\; of\; operations.}$

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

The third line contains two integers $\mathrm{x,y (-109\le x,y\le 109)x,y (-109\le x,y\le 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

3

input

Copy

4 RULR 1 1

output

Copy

0

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 $\mathrm{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).$

 

题意概括：

输入N个操作，询问修操作是否能到达终点，如果能到达终点输出“修改的区间”；

修改区间的定义：修改的最大坐标操作的坐标 - 修改的最小坐标操作的坐标

【规定起点为 （0，0），输入终点（ x, y )；】

操作（上下左右）：

• • 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)$

解题思路：二分 || 尺取

预处理路径前缀和（压缩路径）sum_x [ ]，sum_y[ ] ;则sum_x[ N ] , sum_y[ N ] 为实际的终点；

输入的终点为 (ex, ey)，假设能修改若干个操作到达输入的终点，那么：

某一段 [ st, ed ] 所走的影响为:

　　　　　　　　　　　　　 X轴方向：xx = ex - ( sum_x[ N ] - sum_x[ ed -1 ] + sum_x[ st - 1 ] )

　　　　　　　　　　　　 　Y轴方向：yy = ey - ( sum_y[ N ] - sum_y[ ed - 1 ] + sum_y[ st - 1 ] )

二分

二分修改区间长度 len ，尺取判断在该长度是否满足修改条件；

 

①操作所走最大范围不得超过 len ，因为每次操作只是上下左右移动一步

②判断能否完成假设的影响  len - abs(xx) - abs(yy))%2 ?= 0;

　abs（xx）表示的是 x 方向 到达终点 ex 的差值

　abs（yy）表示的是 y 方向 到达终点 ey 的差值

　假如 len > abs(xx)+abs(yy) 说明这段区间有操作是多余的，但是只要剩下的操作数是偶数就可以两两抵消。

 

尺取：

直接定义一个头指针一个尾指针，暴力一遍，条件判断是要头指针加还是尾指针加，记录最小修改区间。

 

AC code:

1 #include
      
        2 using namespace std; 3 const int N=1e6+6; 4 int x[N],y[N]; 5 int sx,sy,n; 6 char s[N]; 7 bool check(int m) 8 { 9     for(int i=1;i<=n-m+1;i++)10     {11         int tx=x[n]-x[i+m-1]+x[i-1];  //当前原来选项造成的横坐标影响12         int ty=y[n]-y[i+m-1]+y[i-1];  //当前原来选项造成的纵坐标影响13         int ex=sx-tx, ey=sy-ty;        //消除当前影响14         printf("%d %d m: %d\n",ex,ey,m);15         if(m>=(abs(ex)+abs(ey)) && (m-abs(ex)-abs(ey))%2==0) //可以构造16             return 1;17     }18     return 0;19 }20 int main()21 {22     //string s;23     while(~scanf("%d",&n))24     {25         scanf("%s",s+1);26         x[0]=y[0]=0;27         for(int i=1;i<=n;i++)28         {29             x[i]=x[i-1];y[i]=y[i-1];  //累积前面步数的结果30 31             if(s[i]=='L') x[i]-=1;    //当前步数造成的影响32             else if(s[i]=='R') x[i]+=1;33             else if(s[i]=='D') y[i]-=1;34             else y[i]+=1;35         }36        // printf("%d %d\n",x[n],y[n]);37         scanf("%d %d",&sx,&sy);       //终点38        // printf("HH");39         int l=0,r=n,ans=-1;40         while(l<=r)                   //二分答案41         {42             printf("l:%d r:%d\n", l, r);43             int mid=(l+r)>>1;44             if(check(mid)) ans=mid,r=mid-1;45             else l=mid+1;46         }47         printf("%d\n",ans);48     }49 }