题解：UVA10344 23 out of 5

__hanzhenhong__ · 2025-02-10 10:28:24 · 题解

题目大意

给定五个 1 到 50 之间的正整数，判断能否通过特定形式的算术表达式使其结果为 23。算数表达式如题所示，输出以一行五个 0 结束，且输入文件不超过 25 行。

解题思路

利用全排列生成五个数的所有排列组合，可以通过调用库函数 next_permutation，对于每种排列，枚举所有可能的运算符组合。按照给定的表达式计算规则，依次计算每种排列和运算符组合下的表达式结果，判断是否等于 23。

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[5];
bool vis[5];
bool ans;
void dfs(int x,int cc)
{
    if(x==5)
    {
        if(cc==23)
        {
            ans=true;
        }
        return;
    }
    for(int y=0;y<5;y++)
    {
        if(!vis[y])
        {
            vis[y]=true;
            dfs(x+1,cc+a[y]);
            dfs(x+1,cc-a[y]);
            dfs(x+1,cc*a[y]);
            vis[y]=false;
        }
    }
}

int main()
{
    while(1)
    {
        for(int x=0;x<5;x++)
        {
            cin>>a[x];
        }
        if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0)
        {
            break;
        }
        ans=false;
        memset(vis,false,sizeof(vis));
        for(int x=0;x<5;x++)
        {
            vis[x]=true;
            dfs(1,a[x]);
            vis[x]=false;
            if(ans)
            {
                break;
            }
        }
        if(ans)
        {
            cout<<"Possible"<<endl;
        }
        else
        {
            cout<<"Impossible"<<endl;
        }
    }
    return 0;
}

完结撒花！