SW acadeny 1265 달란트2

//공백을 포함한 문자열을 입력받아 각 단어로 분리하여 문자열 배열에 저장한 후 입력순서의 반대 순서로 출력하는 프로그램을 작성하시오.
//문자열의 길이는 100자 이하이다.

#include <iostream>

using namespace std;


int max_sum;

void group(int gCount, int left, int* group_box, int gsize) {
	if (left == 0) {
		//for (int i = 1; i <= gsize; i++)printf("%d, ", group_box[i]);
		//putchar('\n');
		int sum = 1;
		for (int i = 1; i <= gsize; i++) sum *= group_box[i];
		if (sum > max_sum) max_sum = sum;
	}
	else if (gCount == 1) {
		group_box[gCount] += left;
		//for (int i = 1; i <= gsize; i++)printf("%d, ", group_box[i]);
		//putchar('\n');
		int sum = 1;
		for (int i = 1; i <= gsize; i++) sum *= group_box[i];
		if (sum > max_sum) max_sum = sum;
		group_box[gCount] -= left;
	}
	else {
		//nHr = nHr-1 + n-1Hr
		group_box[gCount]++;
		group(gCount, left - 1, group_box, gsize);
		group_box[gCount]--;
		group(gCount - 1, left, group_box, gsize);
		
		/* Brute force
		for (int i = 1; i <= left; i++) {
			if (i >= left) break;
			group(left - i, gCount + 1, sum*i, group_box, gsize);
		}
		*/
	}
}

int main() {
	//freopen("Text.txt", "r", stdin);

	int TC;
	cin >> TC;
	long long res[20]{ 0, };
	for (int t = 0; t < TC; t++) {
		int N, P;//개수, 묶음수
		cin >> N >> P;
		long long* group_box;
		group_box = new long long[P+1];
		
		long long least_talent = N / P;
		//Group_box의 첫번째 상자는 group_box[1]임에 주의한다.
		group_box[0] = 0;
		//빈상자는 있을 수 없다.
		for (int i = 1; i <=P; i++) group_box[i] = least_talent;
		long long max_sum = 1;
		//nHr에서 r을 효과적으로 줄인다.
		N -= (P * least_talent);
		for (int i = 1; i <= N; i++) {
			group_box[i]++;
		}
		//for (int i = 1; i <= P; i++)printf("%d, ", group_box[i]);
		//putchar('\n');
		for (int i = 1; i <= P; i++) {
			max_sum *= group_box[i];
		}
		//group(P,N, group_box, P);
		res[t] = max_sum;
		//printf("#%d result Found = %lld\n", t + 1, max_sum); 
		delete[] group_box;
	}
	for (int t = 0; t < TC; t++) {
		printf("#%d %lld\n", t + 1, res[t]);
	}



	return 0;
}