hdu 1427 速算24点【暴力枚举】
速算24点
time limit: 2000/1000 ms (java/others) memory limit: 65536/32768 k (java/others)
total submission(s): 6946 accepted submission(s): 1828
problem description
速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括a(1),2,3,4,5,6,7,8,9,10,j(11),q(12),k(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断是否有解。我们另外规定，整个计算过程中都不能出现小数。
input
每组输入数据占一行，给定四张牌。
output
每一组输入数据对应一行输出。如果有解则输出"yes"，无解则输出"no"。
sample input
a 2 3 6 3 3 8 8
sample output
yes no
author
ll
source
acm暑期集训队练习赛（三）
因规模不大，直接暴力枚举了所有情况。
ac代码如下：
//1427
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int sum(int a,int b,int c,int d) //枚举不加括号所有情况
{
char str[4]={'+','-','*','/'};
int i,j,k,l,ans=0,n,m,p;
for(i=0;i<2;i++)
{
ans=0;
if(i==1)
ans-=a;
else
ans+=a;
n=ans;
for(j=0;j<4;j++)
{ans=n;
if(j==0)
ans+=b;
else if(j==1)
ans-=b;
else if(j==2)
ans*=b;
else
if(ans%b==0&&b!=0)
ans/=b;
else
continue;
m=ans;
for(k=0;k<4;k++)
{ans=m;
if(k==0)
ans+=c;
else if(k==1)
ans-=c;
else if(k==2)
ans*=c;
else
if(ans%c==0&&c!=0)
ans/=c;
else
continue;
p=ans;
for(l=0;l<4;l++)
{ans=p;
if(l==0)
ans+=d;
else if(l==1)
ans-=d;
else if(l==2)
ans*=d;
else
if(ans%d==0&&d!=0)
ans/=d;
else
continue;
if(ans==24)
{
//printf("%c%d%c%d%c%d%c%d=%d\n",str[i],a,str[j],b,str[k],c,str[l],d,ans); //输出算式
return 1;
}
}
}
}
}
return 0;
}
int kh(int a,int b,int c,int d) //枚举加括号的所有情况
{
char str[4]={'+','-','*','/'};
int ans,bns,sum,i,j,k,l;
for(i=0;i<4;i++)
{
ans=0;
if(i==0)
ans=a+b;
else if(i==1)
ans=a-b;
else if(i==2)
ans=a*b;
else
if(i==3&&a%b==0)
ans=a/b;
else
continue;
for(j=0;j<4;j++)
{
bns=0;
if(j==0)
bns=c+d;
else if(j==1)
bns=c-d;
else if(j==2)
bns=c*d;
else
if(j==3&&c%d==0)
bns=c/d;
else
continue;
for(k=0;k<4;k++)
{
sum=0;
if(k==0)
sum=ans+bns;
else if(k==1)
sum=ans-bns;
else if(k==2)
sum=ans*bns;
else
if(k==3&&bns!=0&&ans%bns==0)
sum=ans/bns;
else
continue;
if(sum==24)
{
//printf("(%d%c%d)%c(%d%c%d)=%d\n",a,str[i],b,str[k],c,str[j],d,sum); //输出算式
return 1;
}
}
}
}
return 0;
}
int main()
{
int a,b,c,d,i,aa[4];
char temp[4][3];
char aaa[14][3]={"0","a","2","3","4","5","6","7","8","9","10","j","q","k"};
while(scanf("%s %s %s %s",temp[0],temp[1],temp[2],temp[3])!=eof)
{
int f=0;
for(int i=0;i<4;i++)//把牌转换成对应的数字
{
for(int j=1;j<=13;j++)
if(strcmp(temp[i],aaa[j])==0)
{
aa[i]=j;
break;
}
}
for(a=0;a<4;a++) //全排
{
if(f==1) break;
for(b=0;b<4;b++)
{
if(f==1) break;
if(b==a) continue;
for(c=0;c<4;c++)
{
if(f==1) break;
if(c==a||c==b) continue;
d=6-a-b-c;
if(sum(aa[a],aa[b],aa[c],aa[d])||kh(aa[a],aa[b],aa[c],aa[d]))
{
printf("yes\n");
f=1;
break;
}
}
}
}
if(f==0)
printf("no\n");
}
return 0;
}
---------------------
作者：yongtaozheng
来源：csdn
原文：https://blog.csdn.net/twinkle_sone/article/details/95041176
版权声明：本文为博主原创文章，转载请附上博文链接！