[模拟]ACM-T4-24点

题面题目描述输入格式输出格式 模拟思路运算优先级数字全排列运算符排列全枚举 完整代码(判断能否组成24)拓展延伸代码(输出算式)

题面

题目描述

您作为游戏者将得到$4$个$1-13$（在扑克牌里用$A$代替$1$，$J$代替$11$，$Q$代替$12$，$K$代替$13$）之间的自然数作为操作数，而您的任务是对这$4$个操作数进行适当的算术运算，判断运算结果是否等于$24$。能输出$1$，不能输出$0$。您可以使用的运算只有：$+$，$-$，$\ast$，$/$，您还可以使用$($，$)$来改变运算顺序。 注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，$(2\ast 2)/4$是合法的，$2\ast (2/4)$是不合法的）。下面我们给出一个游戏的具体例子：若给出的$4$个操作数是：$1$、$2$、$3$、$7$，则一种可能的解答是$1+2+3\ast 7=24$。

输入格式

四个牌面值。牌面值与牌面值之间用一个空格隔开。

输出格式

输出$0$或$1$。

模拟思路

运算优先级

在$4$个数中，运算优先级有以下几种可能 （$⨀$表示任意一个四则运算符） 序号运算1(($a⨀b$)$⨀c$)$⨀d$2($a⨀$($b⨀c$))$⨀d$3$a⨀$(($b⨀c$)$⨀d$)4($a⨀b$)$⨀$($c⨀d$)5$a⨀$($b⨀$($c⨀d$))

数字全排列

在$4$个数中,全排列有以下几种可能 （$a$,$b$,$c$,$d$代表这$4$个数） 序号全排列1$abcd$2$abdc$3$acbd$4$acdb$5$adbc$$\dots \dots$$\dots \dots$24$dcba$

运算符排列

在$4$个数中($3$个运算符),排列有以下几种可能 序号全排列1$+++$2$++-$3$++\ast$4$++/$5$+-+$$\dots \dots$$\dots \dots$256$///$

全枚举

$O(5\ast 24\ast 256)=O(30720)$

完整代码(判断能否组成24)

#include<bits/stdc++.h> #define forr(i) for(int i=1;i<=4;i++) using namespace std; char a_c[2],b_c[2],c_c[2],d_c[2]; int a,b,c,d,a1,b1,c1,d1; int num[4]={1,2,3,4}; bool ans; int js(int x,int y,int n) { if(n==1)return x+y; if(n==2)return x-y; if(n==3)return x*y; if(n==4&&y!=0&&x%y==0)return x/y; return -10000000; } int main() { cin>>a_c>>b_c>>c_c>>d_c; if(a_c[0]=='1'&&a_c[1]=='0')a=10;else if(a_c[0]=='A')a=1;else if(a_c[0]=='J')a=11;else if(a_c[0]=='Q')a=12;else if(a_c[0]=='K')a=13;else a=a_c[0]-'0'; if(b_c[0]=='1'&&b_c[1]=='0')b=10;else if(b_c[0]=='A')b=1;else if(b_c[0]=='J')b=11;else if(b_c[0]=='Q')b=12;else if(b_c[0]=='K')b=13;else b=b_c[0]-'0'; if(c_c[0]=='1'&&c_c[1]=='0')c=10;else if(c_c[0]=='A')c=1;else if(c_c[0]=='J')c=11;else if(c_c[0]=='Q')c=12;else if(c_c[0]=='K')c=13;else c=c_c[0]-'0'; if(d_c[0]=='1'&&d_c[1]=='0')d=10;else if(d_c[0]=='A')d=1;else if(d_c[0]=='J')d=11;else if(d_c[0]=='Q')d=12;else if(d_c[0]=='K')d=13;else d=d_c[0]-'0'; do { if(num[0]==1)a1=a;if(num[0]==2)a1=b;if(num[0]==3)a1=c;if(num[0]==4)a1=d; if(num[1]==1)b1=a;if(num[1]==2)b1=b;if(num[1]==3)b1=c;if(num[1]==4)b1=d; if(num[2]==1)c1=a;if(num[2]==2)c1=b;if(num[2]==3)c1=c;if(num[2]==4)c1=d; if(num[3]==1)d1=a;if(num[3]==2)d1=b;if(num[3]==3)d1=c;if(num[3]==4)d1=d; forr(i) { forr(j) { forr(k) { if(js(js(js(a1,b1,i),c1,j),d1,k)==24) { printf("1\n"); return 0; } if(js(js(a1,js(b1,c1,i),j),d1,k)==24) { printf("1\n"); return 0; } if(js(a1,js(js(b1,c1,i),d1,j),k)==24) { printf("1\n"); return 0; } if(js(js(a1,b1,i),js(c1,d1,j),k)==24) { printf("1\n"); return 0; } if(js(a1,js(b1,js(c1,d1,i),j),k)==24) { printf("1\n"); return 0; } } } } } while(next_permutation(num,num+4)); printf("0\n"); return 0; }

