URAL 2011. Long Statement （數論）

 

2011. Long Statement

Time limit: 0.5 second
Memory limit: 64 MB
Nikita, a schoolboy, is currently taking part in one of programming contests.He is really upset because all the problem statements are so long and unclear. So he took the statement of the first problem and cut itinto pieces in such a way that each piece contained exactly one letter. After that, he threw away all pieces with letter other than“a”, “b” or “c”. Now he has only n pieces and wants to compilefrom them his own statement that should be shorter and clearer than the original one. The new statement should be a single word compiled from all n letters placed in some order. Nikita wondered if he can compile at least six different words of length n from the letters. If this is not true,he will be ruined and will start solving other problems.Help Nikita to answer this monumental question!

Input

The first line contains an integer n that is the number of pieces with letters (1 ≤ n ≤ 100).The second line describes these pieces as n integers from 1 to 3.1 represents a piece with letter “a”, 2 represents a piece with letter “b”,3 represents a piece with letter “c”.

Output

If Nikita can compile at least six different words of length n, output “Yes”. Otherwise output “No”.

Sample

input output

6
1 2 2 3 3 3

Yes

Problem Author: Alexey Kungurtsev
Problem Source: Ural Regional School Programming Contest 2013

 

 

 

 

解析：坑爹的計數題。。。開始本以為必須用階乘搞，最後發現，100！太大，搞不起。不過，我們可以換種思路，找找規律。

分情況討論滿足的情況：

n = 3：必須是1，2，3同時出現才滿足。

n = 4：三個數字同時出現或者存在兩個數量超過2的數字出現。

n = 5：同n = 4.

n > 5：至少有兩個不同的數字出現。

其余的情況均不滿足。

 

 

 

AC代碼：

 

#include 
using namespace std;

int main(){
    #ifdef sxk
        freopen("in.txt", "r", stdin);
    #endif // sxk

    int n, a, b, x;
    while(~scanf("%d", &n)){
        a = b = 0;
        for(int i=0; i= 2) + (b >= 2) + (n - a - b >= 2) >= 2))
            flag = 1;
        else if(n > 5 && (a > 0) + (b > 0) + (n - a - b > 0) >= 2) flag = 1;
        puts(flag ? "Yes" : "No");
    }
    return 0;
}