C - 4-adjacent Time limit : 2sec / Memory limit : 256MB
Score : 400 points
Problem Statement 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≤105 ai is an integer. 1≤ai≤109 Input Input is given from Standard Input in the following format:
N a1 a2 … aN Output If Snuke can achieve his objective, print Yes; otherwise, print No.
Sample Input 1 3 1 10 100 Sample Output 1 Yes One solution is (1,100,10).
Sample Input 2 4 1 2 3 4 Sample Output 2 No It is impossible to permute a so that the condition is satisfied.
Sample Input 3 3 1 4 1 Sample Output 3 Yes The condition is already satisfied initially.
Sample Input 4 2 1 1 Sample Output 4 No Sample Input 5 6 2 7 1 8 2 8 Sample Output 5 Yes
题目大意：相邻数乘积是4的倍数 **解题思路：**1*4=4，2*2=4，判断个数即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<set> using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; const int MAXN=1e5+5; int a[MAXN]; int main() { int n; while(scanf("%d",&n)!=EOF) { bool flag=false; int four=0,one=0,two=0; for(int i=1;i<=n;++i) { scanf("%d",&a[i]); { if(a[i]%4==0) four++; else if(a[i]%2==0) two++; else one++; } } if(one>four+1||(one==four+1&&two!=0)) printf("No\n"); else printf("Yes\n"); } return 0; }