elephents

 avatar
duyvan
plain_text
2 years ago
1.0 kB
8
Indexable
//elephent, voi con uong ruou

#include<iostream>
#define endl '\n'
using namespace std;

int N, K, M;
int ans;
int ele[18];

bool check()
{
	for(int i = 0; i <= N - K; ++i)
	{
		int tmp = 0;
		for(int j = i; j < i + K; ++j)
			tmp = max(tmp, ele[j]);
		int cnt = 0;
		for(int j = i; j < i + K; ++j)
            		if(ele[j] == tmp)
                		cnt++;
		if(cnt >= M)	return false;
	}
	return true;
}

void input()
{
	cin >> N >> K >> M;
	for(int i = 0; i < N; ++i)
		cin >> ele[i];
}

void backtrack(int x, int change)
{
	if(x == N)
	{
		if(check())
			ans = min(ans, change);
		return;
	}
	if(change > ans)	return;
	ele[x]++;
	backtrack(x + 1, change + 1);
	ele[x]--;
	backtrack(x + 1, change);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	for(int tc = 1; tc <= T; ++tc)
	{
		ans = 1000000;
		input();
		if(check())
		{
			ans = 0;
			goto result;
		}
		backtrack(0,0);
result:;
		if(ans == 1000000)	ans = -1;
		cout << "#" << tc << " " << ans << endl;
	}
	return  0;
}
Editor is loading...
Leave a Comment