首页 > 代码库 > UVA - 10344

UVA - 10344

2024-08-04 23:30:46   219人阅读

Problem I

23 Out of 5

Input: standard input

Output: standard output

Time Limit: 1 second

Memory Limit: 32 MB

Your task is to write a program that can decide whether you can find an arithmetic expression consisting of five given numbers (1<=i<=5) that will yield the value 23.
For this problem we will only consider arithmetic expressions of the following from:

 
where : {1,2,3,4,5} -> {1,2,3,4,5} is a bijective function
and  {+,-,*} (1<=i<=4)
Input
The Input consists of 5-Tupels of positive Integers, each between 1 and 50.
Input is terminated by a line containing five zero‘s. This line should not be processed.
Output
For each 5-Tupel print "Possible" (without quotes) if their exists an arithmetic expression (as described above) that yields 23. Otherwise print "Impossible".
Sample Input
1 1 1 1 1
1 2 3 4 5
2 3 5 7 11
0 0 0 0 0
Sample Output
Impossible
Possible
Possible

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 int cal(int a,char c,int b) { 8     if (c == ‘+‘) return a + b; 9     if (c == ‘-‘) return a - b;10     if (c == ‘*‘) return a * b;11 }12 13 int a[5];14 char s[4] = {"+-*"};15 int dfs(int sum ,int cur) {16     if (cur == 5) {17         if (sum == 23) return 1;18         else return 0;19     }20     for (int i = 0;i < 3;i++) {21         if (dfs(cal(sum,s[i],a[cur]),cur + 1)) return 1;22     }23     return 0;24 }25 26 int main () {27     // freopen("1.in","r",stdin);28     while (cin >> a[0]) {29         for (int i = 1;i < 5;i++) {30             cin >> a[i];31         }32         if (a[0] == 0) break;33         int ok = 0;34         sort(a,a + 5);35         do {36             if(dfs(a[0],1)) {37                 cout << "Possible" << endl;38                 ok = 1;39                 break;40             }41         }while (next_permutation(a,a + 5));42         if (ok == 0) cout << "Impossible" << endl;43     }44 }
View Code
 


UVA - 10344






























        

            
                
                  
                
                

                    联系

                    我们