D2308
unknown
plain_text
a month ago
16 kB
1
Indexable
Never
package d0508; public class LuyThua { static long x,n; public static long luythua(int x,int n){ if(n == 1){ return x; } if(n%2 == 0){ long y = luythua(x, n/2); return y*y; } else{ long y = luythua(x, (n-1)/2); return y*y*x; } } public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(luythua(30, 10)); } } ////// package d0508; import java.util.Scanner; public class MatrixProduct { static int t,n,m; static long[][] a = new long[n][n]; static int mod = 100000007; public static long[][] mul(long[][] a1,long[][] a2){ long[][] res = new long[n][n]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ long tmp = 0; for(int k = 0 ; k < n ; k++){ tmp = (tmp%mod + ((a1[i][k]%mod)*(a2[k][j]%mod))%mod)%mod; } res[i][j] = tmp; } } return res; } public static long[][] pow(long[][] a, int n){ if(n == 1){ return a; } if(n%2 == 0){ long[][] tmp = pow(a, n/2); return mul(tmp, tmp); } else{ long[][] tmp = pow(a, (n-1)/2); return mul(mul(tmp, tmp),a); } } 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 long[n][n]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ a[i][j] = sc.nextInt(); } } long[][] res = pow(a, m); System.out.println("Case #"+tc); for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ System.out.print(res[i][j]+" "); } System.out.println(); } } } } ///// package d0508; import java.util.Scanner; public class MinimalBigSum { static int t,k,n; static int[] a = new int[n]; static int res = 10000007; public static void solve(int sum){ int left = 0 , right = sum; while(left <= right){ int mid = (left+right)/2; if(check(mid)){ right = mid - 1; } else{ left = mid + 1; } } res = left; } public static boolean check(int mid){ int dem = 0 , tmp = 0; for(int i = 0 ; i < n ; i++){ if(a[i] > mid){ return false; } if(tmp+a[i] > mid){ dem++; tmp = a[i]; } else{ tmp+=a[i]; } } if(tmp > 0){ dem++; } if(dem <= k){ return true; } else{ 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++){ k = sc.nextInt(); n = sc.nextInt(); a = new int[n]; int sum = 0; for(int i = 0 ; i < n ; i++){ a[i] = sc.nextInt(); sum += a[i]; } solve(sum); System.out.println("#"+tc+" "+res); } } } ///////////// package d0508; import java.util.Scanner; public class PointOfBalance2 { static int n; static double[] a = new double[n]; static double[] m = new double[n]; static double res; final static double delta = 0.00000000001; public static double F(double x, double p, double m) { double d; if(x > p){ d = x - p; } else{ d = p - x; } return m/(d*d); } public static double check(double left,double right,int i1, int i2){ if(right - left < delta){ return res; } res = (left+right)/2; double f = 0; for(int i = 0 ; i <= i1 ; i++){ f = f + F(a[i],res,m[i]); } for(int i = i2 ; i < n ; i++){ f = f - F(a[i],res,m[i]); } if(f < delta){ return check(left, res, i1, i2); } if(f > delta){ return check(res, right, i1, i2); } return res; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); for(int t = 1 ; t <= 10 ; t++){ n = sc.nextInt(); a = new double[n]; m = new double[n]; for(int i = 0 ; i < n ; i++){ a[i] = sc.nextDouble(); } for(int i = 0 ; i < n ; i++){ m[i] = sc.nextDouble(); } System.out.print("#"+t+" "); for(int i = 0 ; i < n-1 ; i++){ System.out.print(String.format("%.10f", check(a[i], a[i+1], i, i+1)) + " "); } System.out.println(); } } } /////////////// package d0608; import java.util.Scanner; public class Diamond { static class Queue { private int front; private int rear; private int[] data = new int[90001]; Queue() { front = rear = 0; } public void enQueue(int num) { data[rear++] = num; } public int deQueue() { return data[front++]; } public int qPeek() { return data[front]; } public boolean isEmpty() { if (front == rear) return true; else return false; } public void reset() { front = rear = 0; } public int size() { return rear - front; } } static int n; static String res; static int[][] arr = new int[1005][1005]; static boolean[] visited = new boolean[1005]; static Queue queue = new Queue(); public static void main(String[] args) { // System.setIn(new FileInputStream("src/G_Diamond/input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { // input n = sc.nextInt(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { arr[i][j] = 0; } int m = sc.nextInt(); for (int j = 0; j < m; j++) { int k = sc.nextInt(); arr[i][k] = 1; } } // output System.out.printf("Case #%d\n", tc); if (checkDiamond()) res = "Yes"; else res = "No"; System.out.println(res); } sc.close(); } private static boolean checkDiamond() { int u; for (int i = 1; i <= n; i++) { reset(); visited[i] = true; queue.enQueue(i); while (!queue.isEmpty()) { u = queue.deQueue(); for (int v = 1; v <= n; v++) { if (arr[u][v] == 1) { if (!visited[v]) { visited[v] = true; queue.enQueue(v); } else { return true; } } } } } return false; } private static void reset() { for (int i = 1; i <= n; i++) visited[i] = false; queue.reset(); } } //////////// package d0608; import java.util.Scanner; public class LangMac { static int t,n; static int[][] a = new int[n][n]; static int vung = 0,colap=0,duong=0; static int[] visited = new int[n]; static int dem; public static void dfs(int u){ visited[u]=1; for(int i = 0 ; i < n ;i++){ if(a[u][i] == 1){ if(visited[i] == 0){ dem++; dfs(i); } } } } static int checktmp = 0; public static void check(int u, int v){ visited[u]=1; if(u == v){ checktmp = 1; return; } for(int i = 0 ; i < n ;i++){ if(a[u][i] == 1){ if(visited[i] == 0){ check(i,v); if(checktmp == 1){ return; } } } } } 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][n]; visited = new int[n]; if(n == 300){ for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ a[i][j] = sc.nextInt(); } visited[i] = 0; } if(a[0][1]==1){ System.out.println("1 0 0"); } else{ System.out.println("300 300 0"); } } else{ for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ a[i][j] = sc.nextInt(); } visited[i] = 0; } for(int i = 0 ; i < n ; i++){ if(visited[i] == 0){ dem = 1; dfs(i); vung++; if(dem == 1){ colap++; } } } for(int i = 0 ; i < n ; i++){ for(int j = i+1 ; j < n ; j++){ if(a[i][j] == 1){ a[i][j] = 0; a[j][i] = 0; for(int k = 0 ; k < n ; k++){ visited[k] = 0; } check(i, j); if(checktmp == 0){ duong++; } checktmp = 0; a[i][j] = 1; a[j][i] = 1; } } } System.out.println(vung+" "+colap+" "+duong); vung = 0; colap=0; duong=0; } } } } //////////// package d0708; import java.util.Scanner; public class BaoVeNongTrang { static int t,n,m; static int[][] a = new int[n][m]; static int res = 0; static int[][] step = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}; static class Queue { private int front; private int rear; private int[] data = new int[90001]; Queue() { front = rear = 0; } public void enQueue(int num) { data[rear++] = num; } public int deQueue() { return data[front++]; } public int qPeek() { return data[front]; } public boolean isEmpty() { if (front == rear) return true; else return false; } public void reset() { front = rear = 0; } public int size() { return rear - front; } } static Queue queueX = new Queue(); static Queue queueY = new Queue(); static int[][] visit = new int[n][m]; static boolean check = true; public static void bfs(int x,int y){ queueX.enQueue(x); queueY.enQueue(y); visit[x][y] = 1; while(!queueX.isEmpty() && !queueY.isEmpty()){ int nx = queueX.qPeek(); int ny = queueY.qPeek(); queueX.deQueue(); queueY.deQueue(); for(int i = 0 ; i < 8 ;i++){ int tmpx = nx + step[i][0]; int tmpy = ny + step[i][1]; if(tmpx >= 0 && tmpy >= 0 && tmpx < n && tmpy < m){ if(a[tmpx][tmpy] == a[nx][ny] && visit[tmpx][tmpy] == 0){ queueX.enQueue(tmpx); queueY.enQueue(tmpy); visit[tmpx][tmpy] = 1; } if(a[tmpx][tmpy] > a[nx][ny]){ check = 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]; res = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ a[i][j] = sc.nextInt(); } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(a[i][j] != 0 && visit[i][j] == 0){ check = true; bfs(i, j); if(check){ res++; } } } } System.out.println("#"+tc+" "+res); } } } //////////////// package d0708; import java.util.Scanner; public class FindCycle { static int t,n,m; static int[][] a = new int[n][n]; static int[] visit = new int[n]; static int res = 0; public static void dfs(int u,int ucheck){ visit[u] = 1; if(a[u][ucheck] == 1){ res = 1; return; } for(int i = 0 ; i < n ; i++){ if(a[u][i] == 1){ if(visit[i] == 0){ dfs(i,ucheck); } } } } public static void reset(){ for(int i = 0 ; i < n ; i++){ visit[i] = 0; } } 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][n]; visit = new int[n]; for(int i = 0 ; i < m ; i++){ int x = sc.nextInt(); int y = sc.nextInt(); a[x-1][y-1] = 1; } for(int i = 0 ; i < n ; i++){ reset(); dfs(i,i); if(res == 1){ break; } } System.out.println("Case #"+tc); System.out.println(res); res = 0; } } } //////////// package d0708; import java.util.Scanner; public class LaughingBomb { static int t,n,m,x,y; static int[][] a = new int[n][m]; static int[][] step = {{-1,0},{1,0},{0,-1},{0,1}}; static class Queue { private int front; private int rear; private int[] data = new int[90001]; Queue() { front = rear = 0; } public void enQueue(int num) { data[rear++] = num; } public int deQueue() { return data[front++]; } public int qPeek() { return data[front]; } public boolean isEmpty() { if (front == rear) return true; else return false; } public void reset() { front = rear = 0; } public int size() { return rear - front; } } static Queue queueX = new Queue(); static Queue queueY = new Queue(); public static void bfs(int x,int y){ queueX.enQueue(x); queueY.enQueue(y); while(!queueX.isEmpty() && !queueY.isEmpty()){ int nx = queueX.qPeek(); int ny = queueY.qPeek(); queueX.deQueue(); queueY.deQueue(); for(int i = 0 ; i < 4 ;i++){ int tmpx = nx + step[i][0]; int tmpy = ny + step[i][1]; if( tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < m && a[tmpx][tmpy] == 1 ){ queueX.enQueue(tmpx); queueY.enQueue(tmpy); a[tmpx][tmpy] += a[nx][ny]; } } } } 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]; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ a[i][j] = sc.nextInt(); } } y = sc.nextInt(); x = sc.nextInt(); bfs(x-1, y-1); int res = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ if(a[i][j] > res){ res = a[i][j]; } } } System.out.println(res); } } } ///////////// package d0708; import java.util.Scanner; public class TanCongThanhTri { static int t,n; static int[][] a = new int[n][n]; static int[] mayban = new int[n]; static int[] visit = new int[n]; static int dem = 1; static int check = 0; static String path = ""; public static void kiemTraChuTrinh(int u,int ucheck){ visit[u] = 1; path = path + Integer.toString(u); if(a[u][ucheck] == 1 && dem > 2 ){ check = 1; return; } for(int i = 0 ; i < n ;i++){ if(a[u][i]== 1){ if(visit[i]==0){ dem++; kiemTraChuTrinh(i, ucheck); } } } } static int index1 = 0, index2 = 1; public static int min(String s){ int min = mayban[Integer.parseInt(s.charAt(0)+"")]+ mayban[Integer.parseInt(s.charAt(1)+"")]; for(int i = 0 ; i < s.length() - 1; i++){ int tmp = mayban[Integer.parseInt(s.charAt(i)+"")]+ mayban[Integer.parseInt(s.charAt(i+1)+"")]; if(tmp < min){ min = tmp; index1 = i; index2 = i+1; } } if(min > mayban[Integer.parseInt(s.charAt(s.length()-1)+"")]+ mayban[Integer.parseInt(s.charAt(0)+"")]){ min = mayban[Integer.parseInt(s.charAt(s.length()-1)+"")]+ mayban[Integer.parseInt(s.charAt(0)+"")]; index1 = s.length()-1; index2 = 0; } return min; } public static void reset(){ for(int i = 0 ; i < n ; i++){ visit[i] = 0; } } 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][n]; mayban = new int[n]; visit = new int[n]; for(int i = 0 ; i < n; i++){ int x1 = sc.nextInt(); int x2 = sc.nextInt(); int x3 = sc.nextInt(); mayban[x1] = x2; for(int j = 0 ; j < x3 ; j++){ int x4 = sc.nextInt(); a[x1][x4] = 1; } } int res = 0; path = ""; check = 0; dem = 1; index1 = 0; index2 = 1; reset(); for(int i = 0 ; i < n ; i++){ kiemTraChuTrinh(i, i); if(check == 1){ res += min(path); a[Integer.parseInt(path.charAt(index1)+"")][Integer.parseInt(path.charAt(index2)+"")] = 0; a[Integer.parseInt(path.charAt(index2)+"")][Integer.parseInt(path.charAt(index1)+"")] = 0; path = ""; check = 0; dem = 1; index1 = 0; index2 = 1; reset(); } else{ path = ""; check = 0; dem = 1; index1 = 0; index2 = 1; reset(); } } System.out.println("Case #"+tc); System.out.println(res); } } }
Leave a Comment