Flip and Shift boj1149

Flip and ShiftSubmit: 96   Accepted:66Time Limit: 1000MS  Memory Limit: 65336KDescription
This puzzle consists of a random sequence of m black disks and n white disks on an oval-shaped track, with a turnstile capable of flipping (i.e., reversing) three consecutive disks. In Figure 1, there are 8 black disks and 10 white disks on the track. You may spin the turnstile to flip the three disks in it or shift one position clockwise for each of the disks on the track (Figure 1).



The goal of this puzzle is to gather the disks of the same color in adjacent positions using flips and shifts. (Figure 2)





Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each of the next T lines gives a test case. A test case consists of an integer, representing the sum of m and n, and a sequence of m+n 0s and 1s, representing an initial sequence. A 0 denotes a white disk and a 1 denotes a black disk. The sum of m and n is at least 10 and does not exceed 30. There is a space between numbers.


Output
The output should print either "YES" or "NO" for each test case, one per line.

Sample Input

2
18 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1
14 1 1 0 0 1 1 1 0 0 1 1 0 1 0


Sample Output



Hint
YES
NO


Source
Taejon 2001

解题思路：
题目要求把所有颜色相同的球移到一起。
在环状的情况下，分两种情况来考虑，只考虑如何将1交换在一起(注意步长为2)：
1.球数目为奇数：这时，不管1在那个位置，总是可以以2为步长到达任何一个位置，所以总是能成功
2.球数目为偶数：这时，处于奇数位置的1，在2的步长要求下，只能到达奇数位置，处理偶数位置的1，只能到达偶数位置，所以只要满足奇数位置的1和偶数位置的1的数目相差小于1，总能将所有1移到一起。
其他情况则不能

#include <iostream>
#include <stdlib.h>
using namespace std;

int main(int argc, char *argv[])
{
    int T, N, i, odd_cnt, mate_cnt, color;
    cin >> T;
    while (T--)
    {
        cin >> N;
        odd_cnt = mate_cnt = 0;
        for (i=1 ; i<=N ; i++)
        {
            cin >> color;
            if (1 == color)
            {
                if (0 == i % 2)
                    mate_cnt++;
                else
                    odd_cnt++;
            }
        }
        if (1 == N % 2)
        {
            cout << "YES" << endl;
        }
        else
        {
            if (abs(mate_cnt - odd_cnt) <= 1)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
}