UVA 23 out of 5

題目如下：

Problem I

23 Out of 5

Input: standard input

Output: standardoutput

Time Limit: 1 second

Memory Limit: 32 MB

Your task is to writea program that can decide whether you can find an arithmetic expression consistingof five given numbers

(1<=i<=5) that will yieldthe value 23.

For this problem we will only consider arithmetic expressions of the followingfrom:

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-Tupelsof positive Integers, each between 1 and 50.

Input is terminated by a line containing five zero's. This line should not beprocessed.

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      

也是直接回溯就可以了，不過要注意π是個雙射函數（bijective function)，是以要一一對應，不能重複使用，采用一個vis數組标記即可。

AC的代碼如下：

#include 
   
    

using namespace std;
int a[5];
int ok=0;
int vis[5];
void dfs(int cur,int result)
{
    if(ok)
        return;
    if(cur==4)
    {
        if(result==23)
            ok=1;
        return;
    }

    for(int i=0; i<5; i++)
        if(!vis[i])
        {
            vis[i]=1;
            dfs(cur+1,result+a[i]);
            dfs(cur+1,result-a[i]);
            dfs(cur+1,result*a[i]);
            vis[i]=0;
        }

}
int main()
{
    while(1)
    {
        for(int i=0; i<5; i++)
            cin>>a[i];
        if(a[0]==0)
            break;
        ok=0;
        for(int i=0; i<5; i++)
        {
            memset(vis,0,sizeof vis);
            vis[i]=1;
            dfs(0,a[i]);
            if(ok)
                break;
        }
        if(ok)
            cout<<"Possible"<