暴力枚举 + 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[];
double aa[];
double calc(double a,double b,int flag)
{
switch(flag)
{
case :return (a+b);
case :return (a-b);
case :return (a*b);
case :return (a/b);
}
}
void algebra()
{
double tmp1,tmp2,tmp3;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
for(int k=;k<=;k++)
{
// 运算顺序1
tmp1=calc(aa[],aa[],i);
tmp2=calc(tmp1,aa[],j);
tmp3=calc(tmp2,aa[],k);
if(fabs(tmp3-)<1e-6)
{
mark=;
return ;
}
// 运算顺序2
tmp1=calc(aa[],aa[],i);
tmp2=calc(aa[],aa[],k);
tmp3=calc(tmp1,tmp2,j);
if(fabs(tmp3-)<1e-6)
{
mark=;
return ;
}
// 运算顺序3
tmp1=calc(aa[],aa[],j);
tmp2=calc(aa[],tmp1,i);
tmp3=calc(tmp2,aa[],k);
if(fabs(tmp3-)<1e-6)
{
mark=;
return ;
}
// 运算顺序4
tmp1=calc(aa[],aa[],j);
tmp2=calc(tmp1,aa[],k);
tmp3=calc(tmp2,aa[],i);
if(fabs(tmp3-)<1e-6)
{
mark=;
return ;
}
// 运算顺序5
tmp1=calc(aa[],aa[],k);
tmp2=calc(aa[],tmp1,j);
tmp3=calc(aa[],tmp2,i);
if(fabs(tmp3-)<1e-6)
{
mark=;
return ;
}
}
}
}
}

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

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

递归：

//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[];
bool solve ( int n ) {
if ( n == ) {
if ( fabs ( num[] - ) < 1E-6 )
return true;
else
return false;
}

for ( int i = ; i < n; i++ )
{
for ( int j = i + ; j < n; j++ )
{
double a, b;
a = num[i];
b = num[j];
num[j] = num[n - ];

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

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

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

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

if ( b != ) {
num[i] = a / b;

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

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

return ;
}