Codeforces 7/16 Div.2

A. Vika and Her Friends

题目

Vika and her friends went shopping in a mall, which can be represented as a rectangular grid of rooms with sides of length nn and mm. Each room has coordinates (a,b)(a,b), where 1≤a≤n,1≤b≤m1≤a≤n,1≤b≤m. Thus we call a hall with coordinates (c,d)(c,d) a neighbouring for it if |a−c|+|b−d|=1|a−c|+|b−d|=1.

Tired of empty fashion talks, Vika decided to sneak away unnoticed. But since she hasn't had a chance to visit one of the shops yet, she doesn't want to leave the mall. After a while, her friends noticed Vika's disappearance and started looking for her.

Currently, Vika is in a room with coordinates (x,y)(x,y), and her kk friends are in rooms with coordinates (x1,y1)(x1,y1), (x2,y2)(x2,y2), ... ,(xk,yk),(xk,yk), respectively. The coordinates can coincide. Note that all the girls must move to the neighbouring rooms.

Every minute, first Vika moves to one of the adjacent to the side rooms of her choice, and then each friend (seeing Vika's choice) also chooses one of the adjacent rooms to move to.

If at the end of the minute (that is, after all the girls have moved on to the neighbouring rooms) at least one friend is in the same room as Vika, she is caught and all the other friends are called.

Tell us, can Vika run away from her annoying friends forever, or will she have to continue listening to empty fashion talks after some time?

Input

Each test consists of multiple test cases. The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers nn, mm, kk (1≤n,m,k≤1001≤n,m,k≤100) — the sizes of the mall and the number of Vika's friends.

The second line of each test case contains a pair of integers xx and yy (1≤x≤n1≤x≤n, 1≤y≤m1≤y≤m) — the coordinates of the room where Vika is.

Each of the next kk lines of each test case contains a pair of integers xixi and yiyi (1≤xi≤n1≤xi≤n, 1≤yi≤m1≤yi≤m) — the coordinates of the room where the ii-th friend is.

Output

For each test case, output "YES" if Vika can run away from her friends forever, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Example

input

1. 6
2. 2 2 1
3. 1 1
4. 1 2
5. 2 2 2
6. 1 1
7. 2 2
8. 2 2
9. 1 2 1
10. 1 1
11. 1 2
12. 5 5 4
13. 3 3
14. 1 1
15. 1 5
16. 5 1
17. 5 5
18. 2 2 2
19. 1 1
20. 2 1
21. 1 2
22. 3 4 1
23. 1 2
24. 3 3

output

1. YES
2. NO
3. YES
4. NO
5. YES
6. YES

Note

In the first test case, the friend will never catch up with Vika, because Vika can always move to the room diagonally opposite to the one where the friend is.

In the second test case, no matter where Vika goes, each of her friends can catch her after the first move.

In the third test case, Vika and her friend will always be in different halls.

解析

在规定范围的矩阵内，只要朋友能抓住vika输出NO，否则输出YES，这里我们只需要判断vika与所有朋友的曼哈顿距离是否有偶数，有偶数就可以抓住

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
  int n,m,k,x,y,a,b,flag=0;
  cin>>n>>m>>k;
  cin>>x>>y;
  for(int i=0;i<k;i++)
  {
    cin>>a>>b;
    if((abs(x-a)+abs(y-b))%2==0)
    flag=1;
  }
  if(flag)
  cout<<"NO"<<endl;
  else
  cout<<"YES"<<endl; 
  }
  return 0;
}

B. Vika and the Bridge

题目

In the summer, Vika likes to visit her country house. There is everything for relaxation: comfortable swings, bicycles, and a river.

There is a wooden bridge over the river, consisting of nn planks. It is quite old and unattractive, so Vika decided to paint it. And in the shed, they just found cans of paint of kk colors.

