hdu5143 暴力枚舉

hdu5143 暴力枚舉

http://acm.hdu.edu.cn/showproblem.php?pid=5143

Problem Description NPY is learning arithmetic progression in his math class. In mathematics, an arithmetic progression (AP) is a sequence of numbers such that the difference between the consecutive terms is constant.(from wikipedia)
He thinks it's easy to understand,and he found a challenging problem from his talented math teacher:
You're given four integers, a1,a2,a3,a4, which are the numbers of 1,2,3,4 you have.Can you divide these numbers into some Arithmetic Progressions,whose lengths are equal to or greater than 3?(i.e.The number of AP can be one)
Attention: You must use every number exactly once.
Can you solve this problem?
Input The first line contains a integer T — the number of test cases (1≤T≤100000).
The next T lines,each contains 4 integers a1,a2,a3,a4(0≤a1,a2,a3,a4≤109).
Output For each test case,print "Yes"(without quotes) if the numbers can be divided properly,otherwise print "No"(without quotes).
Sample Input

3
1 2 2 1
1 0 0 0
3 0 0 0

Sample Output

Yes
No
Yes
HintIn the first case,the numbers can be divided into {1,2,3} and {2,3,4}.
In the second case,the numbers can't be divided properly.
In the third case,the numbers can be divided into {1,1,1}.

/*
hdu 5143 暴力枚舉
題目大意：
     給定數字1,2,3,4.的個數每個數字能且僅能使用一次，組成多個或一個等差數列（長度大於等於3）問能否成功
解題思路：（杭電官方題解）
     可以發現等差數列只有（123,234,1234和長度>=3的常數列），如果選擇非常數列（123,234,1234）數量大於等於3，
可以變為三個或4個常數列,例如（123,123,123）變為（111,222,333）。所以從0-2枚舉選擇非常數列的數量，再判斷能
否用常數列覆蓋剩下的（如果數字長度正好為0或≤3就可以）。
*/
#include 
#include 
#include 
using namespace std;
bool ok(int a[5])
{
    if((a[0]>=3||a[0]==0)&&(a[1]>=3||a[1]==0)&&(a[2]>=3||a[2]==0)&&(a[3]>=3||a[3]==0))
        return true;
    return false;
}
int a[10],b[10];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<4;i++)
        {
            scanf("%d",&a[i]);
        }
        int flag=0;
        if(ok(a))
        {
            flag=1;
        }
        else
        {
            for(int i=0;i<=2;i++)
            {
                for(int j=0;j<=2;j++)
                {
                    for(int k=0;k<=2;k++)
                    {
                        b[0]=a[0]-i-j;
                        b[1]=a[1]-i-j-k;
                        b[2]=a[2]-i-j-k;
                        b[3]=a[3]-i-k;
                        if(ok(b))
                            flag=true;
                    }
                }
            }
        }
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}