【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d762
【解題想法】
- next_permutation：枚舉5個數字的所有排列。
- dfs( )：搜索所有運算子 (+/-/*) 的可能計算結果。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[5];
bool dfs(int idx, int sum){
if (idx == 4) return sum == 23;
if (dfs(idx+1, sum + a[idx+1])) return true;
else if (dfs(idx+1, sum - a[idx+1])) return true;
else if (dfs(idx+1, sum * a[idx+1])) return true;
else return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4]) {
if (a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0 && a[4] == 0) break;
sort(a, a+5);
bool flag = false;
if (dfs(0, a[0])) {
cout << "Possible\n";
continue;
}
else {
while (next_permutation(a, a+5)){
if (dfs(0, a[0])) {
flag = true;
break;
}
}
}
if (flag) cout << "Possible\n";
else cout << "Impossible\n";
}
return 0;
}
Python code (credit: Amy Chou)
- import itertools
- 利用 itertools.permutations() 把五個數字的所有可能排列找出來，在針對每一種數字排列，利用函式 dfs( ) 檢查是否有任一種運算子的組合可以計算得到數字 23。
- Line-21: 利用 set( ) 排除重複的數字排列，可能加快速度。
import itertools
def dfs(idx, total):
if idx==4:
return total == 23
if dfs(idx+1, total + lst[idx+1]):
return True
elif dfs(idx+1, total - lst[idx+1]):
return True
elif dfs(idx+1, total * lst[idx+1]):
return True
else:
return False
while True:
a = list(map(int, input().split()))
if a[0]==0 and a[1]==0 and a[2]==0 and a[3]==0 and a[4]==0:
break
a.sort()
A = set(list(itertools.permutations(a, 5)))
flag = False
for lst in A:
if dfs(0, lst[0]):
flag = True
break
if flag:
print("Possible")
else:
print("Impossible")