Untitled
unknown
plain_text
10 days ago
2.5 kB
8
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