Untitled

mail@pastecode.io avatar
unknown
plain_text
8 months ago
2.5 kB
11
Indexable
Never
// Tắt đèn
import java.io.FileInputStream;
import java.util.Scanner;

public class TatDen {
	static int N, K, answer;
	static int[] light = new int[102];

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = scanner.nextInt();
			K = scanner.nextInt();
			answer = 0;
			for (int i = 1; i <= N; i++) {
				light[i] = scanner.nextInt();
			}
			backtrack(0, 0);
			System.out.println(answer);
		}
	}

	public static void backtrack(int index, int times) {
		if (times == 4) {
			int cnt = count(); // đếm số bóng đã tắt
			answer = (answer > cnt) ? answer : cnt;
			return;
		}
		for (int i = 1; i <= K; i++) {
			change(i); // thay đổi bóng liên quan khi tác động khóa i
			backtrack(i, times + 1);
			change(i);
		}
	}

	public static int count() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			if (light[i] == 0) {
				cnt++;
			}
		}
		return cnt;
	}

	public static void change(int index) {
		for (int i = 0; i < N; i++) {
			int num = index + i * (index + 1);
			if (num <= N) {
				light[num] = 1 - light[num];
			} else {
				break;
			}
		}
	}
}


// Hugo Thi chay
import java.io.FileInputStream;
import java.util.Scanner;

import org.omg.CORBA.INTERNAL;

public class HigoThiChay {
	static int M, D, answer;
	static int[][] runType = new int[5][2];

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			M = scanner.nextInt();
			D = scanner.nextInt();
			answer = Integer.MAX_VALUE;
			for (int i = 0; i < 5; i++) {
				int minute = scanner.nextInt();
				int second = scanner.nextInt();
				runType[i][0] = minute * 60 + second;
				runType[i][1] = scanner.nextInt();
			}
			backtrack(0, 0, 0, 0);
			if (answer == Integer.MAX_VALUE) {
				System.out.println("Case #" + tc + "\n" + -1);
				continue;
			}
			System.out.println("Case #" + tc + "\n" + (answer / 60) + " "
					+ (answer % 60));
		}
	}

	public static void backtrack(int runIndex, int timeSum, int mana, int s) {
		if (timeSum > answer || mana > M) {
			return;
		}
		if (s == D) {
			answer = (answer > timeSum) ? timeSum : answer;
			return;
		}
		for (int i = runIndex; i < 5; i++) {
			backtrack(i, timeSum + runType[i][0], mana + runType[i][1], s + 1);
		}
	}
}
Leave a Comment