boj 11

Description

We are familiar with the game called “Counting 24”. Now it comes a problem that we want to know whether we can figure out the exact answer with given 4 numbers only using +,-,*,/ and (,).

Input

There are several cases in a test. Each case contains only 5 integers, a1, a2, a3, a4 and required answer. All integers are positive and no more than 100.

Output

If it is possible to figure out the required answer, output “Possible”; otherwise output “Impossible”.

Sample Input

5 5 1 5 24

Sample Output

Impossible

乱七八糟。。。。

代码：

#include<iostream>
using namespace std;
bool flag;
int arr[4],x[4],res;
int calTwo(int x,int y,int oper)
{if(x<y)swap(x,y);if(oper==0)return x+y;if(oper==1)return x-y;if(oper==2)return x*y;if(oper==3){if(y!=0&&x%y==0)return x/y;else if(x!=0&&y%x==0)return y/x;}return 200000001;
}
void calTree(int x,int y,int z)
{for(int i=0;i<=3;i++){int tmp = calTwo(x,y,i);if(tmp!=200000001&&flag==false){for(int j=0;j<=3;j++){if(calTwo(tmp,z,j)==res){flag = true;break;}}}}for(int i=0;i<=3;i++){int tmp = calTwo(x,z,i);if(tmp!=200000001&&flag==false){for(int j=0;j<=3;j++){if(calTwo(tmp,y,j)==res){flag = true;break;}}}}for(int i=0;i<=3;i++){int tmp = calTwo(z,y,i);if(tmp!=200000001&&flag==false){for(int j=0;j<=3;j++){if(calTwo(tmp,x,j)==res){flag = true;break;}}}}
}
void search(int cur,int res)
{if(cur==4){for(int i=0;i<=3;i++){int temp = calTwo(x[0],x[1],i);calTree(temp,x[2],x[3]);}if(flag)return ;}for(int i=cur;i<4;i++){x[cur] = arr[i];swap(arr[cur],arr[i]);search(cur+1,res);swap(arr[cur],arr[i]);}return ;
}
int main()
{while(~scanf("%d %d %d %d %d",&arr[0],&arr[1],&arr[2],&arr[3],&res)){flag = false;search(0,res);if(flag) printf("Possible\n");else printf("Impossible\n");}
}