2021年杭电多校1008
————南昌理工学院acm集训队
链接：https://ac.nowcoder.com/acm/contest/11254/F
来源：牛客网
24dian is a famous game. You are given a set of n cards, each card contains an integer between 1 to 13. You can put the cards in arbitrary order, add + or - or * or / between any two cards, and add as many parentheses as you want. Your goal is to make the expression valid and its value equals m.
However, there’re cases when valid solutions exist, but all the valid solutions involve fractions, that is, non-integers, in the process of calculation. For example, if you want to use (1, 5, 5, 5) to get 24, the only solution is 5*(1-(1/5)), where 1/5 is a fraction.
Given the number of cards n and the result m you want to get, find all the possible set of cards that has a valid solution but any solution involves fraction in the calculation.
输入描述:
The first line contains two integers n,m(1\leq n\leq 4,1\leq m\leq 109)n,m(1≤n≤4,1≤m≤109 ) , representing the number of cards and the result you want to get.
输出描述:
First line contains an integer k, denoting the number of possible sets.
In next k lines, each line contains n non-decreasing numbers, represent a possible set. You should print the sets in lexicographical order.
示例1
输入
4 24
输出
16
1 3 4 6
1 4 5 6
1 5 5 5
1 6 6 8
1 8 12 12
2 2 11 11
2 2 13 13
2 3 5 12
2 4 10 10
2 5 5 10
2 7 7 10
3 3 7 7
3 3 8 8
4 4 7 7
5 5 7 11
5 7 7 11
示例2
输入
1 114514
输出
0
题目翻译：问题描述
24 dian是一种著名的游戏。你有一组n张牌，每张牌包含1到13之间的整数。您可以将卡片按任意顺序排列，在任意两张卡片之间添加+或-或或/，并添加尽可能多的括号。您的目标是使表达式有效并使其值等于m。
然而，也有存在有效解的情况，但在计算过程中，所有的有效解都涉及到分数，也就是非整数。例如，如果你想用(1,5,5,5)得到24，唯一的解是5(1-(1/5))，其中1/5是一个分数。
给定牌的数量n和你想要得到的结果m，找出所有可能的有有效解的牌集，但任何解都涉及到计算中的分数。
输入描述:
第一行包含两个整数n,m(1<= n <=4,1<=m<=109)n,m(1≤n≤4,1≤m≤109)，表示牌的数量和你想要得到的结果。
输出描述:
第一行包含一个整数k，表示可能的集合的数量。
在接下来的k行中，每一行包含n个非递减数，代表一个可能的集合。你应该按字典的顺序打印这些集。
示例1
输入
4 24
输出
16
1 3 4 6
1 4 5 6
1 5 5 5
1 6 6 8
1 8 12 12
2 2 11 11
2 2 13 13
2 3 5 12
2 4 10 10
2 5 5 10
2 7 7 10
3 3 7 7
3 3 8 8
4 4 7 7
5 5 7 11
5 7 7 11
示例2
输入
1 114514
输出
0
题目解法：暴力枚举，每次操作的哪两个数。
dfs(a,b):表示集合a能否凑出b
if(size(a)==1)return a[0]=b;
else
for x,y in a
if(dfs(a-x-y+(x*y或者x/y 或x-y或x+y),b)return 1;
return 0;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<double> vk[5];
int turn=0,flag=0;
int n,m;
double save[6];
const double eps=1e-6;
bool judge(double x){
if(x<=0)return false;
if(fabs(x-(int)x)<0.000001||fabs(x-(int)x)>1-0.000001)return false;
return true;
}
bool check(double x){
x=x-(int)x;
return x>eps && x<1-eps;
}
void dfs(int p,int fl){
if(flag==2)return ;
if(p==4){
if(fabs(save[1]-m)<=0.000001){
if(fl){
flag=1;
}
else flag=2;
}
return ;
}
double temp[5];
for(int i=1;i<=4;i++)temp[i]=save[i];
for(int y=1;y<=4-p+1;y++){
for(int x=1;x<=4-p+1;x++){
if(y!=x){
for(int choice = 1;choice<=4;choice++){
int w=fl;
if(choice==1)save[y]+=save[x];
else if(choice==2)save[y]-=save[x];
else if(choice==3)save[y]*=save[x];
else {
save[y]/=save[x];
if(judge(save[y]))w=1;
}
save[x]=1e9;
sort(save+1,save+1+(4-p+1));
save[4-p+1]=0;
dfs(p+1,w);
memcpy(save,temp,sizeof(save));
}
}
}
}
}
int main() {
scanf("%d %d",&n,&m);
if(n!=4){
printf("0\n");
return 0;
}
for(int a=1;a<=13;a++){
for(int b=a;b<=13;b++){
for(int c=b;c<=13;c++){
for(int d=c;d<=13;d++){
flag=0;
save[1]=a;save[2]=b;save[3]=c;save[4]=d;
dfs(1,0);
if(flag==1){
turn++;
vk[1].push_back(save[1]);
vk[2].push_back(save[2]);
vk[3].push_back(save[3]);
vk[4].push_back(save[4]);
}
}
}
}
}
printf("%d\n",turn);
for(int i=0;i<turn;i++){
printf("%d %d %d %d\n",(int)vk[1][i],(int)vk[2][i],(int)vk[3][i],(int)vk[4][i]);
}
return 0;
}