首页 > 代码库 > 暴力枚举 + 24点 --- hnu : Cracking the Safe
暴力枚举 + 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. |
| Input |
On the first line one positive number: the number of test cases, at most 100. After that per test case: |
| Output |
Per test case: |
| Sample Input |
44 7 8 81 1 2 41 1 1 11 3 4 6 |
| Sample Output |
YESNONOYES |
| 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 longusing 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 longusing 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;}