Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.9 kB
1
Indexable
Never
package chu_voi_nho;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, K, M, res;
	static int[] a, max, dem;

	static void findmax() {
		max = new int[N - K + 1];
		dem = new int[N - K + 1];
		for (int i = 0; i < N - K + 1; i++) {
			int count = 0;
			int tmp = a[i];
			for (int j = i; j < i + K; j++) {
				if (a[j] > tmp) {
					tmp = a[j];
					count = 1;
				} else if (a[j] == tmp) {
					count++;
				}
			}

			max[i] = tmp;
			dem[i] = count;

		}
		
	}

	static void backtrack(int k, int count) {
		if (k == N) {
			findmax();
			int check = 0;
			for(int i = 0; i <N-K+1;i++){
				if(dem[i] >= M){
					check = 1;
					break;
				}
			}
			if (check == 0) {
				res = Math.min(res, count);
			}
			return;
		}
		if (count >= res) {
			return;
		}

		for (int i = 0; i < 2; i++) {
			a[k] += i;
			backtrack(k + 1, count + i);
			a[k] -= i;
		}

	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			N = scanner.nextInt();
			K = scanner.nextInt();
			M = scanner.nextInt();
			a = new int[N];
			for (int i = 0; i < N; i++) {
				a[i] = scanner.nextInt();
			}

			res = Integer.MAX_VALUE;

			// for (int i = 0; i < N - K + 1; i++) {
			// System.out.print(max[i] + " ");
			// }
			// System.out.println();
			//
			// for (int i = 0; i < N - K + 1; i++) {
			// System.out.print(dem[i] + " ");
			// }
			// System.out.println();

			if (M == 1) {
				res = -1;
			} else {
				backtrack(0, 0);
			}

			System.out.println("#" + t + " " + res);
		}
		scanner.close();
	}
}