Quân Vương Đình
@dinhquan96
Viet Nam, Hà Nội
Institution: KMA
package BatTatDen; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int M, K, Answer, max; static int[] Arr; static int[] A; static int[] VS; static int[] Set; static int check = 0; public static void main(String[] agrs) throws Exception { System.setIn(new FileInputStream("src/BatTatDen/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { M = sc.nextInt(); K = sc.nextInt(); Arr = new int[M + 1]; Set = new int[K + 1]; A = new int[M + 1]; Answer = 0; for (int i = 1; i < M + 1; i++) { A[i] = Arr[i] = sc.nextInt(); if (Arr[i] == 0) { Answer++; } } Backtrack(1); System.out.println("#" + tc + " " + Answer); } } public static void Backtrack(int v) { if (v == K + 1) { int n = 0; for (int i = 1; i <= K; i++) { if (Set[i] == 1) { n++; } } if (n <= 3 && n > 0) { int dem = 0; for (int i = 1; i <= K; i++) { if (Set[i] == 1) { for (int j = 0; j <= M; j++) { if ((i + j * (i + 1)) >= 0 && (i + j * (i + 1)) <= M) { A[(i + j * (i + 1))] = 1 - A[(i + j * (i + 1))]; } else { break; } } } } for (int i = 1; i <= M; i++) { if (A[i] == 0) { dem++; } } if (dem > Answer) { Answer = dem; } for (int i = 1; i <= M; i++) { A[i] = Arr[i]; } } return; } else { for (int i = 0; i < 2; i++) { Set[v] = i; Backtrack(v + 1); } } } } package BraveArmy; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int M, N, x, y, Answer, max, check; static int[][] Arr; static int[] A; static int[][] VS; static int[][] Set; static int[] dx = { -1, 0, 1, 0 }; static int[] dy = { 0, 1, 0, -1 }; public static void main(String[] agrs) throws Exception { System.setIn(new FileInputStream("src/BraveArmy/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { M = sc.nextInt(); N = sc.nextInt(); x = sc.nextInt() - 1; y = sc.nextInt() - 1; Arr = new int[M][N]; Set = new int[M][N]; VS = new int[M][N]; Answer = 0; max = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { Arr[i][j] = sc.nextInt(); } } VS[x][y] = 1; Backtrack(x, y, Arr[x][y]); System.out.println("#" + tc + " " + Answer); } } public static void Backtrack(int x, int y, int v) { for (int i = 0; i < 4; i++) { int check = 0; int a = x + dx[i]; int b = y + dy[i]; if (a >= 0 && a < M && b >= 0 && b < N && VS[a][b] == 0) { if (Arr[a][b] <= v / 2 && Arr[a][b] > 0) { VS[a][b] = 1; check = 1; max++; Backtrack(a, b, v + Arr[a][b]); max--; VS[a][b] = 0; } if (Arr[a][b] > v / 2 && Arr[a][b] < v) { VS[a][b] = 1; check = 1; max++; Backtrack(a, b, v - Arr[a][b]); max--; VS[a][b] = 0; } } } if (check == 0) { if (max > Answer) { Answer = max + 1; } } } } package HappyCount; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int M, N, K, Answer, hanhphuc; static int[][] Arr; static int nhanvien[]; static int Bophan[]; static int[] cong = { 5, 3, 1, 0 }; public static void main(String[] agrs) throws Exception { System.setIn(new FileInputStream("src/HappyCount/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); Answer = 0; hanhphuc = 0; M = sc.nextInt(); K = sc.nextInt(); Arr = new int[N][3]; Bophan = new int[M]; nhanvien = new int[N]; int ans = 0; int k = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < 3; j++) { Arr[i][j] = sc.nextInt(); } } Backtrack(0); System.out.println("Case #" + tc); System.out.println(Answer); } } public static void Backtrack(int stt) { if (stt == N) { if (Answer < hanhphuc) Answer = hanhphuc; return; } else { int x, y; for (x = 0; x < N; x++) { if (nhanvien[x] == 0) { nhanvien[x] = 1; for (y = 0; y < 3; y++) { if (Bophan[Arr[x][y] - 1] < K) { Bophan[Arr[x][y] - 1]++; hanhphuc += cong[y]; break; } } Backtrack(stt + 1); nhanvien[x] = 0; hanhphuc -= cong[y]; if (y != 3) { Bophan[Arr[x][y] - 1]--; } } } } } } package jogging; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int N, K, max; static int[][] Arr; static int[] Dx = { 1, -1, 0, 0 }; static int[] Dy = { 0, 0, 1, -1 }; static int x1, y1; static int[] Vs = new int[4]; static int[][] VsM; public static void main(String args[]) throws Exception { System.setIn(new FileInputStream("src/jogging/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int test = 1; test <= T; test++) { N = sc.nextInt(); K = sc.nextInt(); Arr = new int[N][N]; VsM = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { Arr[i][j] = sc.nextInt(); } } max = 0; int huong = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { x1 = i; y1 = j; BT(i, j, 0, huong, 0); } } System.out.println("#" + test + " " + max); } } static void BT(int x, int y, int count, int huong, int total) { if (x == x1 && y == y1 && total != 0) { if (count > max) { max = count; } } else { for (int i = 0; i < 4; i++) { int a = x + Dx[i]; int b = y + Dy[i]; if (a >= 0 && a <= N - 1 && b >= 0 && b <= N - 1 && VsM[a][b] == 0) { int d = Arr[x][y] - Arr[a][b]; if (huong == i) { if (d >= 0 && total + d * d + 1 <= K) { VsM[a][b] = 1; BT(a, b, count + 1, i, total + d * d + 1); VsM[a][b] = 0; } if (d < 0 && total + d * d * 2 + 1 <= K) { VsM[a][b] = 1; BT(a, b, count + 1, i, total + d * d * 2 + 1); VsM[a][b] = 0; } } else if (huong != i && Vs[i] == 0 && huong + 1 != i && huong - 1 != i) { Vs[i] = 1; if (d >= 0 && total + d * d + 1 <= K) { VsM[a][b] = 1; BT(a, b, count + 1, i, total + d * d + 1); VsM[a][b] = 0; } if (d < 0 && total + d * d * 2 + 1 <= K) { VsM[a][b] = 1; BT(a, b, count + 1, i, total + d * d * 2 + 1); VsM[a][b] = 0; } Vs[i] = 0; } } } } } } package SkyForce; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int M, Ans, check; static int[][] Arr; static int[][] VS; static int[] dx = { -1, -1, -1 }; static int[] dy = { 0, -1, 1 }; public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("src/SkyForce/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 1; t <= T; t++) { M = sc.nextInt(); Arr = new int[M + 1][5]; VS = new int[M + 1][5]; Ans = -1; for (int i = 0; i < M; i++) { for (int j = 0; j < 5; j++) { Arr[i][j] = sc.nextInt(); } } check = 0; BackTrack(M, 2, 0); System.out.println("Case #" + t); System.out.println(Ans); } } public static void BackTrack(int x, int y, int dem) { if (x == 0) { if (dem > Ans) { Ans = dem; } return; } else { for (int i = 0; i < 3; i++) { int a = x + dx[i]; int b = y + dy[i]; if (a >= 0 && b >= 0 && b < 5) { if (Arr[a][b] == 1) { BackTrack(a, b, dem + 1); } if (Arr[a][b] == 0 || Arr[a][b] == -1) { BackTrack(a, b, dem); } if (Arr[a][b] == 2 && check == 0) { for (int c = a - 4; c < M; c++) { for (int d = 0; d < 5; d++) { if (c >= 0) { if (Arr[c][d] == 2) { Arr[c][d] = -1; } } } } check = 1; BackTrack(a, b, dem); for (int c = a - 4; c < M; c++) { for (int d = 0; d < 5; d++) { if (c >= 0) { if (Arr[c][d] == -1) { Arr[c][d] = 2; } } } } check = 0; } if (Arr[a][b] == 2 && check == 1) { BackTrack(a, b, dem - 1); } } } } } } package Voyager; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int M, N, x, y, xx, yy, front, rear, Answer, max; static int[][] Arr; static int[][] Q = new int[1000000][2]; static int[] dx = { -1, 0, 1, 0, -1, 1, -1, 1, -2, 0, 0, 2 }; static int[] dy = { 0, 1, 0, -1, -1, -1, 1, 1, 0, -2, 2, 0 }; public static void main(String[] agrs) throws Exception { System.setIn(new FileInputStream("src/Voyager/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { M = sc.nextInt(); N = sc.nextInt(); Arr = new int[M][N]; front = 0; rear = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { Arr[i][j] = sc.nextInt(); if (Arr[i][j] == 2) { Arr[i][j] = 0; x = i; y = j; } else if (Arr[i][j] == 3) { Arr[i][j] = -1; xx = i; yy = j; } else if (Arr[i][j] == 1) { Arr[i][j] = -2; } else { Arr[i][j] = -1; } } } Q[rear][0] = x; Q[rear][1] = y; rear++; while (front != rear) { int x = Q[front][0]; int y = Q[front][1]; front++; for (int i = 0; i < 12; i++) { int a = x + dx[i]; int b = y + dy[i]; if (a >= 0 && a < M && b >= 0 && b < N) { if (Arr[a][b] == -1) { Arr[a][b] = Arr[x][y]; } if (Arr[a][b] == -2) { Q[rear][0] = a; Q[rear][1] = b; rear++; Arr[a][b] = Arr[x][y] + 1; } } } } System.out.println("Case " + tc); System.out.println(Arr[xx][yy]); } } } package Wooden; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int M, Answer, dem; static int[][] Arr; static int[] VS; static int[] Set; static int check = 0; public static void main(String[] agrs) throws Exception { System.setIn(new FileInputStream("src/Wooden/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { M = sc.nextInt(); Answer = 0; Arr = new int[M][2]; VS = new int[M]; Set = new int[M]; for (int i = 0; i < M; i++) { for (int j = 0; j < 2; j++) { Arr[i][j] = sc.nextInt(); } } Backtrack(0, 0); System.out.println("#" + tc + " " + Answer); } } public static void Backtrack(int v, int dem) { if (dem > Answer) { Answer = dem; } if (v == 0) { for (int i = 0; i < M; i++) { if (VS[i] == 0) { VS[i] = 1; Set[v] = i; Backtrack(v + 1, dem + 1); VS[i] = 0; } } } else { for (int i = 0; i < M; i++) { if (VS[i] == 0) { if ((Arr[Set[v - 1]][0] >= Arr[i][0] && Arr[Set[v - 1]][1] >= Arr[i][1])) { VS[i] = 1; Set[v] = i; Backtrack(v + 1, dem + 1); VS[i] = 0; } } } } } } package CleaningRobot; import java.util.Scanner; public class Solution { static int[][] Q; static int M; static int N; static int[] VS; static int[] Set; static int[][] A, khoangcach; static int[][] Visit; static int[][] D; static int[][] B; static int n, k, min; static boolean check = true; static int[] Dx = { 0, -1, 0, 1 }; static int[] Dy = { -1, 0, 1, 0 }; public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int test = 1; test <= T; test++) { M = sc.nextInt(); N = sc.nextInt(); A = new int[M][N]; D = new int[M * N][2]; Q = new int[100000][2]; k = 1; min = 100000; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { A[i][j] = sc.nextInt(); if (A[i][j] == 1) { D[k][0] = i; D[k][1] = j; k++; } if (A[i][j] == 3) { D[0][0] = i; D[0][1] = j; } } } B = new int[k][k]; VS = new int[k]; Set = new int[k]; for (int i = 0; i < k; i++) { Visit = new int[M][N]; khoangcach = new int[M][N]; BFS(i); for (int j = 0; j < k; j++) { B[i][j] = khoangcach[D[j][0]][D[j][1]]; } } if (check) { BackTrack(1, 0); System.out.println("Case #" + test); System.out.println(min); } else { System.out.println("Case #" + test); System.out.println("-1"); } } } static void BFS(int i) { int front = 0; int rear = 0; int dem = 1; Q[rear][0] = D[i][0]; Q[rear][1] = D[i][1]; rear++; Visit[D[i][0]][D[i][1]] = 1; while (front != rear) { int x = Q[front][0]; int y = Q[front][1]; front++; for (int j = 0; j < 4; j++) { int a = x + Dx[j]; int b = y + Dy[j]; if (a >= 0 && a <= M - 1 && b >= 0 && b <= N - 1) { if (A[a][b] != 2 && Visit[a][b] == 0) { khoangcach[a][b] = khoangcach[x][y] + 1; Q[rear][0] = a; Q[rear][1] = b; Visit[a][b] = 1; rear++; if (A[a][b] == 1 || A[a][b] == 3) { dem++; } } if (dem == k) { front = rear; break; } } } } if (dem == k) check = true; else check = false; } static void BackTrack(int v, int sum) { if (v == k) { if (sum < min) { min = sum; } return; } if (sum > min) { return; } else { for (int i = 1; i < k; i++) { if (VS[i] == 0) { VS[i] = 1; Set[v] = i; BackTrack(v + 1, sum + B[Set[v - 1]][Set[v]]); VS[i] = 0; } } } } } package Code; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; package DeSTC; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int N, Answer; static int[] pawn; static int[] gold; public static void main(String[] agrs) throws Exception { System.setIn(new FileInputStream("src/DeSTC/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); pawn = new int[N]; gold = new int[N]; Answer = 0; for (int i = 0; i < N; i++) { pawn[i] = sc.nextInt(); gold[i] = sc.nextInt(); } Answer = 99999; Backtrack(0, 0, 0, 0, 0); System.out.println("#" + tc + " " + Answer); } } public static void Backtrack(int index, int sumGold, int pawn0, int pawn1, int pawn2) { if (index == N) { if (sumGold < Answer) { Answer = sumGold; } } else { if (sumGold >= Answer) { return; } else { for (int i = 0; i < 3; i++) { if (i == 0) { Backtrack(index + 1, sumGold + gold[index], pawn0, pawn1, pawn2); } else if (i == 1) { Backtrack(index + 1, sumGold + 2 * gold[index], pawn0 + pawn[index], pawn1, pawn2); } else { if (pawn0 + pawn1 + pawn2 >= pawn[index]) { if (pawn2 >= pawn[index]) { Backtrack(index + 1, sumGold, 0, pawn0, pawn1); } else if (pawn2 + pawn1 >= pawn[index]) { Backtrack(index + 1, sumGold, 0, pawn0, pawn2 + pawn1 - pawn[index]); } else { Backtrack(index + 1, sumGold, 0, pawn2 + pawn1 + pawn0 - pawn[index], 0); } } } } } } } }
Các lần nộp bài đã được ghi nhân(Xem dạng tệp tin văn bản)
RSS