UVA 10344 23 out of 5

UVA_10344

由于计算顺序已经给定了，那么便只需要依次枚举符号和符号后面ai的值即可，其中符号是可以重复使用的，但每个ai只能使用一次。

当递归到所有ai都已使用时就检查计算结果是否为23即可。

#include<stdio.h>
#include<string.h>
int a[10],vis[10];
int dfs(int cur,int tot)
{
    int i,j,t;
    if(cur==5)
    {
        if(tot==23)
            return 1;
        else
            return 0;
    }
    for(i=0;i<3;i++)
        for(j=0;j<5;j++)
            if(!vis[j])
            {
                vis[j]=1;
                if(i==0)
                    t=tot+a[j];
                else if(i==1)
                    t=tot-a[j];
                else
                    t=tot*a[j];
                if(dfs(cur+1,t))
                    return 1;
                vis[j]=0;
            }
    return 0;
}
int main()
{
    int i,j,k,ok;
    while(1)
    {
        for(i=0;i<5;i++)
            scanf("%d",&a[i]);
        if(a[0]==0)
            break;
        memset(vis,0,sizeof(vis));
        ok=0;
        for(i=0;i<5;i++)
        {
            vis[i]=1;
            if(dfs(1,a[i]))
            {
                ok=1;
                break;
            }
            vis[i]=0;
        }
        if(ok)
            printf("Possible\n");
        else
            printf("Impossible\n");
    }
    return 0;    
}