Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.0 kB
0
Indexable
Never
#include <iostream>
using namespace std;

int s, k, n;
int arr[21][21];
int dd[21];
int sum;
bool flag;
int res[21];
int dem;


void BackTrack(int j) {

	if (j == k + 1 && sum == s) {
		flag = true;
		return;
	}

	if (sum > s)
		return;

	for (int i = 1; i <= n; i++) {
		if (j>=1 && j<=k && dd[j] == 0) {
			if (arr[i][j] >= res[dem - 1]) {

				dd[j] = 1;
				sum += arr[i][j];
				res[dem++] = arr[i][j];

				BackTrack(j + 1);
				if (flag)
					return;

				dem--;
				sum -= arr[i][j];
				dd[j] = 0;

			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cin >> s >> k >> n;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= k; j++) {
				cin >> arr[i][j];
			}
		}

		for (int i = 1; i <= k; i++) {
			dd[i] = 0;
		}

		sum = 0;
		dem = 1;
		flag = false;
		res[0] = -1;
		BackTrack(1);

		cout << "Case #" << tc << endl;

		if (flag) {
			cout << "1" << endl;
		}
		else {
			cout << "-1" << endl;
		}
	}
}