uva 10344 - 23 Out of 5

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

---

Thomas Strohmann

DFS +backtracking

#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int data[5];
bool used[5];
bool DFS(int ind,int num,int len,int left){
    if(DBG)printf("dfs: ind num %d %d\n",ind,num);
    int b;
    if(len==5)return num==23;
    if(num-23>left){if(DBG)printf("len num left %d %d %d\n",len,num,left);return 0;}
    used[ind]=1;
    rep(i,5){
        if(!used[i]){
            b=left-data[i];
            if(DFS(i,num+data[i],len+1,b))return 1;
            if(DFS(i,num-data[i],len+1,b))return 1;
            if(DFS(i,num*data[i],len+1,b))return 1;
        }
    }
    used[ind]=0;
    return 0;
}
void ans(){
    int tot=0;
    rep(i,5)tot+=data[i];
    memset(used,0,sizeof(used));
    rep(i,5)if(DFS(i,data[i],1,tot-data[i])){printf("Possible\n");return;}
    printf("Impossible\n");
}
int main(){
    int a,i;
    while(scanf("%d%d%d%d%d",&data[0],&data[1],&data[2],&data[3],&data[4])==5){
        for(i=0;i<5;i++)if(data[i]>0)break;
        if(i==5)break;
        ans();
    }
}