Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
12
Indexable
Never
#include <iostream>

using namespace std;
#define maxn 20
int n, m, k, ans;
int map[maxn];

void imports(){
	cin >> n >> k >> m;
	for(int i = 0; i < n; i++){
		cin >> map[i];
	}
}

void reset(){
	for(int i = 0; i < maxn; i++){
		map[i] = 0;
	}
}

bool check(){
	for(int i = 0; i <= n - k; i++){
		int cnt_max = 0;
		int max = 0;
		for(int j = i; j < i + k; j++){
			if(map[j] > max)
				max = map[j];
		}
		for(int j = i; j < i + k; j ++){
			if(map[j] == max)
				cnt_max++;
		}
		if(cnt_max >= m)
			return false;
	}
	return true;
}

void backtrack(int index, int cnt){
	if(cnt > ans)
		return;
	if(index == n){
		if(check()){
			if(cnt < ans)
				ans = cnt;
		}
		return;
	}
	for(int i = 0; i < 2; i++){
		if(i == 0){
			backtrack(index +1 , cnt);
		}
		else{
			map[index] += 1;
			backtrack(index +1 , cnt + 1);
			map[index] -= 1;
		}
	}
}

void exports(int tc){
	ans = n;
	backtrack(0, 0);
	if(ans == n)
		ans = -1;
	cout << "#" << tc <<" " << ans << endl;
}

int main(){
	freopen("input.txt","r",stdin);
	int t;
	cin >> t;
	for(int tc = 1; tc <= t; tc++){
		reset();
		imports();
		exports(tc);
	}
	return 0;
}