Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1285
Your task is to write a program that can decide whether you can find an arithmetic expression consisting of five given numbers ai (1 ≤ i ≤ 5) that will yield the value 23. For this problem we will only consider arithmetic expressions of the following from: (((aπ(1) o1 aπ(2)) o2 aπ(3)) o3 aπ(4)) o4 aπ(5) where π : {1, 2, 3, 4, 5} → {1, 2, 3, 4, 5} is a bijective function and oi ∈ {+, −, ∗}(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. Input file will have no more than 25 lines. 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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
bool dfs(vector<int>& nums, int cur, vector < bool>& used, bool first){
bool allUsed = true;
for(int i=0;i < 5;i++){
if(used[i]) continue;
allUsed = false;
used[i] = true;
if(dfs(nums,cur+nums[i],used,false)) return true;
else if(!first && dfs(nums,cur-nums[i],used,false)) return true;
else if(!first && dfs(nums,cur*nums[i],used,false)) return true;
used[i] = false;
}
if(allUsed) return cur == 23;
else return false;
}
int main()
{
int a,b,c,d,e;
while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e),a||b||c||d||e){
vector<int> nums = {a,b,c,d,e};
vector < bool> used(5);
cout << (dfs(nums,0,used,true) ? "Possible" : "Impossible") << endl;
}
}Input
1 2 3 4 5
2 3 5 7 11
0 0 0 0 0
Output
Possible
Possible
Demonstration
UVA Online Judge solution - 10344-23 out of 5 - UVA Online Judge solution in C,C++,java