Untitled

 avatar
unknown
plain_text
a year ago
1.4 kB
3
Indexable
class S {
	static int[] R;
	static int Ans = 0;
	static int N, M, K;
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			K = sc.nextInt();
			M = sc.nextInt();
			R = new int[18];
			Ans = 9999;
			for (int i = 0; i < N; i++) {
				R[i] = sc.nextInt();
			}
			backTrack(0, 0);
			System.out.print("#" + tc);
			if (Ans == 9999) {
				System.out.println(" -1");
			} else {
				System.out.println(" " + Ans);
			}
		}
	}

	private static void backTrack(int k, int count) {
		if (count >= Ans) {
			return;
		}
		if (k == N) {
			if (!biBat()) {
				if (count < Ans) {
					Ans = count;
				}
			}
			return;
		}

		for (int i = 0; i <= 1; i++) {
			if (i == 0) {
				backTrack(k + 1, count);
			} else {
				R[k] += 1;
				backTrack(k + 1, count + 1);
				R[k] -= 1;
			}
		}
	}

	static boolean biBat() {
		for (int i = 0; i <= N - K; i++) {
			int count = 0;
			int max = findMax(i, i + K);
			for (int j = i; j < i + K; j++) {
				if (R[j] == max) {
					count++;
				}
			}
			if (count >= M) {
				return true;
			}
		}
		return false;
	}

	private static int findMax(int i, int j) {
		int max = 0;
		for (int k = i; k < j; k++) {
			max = Math.max(max, R[k]);
		}
		return max;
	}
}
Editor is loading...
Leave a Comment