//
问题 G: 4-adjacent
时间限制: 1.000 Sec  内存限制: 128 MB
 
题目描述
We have a sequence of length N, a=(a1,a2,…,aN). Each ai is a positive integer.
Snuke's objective is to permute the element in a so that the following condition is satisfied:
For each 1≤i≤N−1, the product of ai and ai+1 is a multiple of 4.
Determine whether Snuke can achieve his objective.

Constraints
2≤N≤10e5
ai is an integer.
1≤ai≤10e9
输入
Input is given from Standard Input in the following format:
N
a1 a2 … aN
输出
If Snuke can achieve his objective, print Yes; otherwise, print No.
样例输入 Copy
3
1 10 100
样例输出 Copy
Yes
提示
One solution is (1,100,10).

//
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,a,cnt_1,cnt_2,cnt_4;
    while( ~scanf("%d",&n) )
    {
        cnt_1=cnt_2=cnt_4=0;        // 初始化
        while( n-- )
        {
            scanf("%d",&a);
            if( a%4==0 )        cnt_4++;
            else if( a%2==0 )   cnt_2++;
            else                cnt_1++;
        }
        if( cnt_4+1<cnt_1 || ( cnt_4+1==cnt_1 && cnt_2 ) )  printf("No\n");
        else                                                printf("Yes\n");
    }
    return 0;
}

//
find:
01 思维题 相邻两项的乘积为 4 的倍数 即存在因子 1*4=4 2*2=4 
02 找到特殊数据 ( 不止一种 )
    
    01: 1 4 1 4 1 恰好 cnt_4+1 == cnt_1 时 (Yes) —— cnt_4+1 < cnt_1 (No)
    02: 1 2 2 4 1 易知 因子 2 只能挨着 因子 4     —— cnt_4+1 == cnt_1 && cnt_2 != 0 (No)

    补集思想 列举完反例 剩下的都是正确的