拓展延伸代码(输出算式)

并可以求总和为N1代表$+$,2代表$-$,3代表*,$4$代表\ #include<bits/stdc++.h> #define forr(i) for(int i=1;i<=4;i++) using namespace std; char a_c[2],b_c[2],c_c[2],d_c[2]; int a,b,c,d,a1,b1,c1,d1; int num[4]= {1,2,3,4}; bool ans; int N; int js(int x,int y,int n) { if(n==1)return x+y; if(n==2)return x-y; if(n==3)return x*y; if(n==4&&y!=0&&x%y==0)return x/y; return -10000000; } int main() { scanf("%d\n",&N); cin>>a_c>>b_c>>c_c>>d_c; if(a_c[0]=='1'&&a_c[1]=='0')a=10;else if(a_c[0]=='A')a=1;else if(a_c[0]=='J')a=11;else if(a_c[0]=='Q')a=12;else if(a_c[0]=='K')a=13;else a=a_c[0]-'0'; if(b_c[0]=='1'&&b_c[1]=='0')b=10;else if(b_c[0]=='A')b=1;else if(b_c[0]=='J')b=11;else if(b_c[0]=='Q')b=12;else if(b_c[0]=='K')b=13;else b=b_c[0]-'0'; if(c_c[0]=='1'&&c_c[1]=='0')c=10;else if(c_c[0]=='A')c=1;else if(c_c[0]=='J')c=11;else if(c_c[0]=='Q')c=12;else if(c_c[0]=='K')c=13;else c=c_c[0]-'0'; if(d_c[0]=='1'&&d_c[1]=='0')d=10;else if(d_c[0]=='A')d=1;else if(d_c[0]=='J')d=11;else if(d_c[0]=='Q')d=12;else if(d_c[0]=='K')d=13;else d=d_c[0]-'0'; do { if(num[0]==1)a1=a;if(num[0]==2)a1=b;if(num[0]==3)a1=c;if(num[0]==4)a1=d; if(num[1]==1)b1=a;if(num[1]==2)b1=b;if(num[1]==3)b1=c;if(num[1]==4)b1=d; if(num[2]==1)c1=a;if(num[2]==2)c1=b;if(num[2]==3)c1=c;if(num[2]==4)c1=d; if(num[3]==1)d1=a;if(num[3]==2)d1=b;if(num[3]==3)d1=c;if(num[3]==4)d1=d; forr(i) { forr(j) { forr(k) { if(js(js(js(a1,b1,i),c1,j),d1,k)==N) { printf("1\n"); printf("((a%cb)%cc)%cd\n",i,j,k); printf("a:%c\nb:%c\nc:%c\nd:%c\n",a1,b1,c1,d1); return 0; } if(js(js(a1,js(b1,c1,i),j),d1,k)==N) { printf("1\n"); printf("(a%c(b%cc))%cd\n",j,i,k); printf("a:%c\nb:%c\nc:%c\nd:%c\n",a1,b1,c1,d1); return 0; } if(js(a1,js(js(b1,c1,i),d1,j),k)==N) { printf("1\n"); printf("a%c((b%cc)%cd)\n",k,i,j); printf("a:%c\nb:%c\nc:%c\nd:%c\n",a1,b1,c1,d1); return 0; } if(js(js(a1,b1,i),js(c1,d1,j),k)==N) { printf("1\n"); printf("(a%cb)%c(c%cd)\n",i,k,j); printf("a:%c\nb:%c\nc:%c\nd:%c\n",a1,b1,c1,d1); return 0; } if(js(a1,js(b1,js(c1,d1,i),j),k)==N) { printf("1\n"); printf("a%c(b%c(c%cd))\n",k,j,i); printf("a:%c\nb:%c\nc:%c\nd:%c\n",a1,b1,c1,d1); return 0; } } } } } while(next_permutation(num,num+4)); printf("0\n"); return 0; }