csu 1600: Twenty-four point

1600: Twenty-four point

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 490 Solved: 78
[Submit][Status][Web Board]

Description

Given four numbers, can you get twenty-four through the addition, subtraction, multiplication, and division? Each number can be used only once.

Input

The input consists of multiple test cases. Each test case contains 4 integers A, B, C, D in a single line (1 <= A, B, C, D <= 13).

Output

For each case, print the “Yes” or “No”. If twenty-four point can be get, print “Yes”, otherwise, print “No”.

Sample Input

2 2 3 9
1 1 1 1 
5 5 5 1

Sample Output

Yes
No
Yes

HINT

For the first sample, (2/3+2)*9=24.

Source

思路：

dfs，把数组当参数，4个数先选2个算一下，然后变成三个数，传入当下一层，避免了麻烦的选数

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stack>
 6 #include <cctype>
 7 #include <vector>
 8 #include <cmath>
 9 #include <map>
10 #include <queue>
11 
12 #define ll long long
13 #define eps 1e-8
14 
15 using namespace std;
16 
17 double a[5];
18 
19 int dfs(double p[],int len)
20 {
21     if(len==1){
22         if(fabs(p[0]-24)<eps){
23             return 1;
24         }
25         else{
26             return 0;
27         }
28     }
29     double f[5];
30     int cou;
31     int i,j,k;
32     for(i = 0;i <len-1;i++){
33         for(j=i+1;j<len;j++){
34             cou=0;
35             for(k=0;k<len;k++){
36                 if(k!=i && k!=j){
37                     f[cou]=p[k];cou++;
38                 }
39             }
40             f[cou]=p[i]+p[j];
41             if(dfs(f,cou+1)) return 1;
42             f[cou]=p[i]-p[j];
43             if(dfs(f,cou+1)) return 1;
44             f[cou]=p[j]-p[i];
45             if(dfs(f,cou+1)) return 1;
46             f[cou]=p[i]*p[j];
47             if(dfs(f,cou+1)) return 1;
48             if(p[j]!=0){
49                 f[cou]=p[i]/p[j];
50                 if(dfs(f,cou+1)) return 1;
51             }
52             if(p[i]!=0){
53                 f[cou]=p[j]/p[i];
54                 if(dfs(f,cou+1)) return 1;
55             }
56         }
57     }
58     return 0;
59 }
60 
61 int main()
62 {
63     //freopen("in.txt","r",stdin);
64     //scanf("%d",&T);
65     //for(int ccnt=1;ccnt<=T;ccnt++){
66     while(scanf("%lf%lf%lf%lf",&a[0],&a[1],&a[2],&a[3])!=EOF){
67         if(dfs(a,4) == 1){
68             printf("Yes
");
69         }
70         else{
71             printf("No
");
72         }
73     }
74     return 0;
75 }