首页 > 代码库 > UVa 10344 - 23 out of 5
UVa 10344 - 23 out of 5
题目：给你五个数字，在他们中间加上‘+‘，‘-‘，‘*‘，构成结果23，问能否成功。
分析：搜索，24点类似物。
首先，求出五个数的全排列；
然后，按顺序枚举三种运算，计算结果，判断即可。
说明：注意优先级，左边的高。
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int data[5],save[5],used[5],buf[5];
int P[120][5];
int p_count;
//生成全排列
void makep(int d)
{
if (d == 5) {
for (int i = 0 ; i < 5 ; ++ i)
P[p_count][i] = save[i];
p_count ++;
return;
}
for (int i = 0 ; i < 5 ; ++ i)
if (!used[i]) {
used[i] = 1;
save[d] = i;
makep( d+1 );
used[i] = 0;
}
}
//计算24点类似物
bool flag;
void dfs(int d)
{
if (flag) return;
if (!d) {
if (buf[0] == 23) flag = 1;
return;
}
//储存状态
int temp[5],a,b;
for (int i = 0 ; i <= d ; ++ i)
temp[i] = buf[i];
a = buf[0]; b = buf[1];
for (int i = 1 ; i < d ; ++ i)
buf[i] = buf[i+1];
buf[0] = a+b; dfs(d-1);
buf[0] = a-b; dfs(d-1);
buf[0] = a*b; dfs(d-1);
//回溯
for (int i = 0 ; i <= d ; ++ i)
buf[i] = temp[i];
}
int main()
{
p_count = 0;
makep(0);
while (~scanf("")) {
for (int i = 0 ; i < 5 ; ++ i)
scanf("%d",&data[i]);
if (data[0] == 0) break;
flag = 0;
for (int i = 0 ; i < 120 ; ++ i) {
for (int j = 0 ; j < 5 ; ++ j)
buf[j] = data[P[i][j]];
dfs(4);
if (flag) break;
}
if (flag) printf("Possible\n");
else printf("Impossible\n");
}
return 0;
}
测试数据：
输入：
42 8 2 32 37 10 43 21 46 5 44 2 27 30 29 10 20 20 2 36 28 3 34 42 2 22 6 6 5 37 34 3 31 18 12 25 46 28 13 2 12 4 19 2 50 1 12 2 1 49 48 48 42 2 11 1 2 43 26 33 0 0 0 0 0输出：
Possible Possible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible Impossible
UVa 10344 - 23 out of 5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。