ACM-ICPC 2017 Asia Nanning J. Rearrangement

In a two dimensional array of integers of size 2 × 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 ≤ t ≤ 200) which is the number of test cases.

In each case, the first line contains an integers 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 1000000.

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

题目大意

给你一个2 x n 的数，让你重新排列，让这些数与其相邻的数（左右相邻与上相邻）的和不能被三整除。若能排列出这种组合，就输出“YES”，否则输出“NO”。

思路

题目比较简单，但是想了很久，思考了一下还是写一下。

首先对三取模，这样就只剩下了0，1，2

0和0肯定不能相邻，1和2也不能相邻

我们看0的数量

1.如果0的数量大于n，那么不管怎么排列，总有相邻的0，此种情况下肯定不满足题目要求

2如果没有0，这时候，如果一和二都存在的话，怎么排列也都不满足要求

3.如果只有一个0，这种情况和第二种情况是一样的

4.如果有两个0，这两个0肯定不能相邻排列，也不能分的太开，分的太开的话，就会变成第三种情况。那么，这两个0就只能斜着排列，把左右两边分开，一边全都放1，一边全都放2，在这种情况下， 1和2的数量必须都是奇数，否则达不成这种排列方式

5.如果0的数量大于等于三小于等于n，我们把0按照波浪形排序，这时候，不论1和2的数量是奇数还是偶数都无所谓

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cctype>
#include <stack>
#include <map>
#include <cstring>
#include <sstream>
#include <set>
#include <list>
#include <fstream>
#include <iomanip>
#include <assert.h>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>
#define op                            \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);

const int INF = 0x3f3f3f3f;
const int maxn = (10000 + 5);
const int mod = (998244353);

int main()
{
    int t,n,a[2][maxn];
    int zero,one,two;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        zero=0,one=0,two=0;
        for(int i=0;i<2;i++)
            for(int j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
                a[i][j]=a[i][j]%3;
                if(a[i][j]==0) zero++;
                else if(a[i][j]==1) one++;
                else two++;
            }
        if(zero>n) printf("NO\n");
        else if(zero<=1&&one&&two) printf("NO\n");
        else if(zero==2&&one%2==0) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}