voisol

 avatar
quoc14
c_cpp
5 months ago
1.1 kB
1
Indexable
caidat
#include <iostream>

using namespace std;

int m, n, k;
int r[100];
int oo = 9999999;
int ans;
int ok;

bool check() {
	for (int i = 0; i < n - k + 1; i++) {
		int maxx = -1;
		for (int j = i; j < i + k; j++) {
			if (r[j] > maxx) maxx = r[j];
		}
		int dem = 0;
		for (int j = i; j < i + k; j++) {
			if (r[j] == maxx) dem++;
		}
		if (dem >= m) return true;
	}
	return false;
}

void backtrack(int voi, int count) {
	if (count > ans) return;
	if (voi == n) {
		if (check() == false) {
			if (count < ans) ans = count;
			ok = 1;
		}
		return;
	}
	
	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			backtrack(voi + 1, count);
		}
		else {
			r[voi]++;
			backtrack(voi + 1, count + 1);
			r[voi]--;
		}
	}
}

void solve(int testcase) {
	
	cin >> n >> k >> m;
	for (int i = 0; i < n; i++) {
		cin >> r[i];
	}
	ans = oo;
	ok = 0;
	backtrack(0, 0);
	
	if (ok == 0) ans = -1;
	cout << "#" << testcase << " " << ans << endl;
	
}

int main() {
	freopen("Text.txt", "r", stdin);
	int t; cin >> t;
	
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}
Leave a Comment