NC214664. Chickenandrabbitinthesamecage

描述

输入描述

There are a total of T (T<=10) groups of data
The first line of each group of data is n(n<=40), m(m<=2^31-1), k(k<=4),they represent n starfishes, m starfish tentacles and k starfish species
The second line is the number of tentacles of each kind of starfishes,the i-th number represents the number of tentacles of the i-th kind of starfishes（在第i种海星中，一只海星的角数）

输出描述

For each set of data output the most valuable solution, if there is no solution, output -1
The last line outputs the number of successfully solved groups

示例1

输入:

9
31 113 2
2 4
31 68 2
2 4
34 104 2
2 4
38 94 2
2 4
36 121 2
2 4
32 117 2
2 4
33 122 2
2 4
34 100 2
2 4
35 57 2
2 4

输出:

-1
28 3
16 18
29 9
-1
-1
5 28
18 16
-1
5

示例2

输入:

2
36 82 4
2 3 4 5
35 58 4
2 3 4 5

输出:

32 1 0 3
-1
1

原站题解

#include<iostream>
using namespace std;
int a[5],a0[5];
int k;
int m,n,cnt,f;
void dfs(int step,int n){
	if(f){
		return;
	}
	if(step==k){
		int sum=0;
		a[k]=n*a0[step];
		for(int i=1;i<=k;i++){
			sum+=a[i];
		}
		if(sum==m){
			for(int i=1;i<=k;i++){
				cout<<a[i]/a0[i]<<" ";
			}
			cout<<endl;
			cnt++;
			f=1;
		}
		return;
	}
	for(int i=n;i>=0;i--){
		a[step]=i*a0[step];
		dfs(step+1,n-i);
		if(f){
			return;
		}
	}
}
int main(void){
	
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		for(int i=1;i<=k;i++){
			cin>>a0[i];
		}
		f=0;
		dfs(1,n);
		if(!f){
			cout<<-1<<endl;
		}
	} 
	cout<<cnt<<endl;
	return 0;
}