Untitled
plain_text
a month ago
2.7 kB
2
Indexable
Never
50 5 3 2 1 3 1 2 1 5 3 3 7 7 7 7 7 5 3 3 7 7 7 8 8 4 3 1 1 3 1 2 9 3 2 16 4 6 1 9 9 5 2 1 7 4 4 2 10 10 10 10 10 3 9 3 3 5 1 1 7 1 1 1 1 1 7 2 2 10 2 9 17 12 11 4 17 14 14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 13 2 2 2 5 5 14 9 6 7 6 11 14 6 7 7 7 7 7 7 7 7 7 4 2 1 3 8 15 9 6 3 3 15 15 15 15 3 7 1 1 1 1 5 2 2 14 14 14 7 5 8 2 2 4 16 4 4 4 4 4 4 6 2 2 2 15 17 17 17 17 8 3 2 5 8 17 16 16 16 7 7 15 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 16 3 7 6 5 9 3 14 12 12 12 10 3 3 3 6 3 17 11 11 2 4 5 4 10 16 12 10 3 3 10 10 2 2 2 3 3 4 2 2 1 16 8 8 5 4 2 17 3 8 13 13 17 7 6 3 3 3 3 3 3 3 3 3 3 3 15 11 6 8 10 6 17 5 5 17 5 5 5 5 5 5 5 5 5 5 12 12 12 12 12 15 8 3 2 11 7 6 6 6 13 14 8 1 1 1 2 2 2 1 12 9 7 6 3 1 1 1 7 14 7 13 9 8 7 12 14 16 5 7 1 6 3 17 5 2 2 2 6 6 6 6 15 5 5 16 3 6 17 17 17 17 17 17 17 17 17 17 17 17 17 5 5 17 9 8 4 2 7 7 16 10 7 14 12 6 5 3 6 1 3 2 2 10 10 10 17 5 5 4 4 4 4 4 4 4 4 12 6 2 9 8 13 10 9 2 14 6 5 2 5 9 13 4 8 12 16 4 14 17 6 5 9 6 6 2 6 2 16 16 16 16 5 3 2 10 11 9 2 4 15 5 4 7 7 7 7 7 7 7 7 7 2 6 5 14 1 14 14 4 3 15 3 3 3 3 3 3 3 3 3 5 3 14 3 9 4 3 13 13 13 13 13 13 11 4 16 7 3 3 1 7 2 2 2 8 3 5 4 3 13 8 1 13 1 11 4 2 13 13 12 14 2 9 8 10 7 3 9 10 8 8 7 7 7 7 7 7 7 7 7 7 5 3 1 7 6 4 16 16 10 5 5 3 6 6 6 6 6 6 6 1 14 4 2 2 12 12 12 16 #include <iostream> #define MIN 999999999 using namespace std; int n, k, m; int arr[20]; int Min; bool check(){ int arrMax[20]; int index = 1; for(int i=1; i<=n-k+1; i++){ int Max = -1; for(int j=i; j<i+k; j++){ Max = max(Max, arr[j]); } arrMax[index++] = Max; } index = 1; for(int i=1; i<=n-k+1; i++){ int Max = arrMax[index]; int count = 0; for(int j=i; j<i+k; j++){ if(arr[j] == Max){ count++; } } //cout << count << endl; if(count>=m) return false; index++; } return true; } void BackTrack(int k, int count){ if(k == n + 1){ if(check()) Min = min(Min, count); return; } if(count >= Min) return; for(int i=1; i<=2; i++){ if(i==1){ BackTrack(k+1, count); } if(i==2){ arr[k] += 1; BackTrack(k+1, count+1); arr[k] -= 1; } } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n >> k >> m; for(int i=1; i<=n; i++){ cin >> arr[i]; } Min = MIN; cout << "#" << tc << " "; if(check()){ cout << "0" << endl; }else if(!check()){ BackTrack(1, 0); if(Min == MIN) cout << "-1" << endl; else cout << Min << endl; } //cout << check() << endl; } return 0; }