暴力枚举 + 24点 --- hnu : Cracking the Safe

Cracking the Safe

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB

Total submit users: 46, Accepted users: 12

Problem 12886 : No special judgement

Problem description

Secret agent Roger is trying to crack a safe containing evil Syrian chemical weapons. In order to crack the safe, Roger needs to insert a key into the safe. The key consists of four digits. Roger has received a list of possible keys from his informants that he needs to try out. Trying out the whole list will take too long, so Roger needs to find a way to reduce the list.
A valid key satisfies a certain condition, which we call the 24 condition. Four digits that satisfy the 24 condition can be manipulated using addition, subtraction, multiplication, division and parentheses, in such a way, that the end result equals 24.
For example, the key (4; 7; 8; 8) satisfies the 24 condition, because (7-8/8)×4 = 24. The key (1; 1; 2; 4) does not satisfy the 24 condition, nor does (1; 1; 1; 1). These keys cannot possibly be the valid key and do not need to be tried.
Write a program that takes the list of possible keys and outputs for each key whether it satisfies the 24 condition or not.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:
one line with four space-separated integers a; b; c; d (1<=a; b; c; d<=9): a possible key.

Output

Per test case:
one line with either “YES” or “NO”, indicating whether the key satisfies the 24 condition or not.

Sample Input

Sample Output

YES
NO
NO
YES

Problem Source

BAPC preliminary 2013

Mean:

给你4个数，你需要判断这4个数是否能够通过"+"、"-"、"*"、"/"四种得到24。

analyse:

数据这么小，直接暴力枚举。

先枚举四个数的位置，再枚举三个运算符，最后枚举运算顺序。

解法二：递归求解。

Time complexity：4*4*4*4*4*4*4*5=81920，不超过81920次

Source code：

//Memory   Time
// 1143K   27MS
// by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAX 1100
#define LL long long
using namespace std;
bool mark;
double num[5];
double aa[5];
double calc(double a,double b,int flag)
{
    switch(flag)
    {
        case 1:return (a+b);
        case 2:return (a-b);
        case 3:return (a*b);
        case 4:return (a/b);
    }
}
void algebra()
{
    double tmp1,tmp2,tmp3;
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            for(int k=1;k<=4;k++)
            {
                //  运算顺序1
                tmp1=calc(aa[1],aa[2],i);
                tmp2=calc(tmp1,aa[3],j);
                tmp3=calc(tmp2,aa[4],k);
                if(fabs(tmp3-24)<1e-6)
                {
                   mark=1;
                    return ;
                }
                //  运算顺序2
                tmp1=calc(aa[1],aa[2],i);
                tmp2=calc(aa[3],aa[4],k);
                tmp3=calc(tmp1,tmp2,j);
                if(fabs(tmp3-24)<1e-6)
                {
                   mark=1;
                    return ;
                }
                //  运算顺序3
                tmp1=calc(aa[2],aa[3],j);
                tmp2=calc(aa[1],tmp1,i);
                tmp3=calc(tmp2,aa[4],k);
                if(fabs(tmp3-24)<1e-6)
                {
                   mark=1;
                    return ;
                }
                //  运算顺序4
                tmp1=calc(aa[2],aa[3],j);
                tmp2=calc(tmp1,aa[4],k);
                tmp3=calc(tmp2,aa[1],i);
                if(fabs(tmp3-24)<1e-6)
                {
                   mark=1;
                    return ;
                }
                //  运算顺序5
                tmp1=calc(aa[3],aa[4],k);
                tmp2=calc(aa[2],tmp1,j);
                tmp3=calc(aa[1],tmp2,i);
                if(fabs(tmp3-24)<1e-6)
                {
                   mark=1;
                    return ;
                }
            }
        }
    }
}

void arrange()
{
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            if(j==i)continue;
            for(int k=1;k<=4;k++)
            {
                if(k==i||k==j)continue;
                for(int l=1;l<=4;l++)
                {
                    if(l==i||l==j||l==k)continue;
                    aa[1]=num[i],aa[2]=num[j],aa[3]=num[k],aa[4]=num[l];
                    algebra();
                }
            }
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        mark=false;
        for(int i=1;i<=4;i++)
            cin>>num[i];
        arrange();
        if(mark)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

递归：

//Memory   Time
// 724K      0MS
// by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAX 1100
#define LL long long
using namespace std;
double num[4];
bool solve ( int n ) {
    if ( n == 1 ) {
        if ( fabs ( num[0] - 24 ) < 1E-6 )
            return true;
        else
            return false;
    }

    for ( int i = 0; i < n; i++ ) 
    {
        for ( int j = i + 1; j < n; j++ ) 
        {
                    double a, b;
                    a = num[i];
                    b = num[j];
                    num[j] = num[n - 1];
                    
                    num[i] = a + b;
                    if ( solve ( n - 1 ) )
                        return true;
                        
                    num[i] = a - b;
                    if ( solve ( n - 1 ) )
                        return true;

                    num[i] = b - a;
                    if ( solve ( n - 1 ) )
                        return true;

                    num[i] = a * b;
                    if ( solve ( n - 1 ) )
                        return true;
                        
                        
                    if ( b != 0 ) {
                        num[i] = a / b;

                        if ( solve ( n - 1 ) )
                            return true;
                    }
                    if ( a != 0 ) {
                        num[i] = b / a;
                        if ( solve ( n - 1 ) )
                            return true;
                    }
                    num[i] = a;
                    num[j] = b;
        }
    }
    return false;
}
int main() {
    int x;
    int T;
    cin >> T;
    while ( T-- ) {
        for ( int i = 0; i < 4; i++ ) {
            cin >> x;
            num[i] = x;
        }

        if ( solve ( 4 ) ) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}