首页 > 代码库 > UVA - 10344
UVA - 10344
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 }
UVA - 10344
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。