day190824
unknown
plain_text
a month ago
9.0 kB
1
Indexable
Never
////////////////////////////////////////////////// package d1908; import java.util.Scanner; public class HugoVeNha { static int t, n; static int[][] a = new int[n][2]; static int[] solinh = new int[3]; static int res = 999999; public static int tonglinh(){ int sum = 0; for(int i = 0 ; i < 3 ; i++){ sum += solinh[i]; } return sum; } public static void Try(int cong, int chiphi) { if (cong == n) { if (res > chiphi) { res = chiphi; } return; } if (chiphi > res) { return; } for (int i = 0; i < 3; i++) { if (i == 0) { Try(cong + 1, chiphi + a[cong][1]); } else if (i == 1) { solinh[0] = solinh[0] + a[cong][0]; Try(cong + 1, chiphi + a[cong][1] * 2); solinh[0] = solinh[0] - a[cong][0]; } else if (i == 2) { if(tonglinh() >= a[cong][0]){ int linh1 = solinh[0]; int linh2 = solinh[1]; int linh3 = solinh[2]; for(int k = 2 ; k >= 0 ; k--){ if(solinh[k] < a[cong][0]){ solinh[k-1] += solinh[k]; solinh[k] =0 ; } else{ solinh[k] = solinh[k]-a[cong][0]; break; } } solinh[2] = solinh[1]; solinh[1] = solinh[0]; solinh[0] = 0; Try(cong+1, chiphi); solinh[2] = linh3; solinh[1] = linh2; solinh[0] = linh1; } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for (int tc = 1; tc <= t; tc++) { n = sc.nextInt(); a = new int[n][2]; solinh = new int[3]; for (int i = 0; i < n; i++) { a[i][0] = sc.nextInt(); a[i][1] = sc.nextInt(); } res = 999999; Try(0, 0); System.out.println("#" + tc + " " + res); } } } /////////////////////////////////// package d1908; import java.util.Scanner; public class HugoOngNau { static int t,m,n; static int[][] a = new int[n][m]; static boolean[][] visit = new boolean[n][m]; static int[][] stepchan = {{0, -1}, {-1, 0}, {0, 1}, {1, 1}, {1, 0}, {1, -1}}; static int[][] steple = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 0}, {0, -1}}; static int res = 0; public static void Try(int r,int c, int cnt,int sum){ if(cnt == 4){ if(res < sum){ res = sum; } return; } for(int i = 0 ; i < 6 ; i++){ int x,y; if(c%2==0){ x = r+steple[i][0]; y = c+steple[i][1]; } else{ x = r+stepchan[i][0]; y = c+stepchan[i][1]; } if(x >= 0 && x < n && y >= 0 && y < m && visit[x][y] == false){ visit[x][y]= true; Try(x, y, cnt+1, sum+a[x][y]); Try(r, c, cnt+1, sum+a[x][y]); visit[x][y]= false; } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for(int tc = 1 ; tc <= t ; tc++){ m = sc.nextInt(); n = sc.nextInt(); a = new int[n][m]; visit = new boolean[n][m]; for(int i = 0 ; i < n ; i ++){ for(int j = 0 ; j < m ; j++){ a[i][j] = sc.nextInt(); } } res = 0; for(int i= 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ visit[i][j] = true; Try(i, j, 1, a[i][j]); visit[i][j] = false; } } System.out.println("Case #"+tc); System.out.println(res*res); } } } ///////////////////////////////// package d1508; import java.util.Scanner; public class HugoQuanLyTau { static int t, n; static int[] a = new int[n + 1]; static int[][] cua = new int[3][2]; static int res = 200000; static boolean[] visit = new boolean[3]; public static int cal() { int sum = 0; for(int i = 1 ; i <= n ; i++){ if(a[i] > 0){ sum = sum + Math.abs(a[i]-i)+1; } } return sum; } public static void xeptrai(int k) { int ghe = cua[k][0]; int khach = cua[k][1]; int dem = 0; while(khach > 0){ if(ghe - dem > 0 && ghe - dem <= n && a[ghe- dem ] == 0 && khach > 0){ a[ghe - dem ] = ghe; khach--; } if(ghe + dem > 0 && ghe+dem <= n && a[ghe+dem] == 0 && khach > 0 ){ a[ghe+dem] = ghe; khach--; } dem++; } } public static void xepphai(int k) { int ghe = cua[k][0]; int khach = cua[k][1]; int dem = 0; while(khach > 0){ if(ghe - dem > 0 && ghe - dem <= n && a[ghe- dem ] == 0 && khach > 0){ a[ghe - dem ] = ghe; khach--; } if(ghe + dem > 0 && ghe+dem <= n && a[ghe+dem] == 0 && khach > 0){ a[ghe+dem] = ghe; khach--; } dem--; } } public static void trakhach(int k){ for(int i = 1 ; i <= n ; i++){ if(a[i] == cua[k][0]){ a[i]= 0; } } } public static void Try(int k) { if (k == 3) { if (res > cal()) { res = cal(); } return; } for(int i = 0 ; i < 3 ; i++){ for (int j = 0; j < 2; j++) { if (j == 0) { if (!visit[i]) { visit[i] = true; xeptrai(i); Try(k + 1); visit[i] = false; // Xoa dau mang a trakhach(i); } } if(j == 1){ if(!visit[i]){ visit[i] = true; xepphai(i); Try(k+1); visit[i] = false; //xoa dau mang a trakhach(i); } } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for (int tc = 1; tc <= t; tc++) { n = sc.nextInt(); a = new int[n + 1]; visit = new boolean[3]; for (int i = 0; i < 3; i++) { cua[i][0] = sc.nextInt(); cua[i][1] = sc.nextInt(); } res = 200000; Try(0); System.out.println("Case #"+tc); System.out.println(res); } } } //////////////////////////////// package d1908; import java.util.Scanner; public class MarioClimb { static int t, n, m, x1, y1, x2, y2; static int[][] a = new int[n][m]; static int[][] visit = new int[n][m]; static int[][] step = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; static class Queue{ int front,rear; int[] data = new int[90001]; public Queue(){ front = rear = 0; } public void enQ(int n){ data[rear++]=n; } public int deQ(){ return data[front++]; } public int qPeek(){ return data[front]; } public boolean isEmpty(){ if(front==rear){ return true; } return false; } } public static boolean BFS(int h){ Queue qx = new Queue(); Queue qy = new Queue(); qx.enQ(x1); qy.enQ(y1); visit[x1][y1]= h; while(!qx.isEmpty() && !qy.isEmpty()){ int nx = qx.deQ(); int ny = qy.deQ(); for(int i = 0 ; i < 4 ; i++){ if(i == 2 || i == 3){ for(int j = 1 ; j <= h ; j++){ int tmpx = nx + step[i][0]*j; int tmpy = ny + step[i][1]; if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < m && visit[tmpx][tmpy] < h && a[tmpx][tmpy]!=0){ qx.enQ(tmpx); qy.enQ(tmpy); visit[tmpx][tmpy] = h; } } } else{ int tmpx = nx + step[i][0]; int tmpy = ny + step[i][1]; if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < m && visit[tmpx][tmpy] < h && a[tmpx][tmpy]!=0){ qx.enQ(tmpx); qy.enQ(tmpy); visit[tmpx][tmpy] = h; } } if(visit[x2][y2] == h){ return true; } } } return false; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for (int tc = 1; tc <= t; tc++) { n = sc.nextInt(); m = sc.nextInt(); a = new int[n][m]; visit = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] = sc.nextInt(); if (a[i][j] == 2) { x1 = i; y1 = j; } if (a[i][j] == 3) { x2 = i; y2 = j; } } } int res = 0; for(int i = 1 ; i<=n ; i++){ if(BFS(i)){ res = i; break; } } System.out.println("Case #"+tc); System.out.println(res); } } } ////////////////////////////// package d1908; import java.util.Scanner; public class TietKiemDien { static int t, n, k; static int[] trangthai = new int[n+1]; static int res = 0; public static int cal() { int cnt = 0; for (int i = 1; i <= n; i++) { if (trangthai[i] == 0) { cnt++; } } return cnt; } public static void chonkhoa(int i) { int tmp = 0; while (i + tmp * (i + 1) <= n) { if (trangthai[i + tmp * (i + 1)] == 1) { trangthai[i + tmp * (i + 1)] = 0; } else { trangthai[i + tmp * (i + 1)] = 1; } tmp++; } } public static void Try(int khoa,int cnt) { if (cnt == 3) { if (res < cal()) { res = cal(); } return; } if(khoa == k+1){ if(res < cal()){ res = cal(); } return; } for (int j = 0; j < 2; j++) { if (j == 0) { Try(khoa+1,cnt); } if (j == 1) { chonkhoa(khoa); Try(khoa+1,cnt + 1); chonkhoa(khoa); } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); t = sc.nextInt(); for (int tc = 1; tc <= t; tc++) { n = sc.nextInt(); k = sc.nextInt(); trangthai = new int[n + 1]; for (int i = 1; i <= n; i++) { trangthai[i] = sc.nextInt(); } res = 0; Try(1,0); System.out.println("#"+tc+" "+res); } } }
Leave a Comment