In a two dimensional array of integers of size 2 \times n2×n, is it possible to rearrange integers so that the sum of two adjacent elements (which are adjacent in a common row or a common column) is never divisible by three?
Input
The input has several test cases and the first line contains an integer t (1 \le t \le 200)t(1≤t≤200) which is the number of test cases.
In each case, the first line contains an integers n (1 \le n \le 10000)n(1≤n≤10000) indicating the number of columns in the array. The second line contains the elements of the array in the first row separated by single spaces. The third line contains the elements of the array in the second row separated by single spaces. The elements will be positive integers less then 10000001000000.
Output
For each test case, output “YES” in a single line if any valid rearrangement exists, or “NO” if not.
样例输入
6 3 3 6 9 1 4 7 3 3 6 9 1 3 8 5 1 2 3 4 5 6 7 8 9 10 10 1 1 1 1 1 1 1 1 1 1 2 3 2 3 2 3 2 3 2 3 2 3 1 2 3 2 3 1 1 2
样例输出
YES NO YES YES YES NO
1 | 1 | 1 | 0 | 2 | 2 | 2 | 2 |
1 | 1 | 1 | 1 | 0 | 2 | 2 | 2 |
不过还有些细节要处理。
#include<bits/stdc++.h>
using namespace std;
int a[4];
int main()
{
int T;cin>>T;
while(T--)
{
int n;
scanf("%d",&n);
memset(a,0,sizeof a);
for(int i=1;i<=2*n;i++)
{
int x;
scanf("%d",&x);
a[x%3]++;
}
if(a[0]>n)puts("NO");//当0的个数大于n，必定有2个0相邻
else
{
if(a[0]<=1&&a[1]&&a[2])puts("NO");//当0的个数小于等于1时，必定有1个1和1个2相邻
else if(a[1]==0||a[2]==0)puts("YES");
else if(a[0]>=2&&a[1]&&a[2])
{
if(a[0]==2&&a[1]%2==0&&a[2]%2==0)puts("NO");//当只有2个0且1和2的个数均为偶数时，必定有1个1和1个2相邻
else puts("YES");
}
}
}
return 0;
}