After painting each plank in one of kk colors, Vika was about to go swinging to take a break from work. However, she realized that the house was on the other side of the river, and the paint had not yet completely dried, so she could not walk on the bridge yet.

In order not to spoil the appearance of the bridge, Vika decided that she would still walk on it, but only stepping on planks of the same color. Otherwise, a small layer of paint on her sole will spoil the plank of another color. Vika also has a little paint left, but it will only be enough to repaint one plank of the bridge.

Now Vika is standing on the ground in front of the first plank. To walk across the bridge, she will choose some planks of the same color (after repainting), which have numbers 1≤i1<i2<…<im≤n1≤i1<i2<…<im≤n (planks are numbered from 11 from left to right). Then Vika will have to cross i1−1,i2−i1−1,i3−i2−1,…,im−im−1−1,n−imi1−1,i2−i1−1,i3−i2−1,…,im−im−1−1,n−im planks as a result of each of m+1m+1 steps.

Since Vika is afraid of falling, she does not want to take too long steps. Help her and tell her the minimum possible maximum number of planks she will have to cross in one step, if she can repaint one (or zero) plank a different color while crossing the bridge.

Input

Each test consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of planks in the bridge and the number of different colors of paint.

The second line of each test case contains nn integers c1,c2,c3,…,cnc1,c2,c3,…,cn (1≤ci≤k1≤ci≤k) — the colors in which Vika painted the planks of the bridge.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output a single integer — the minimum possible maximum number of planks that Vika will have to step over in one step.

Example

input

1. 5
2. 5 2
3. 1 1 2 1 1
4. 7 3
5. 1 2 3 3 3 2 1
6. 6 6
7. 1 2 3 4 5 6
8. 8 4
9. 1 2 3 4 2 3 1 4
10. 3 1
11. 1 1 1

output

1. 0
2. 1
3. 2
4. 2
5. 0

Note

In the first test case, Vika can repaint the plank in the middle in color 11 and walk across the bridge without stepping over any planks.

In the second test case, Vika can repaint the plank in the middle in color 22 and walk across the bridge, stepping over only one plank each time.

In the third test case, Vika can repaint the penultimate plank in color 22 and walk across the bridge, stepping only on planks with numbers 22 and 55. Then Vika will have to step over 11, 22 and 11 plank each time she steps, so the answer is 22.

In the fourth test case, Vika can simply walk across the bridge without repainting it, stepping over two planks each time, walking on planks of color 33.

In the fifth test case, Vika can simply walk across the bridge without repainting it, without stepping over any planks.

解析

给出了桥上所有板子的颜色，可以用一个二维数组来维护每个颜色的最大和第二大间隔距离，最后开一个循环将最后边界距离加上判断，然后遍历一遍，寻找所有颜色块中每个颜色最大间隔的最小值

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define p 201010
int a[p],z[p][2],o[p];
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
  memset(z,0,sizeof(z));
  memset(o,0,sizeof(o));
  int k,n;
  cin>>k>>n;
  for(int i=1;i<=k;i++)
  cin>>a[i];
  for(int i=1;i<=k;i++)
  {
    int m=i-o[a[i]];
    if(m>z[a[i]][0])
    {
    z[a[i]][1]=z[a[i]][0];
    z[a[i]][0]=m;
    }
    else if(m>z[a[i]][1])
    z[a[i]][1]=m;
    o[a[i]]=i;
  }
  int max1=0,minn=201100;
  for(int i=1;i<=k;i++)
  {
    int m=k+1-o[a[i]];
    if(m>z[a[i]][0])
    {
    z[a[i]][1]=z[a[i]][0];
    z[a[i]][0]=m;
    }
    else if(m>z[a[i]][1])
    z[a[i]][1]=m;
    max1=max((z[a[i]][0]+1)/2,z[a[i]][1]);//最大距离中间可变一次颜色，与第二大距离比较
    minn=min(minn,max1);
     }
  cout<<minn-1<<endl;
  }
  return 0;
}