UVa 10344 23 out of 5：全排列枚举&回溯

UVa 10344 23 out of 5：全排列枚举&回溯2014-10-02 synapse7

10344 - 23 out of 5

Time limit: 3.000 seconds

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

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45364.htm

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

水题。

完整代码：

/*0.279s*/#include<cstdio>#include<algorithm>using namespace std;int a[5];bool flag;void dfs（int cur, int ans）{if （cur == 5）{if （ans == 23） flag = true;return;}if （！flag） dfs（cur + 1, ans + a[cur]）;if （！flag） dfs（cur + 1, ans - a[cur]）;if （！flag） dfs（cur + 1, ans * a[cur]）;}int main（）{while （scanf（"%d%d%d%d%d", &a[0], &a[1], &a[2], &a[3], &a[4]）, a[0]）{flag = false;sort（a, a + 5）;do{dfs（1, a[0]）;if （flag） break;}while （next_permutation（a, a + 5））;puts（flag ？ "Possible" : "Impossible"）;}return 0;}