D2208

mail@pastecode.io avatar
unknown
plain_text
20 days ago
12 kB
1
Indexable
Never
////////////////////////////////////
package d2208;

import java.util.Scanner;

public class BanBongBay {
	static int t, n;
	static int[] bong = new int[n];
	static int res = 0;
	static boolean[] visit = new boolean[n];

	public static int b3() {
		int max = 0;
		int[] a = new int[2];
		int dem = 0;
		for (int i = 0; i < n; i++) {
			if (visit[i] == false) {
				a[dem] = i;
				dem++;
			}
		}
		max = Math.max(bong[a[0]]*2, bong[a[1]]*2);
		return max;
	}

	public static void Try(int k, int sum) {
		if (k == n - 2) {
			if (res < sum + b3()) {
				res = sum + b3();
			}
			return;
		}
		for (int i = 0; i < n; i++) {
			if (visit[i] == false) {
				if (i == 0) {
					visit[i] = true;
					int check = 0;
					for (int j = 1; j < n; j++) {
						if (visit[j] == false) {
							check = j;
							break;
						}
					}
					if (check == 0) {
						Try(k + 1, sum + bong[i]);
					} else {
						Try(k + 1, sum + bong[check]);
					}
					visit[i] = false;
				} else if (i == n - 1) {
					visit[i] = true;
					int check = n - 1;
					for (int j = n - 2; j >= 0; j--) {
						if (visit[j] == false) {
							check = j;
							break;
						}
					}
					if (check == n - 1) {
						Try(k + 1, sum + bong[i]);
					} else {
						Try(k + 1, sum + bong[check]);
					}
					visit[i] = false;
				} else {
					visit[i] = true;
					int left = i;
					int right = i;
					for (int j = left - 1; j >= 0; j--) {
						if (visit[j] == false) {
							left = j;
							break;
						}
					}
					for (int j = right + 1; j < n; j++) {
						if (visit[j] == false) {
							right = j;
							break;
						}
					}
					if (left == i && right == i) {
						Try(k + 1, sum + bong[i]);
					}
					if (left != i && right != i) {
						Try(k + 1, sum + bong[left] * bong[right]);
					}
					if (left != i && right == i) {
						Try(k + 1, sum + bong[left]);
					}
					if (left == i && right != i) {
						Try(k + 1, sum + bong[right]);
					}
					visit[i] = 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();
			bong = new int[n];
			visit = new boolean[n];
			for (int i = 0; i < n; i++) {
				bong[i] = sc.nextInt();
			}
			res = 0;
			Try(0, 0);
			System.out.println("Case #" + tc);
			System.out.println(res);
		}
	}

}
//////////////////////////////////////
package d2208;

import java.util.Scanner;

public class BieuThucZero {
	static int t,n;
	static int[] a = new int[n];
	static int[] dau = new int[n];
	static int res2 = 0;
	public static boolean check(){
		int res=  0, trangthai = 0;
		int tmp = a[0];
		for(int i = 0 ; i < n - 1 ; i++){
			if(dau[i] == 1){
				tmp = tmp*10+a[i+1];
			}
			if(dau[i] == 2){
				if(trangthai == 0){
					res = tmp;
					tmp = a[i+1];
					trangthai = 1;
				}
				else if(trangthai == 1){
					res = res + tmp;
					tmp = a[i+1];
					trangthai = 1;
				}
				else if(trangthai == 2){
					res = res - tmp;
					tmp = a[i+1];
					trangthai = 1;
				}
			}
			if(dau[i] == 3){
				if(trangthai == 0){
					res = tmp;
					tmp = a[i+1];
					trangthai = 2;
				}
				else if(trangthai == 1){
					res = res + tmp;
					tmp = a[i+1];
					trangthai = 2;
				}
				else if(trangthai == 2){
					res = res - tmp;
					tmp = a[i+1];
					trangthai = 2;
				}
			}
		}
		if(trangthai == 1){
			res = res + tmp;
		}
		else if(trangthai == 2){
			res = res - tmp;
		}
		else{
			res = tmp;
		}
		if(res == 0){
			return true;
		}
		return false;
	}
	public static void Try(int k){
		if(k == n - 1){
			if(check()){
				res2++;
			}
			return;
		}
		for(int i = 0 ; i < 3 ; i++){
			if(i == 0){
				dau[k] = 1;
				Try(k+1);
				dau[k] = 0;
			}
			else if(i == 1){
				dau[k] = 2;
				Try(k+1);
				dau[k] = 0;
			}
			else if(i == 2){
				dau[k] = 3;
				Try(k+1);
				dau[k] = 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];
			for(int i = 0 ; i < n ; i++){
				a[i] = i +1 ;
			}
			dau = new int[n-1];
			res2 = 0;
			Try(0);
			System.out.println("#"+tc+" "+res2);
		}
	}

}
/////////////////////////////////
package d2208;

import java.util.Scanner;

public class HeThongDien {
	static int t,n,m,h;
	static int oo = 99999999;
	static int[][] a = new int[n][n];
	static int[] tram = new int[m];
	static int[] visitDao = new int[n];
	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 void bfs(int u){
		Queue q = new Queue();
		q.enQ(u);
		while(!q.isEmpty()){
			int nx = q.deQ();
			for(int i = 0 ; i < n ; i++){
				if(a[nx][i] == 1 && visitDao[i] > visitDao[nx]+1){
					visitDao[i] = visitDao[nx]+1;
					q.enQ(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();
			m = sc.nextInt();
			h = sc.nextInt();
			a = new int[n][n];
			tram = new int[m];
			visitDao = new int[n];
			for(int i = 0 ; i < n ; i++){
				visitDao[i] = oo;
			}
			for(int i = 0 ; i < m ; i++){
				tram[i] = sc.nextInt();
				visitDao[tram[i]] = 0;
			}
			for(int i = 0 ; i < h ; i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x][y] = 1;
				a[y][x] = 1;
			}
			for(int i = 0 ; i < m ; i++){
				bfs(tram[i]);
			}
			int res = -1,id = -1;
			for(int i = 0 ; i < n ; i++){
				if(visitDao[i] > res ){
					res = visitDao[i];
					id = i;
				}
			}
			System.out.println(id);
		}
	}

}
/////////////////////////
package d2208;

import java.util.Scanner;

public class LadderGame {
	static int t,n,b,m;
	static int[][] a = new int[n+1][n+1];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		for(int tc = 1 ; tc <= 10 ;tc++){
			n = sc.nextInt();
			b = sc.nextInt();
			m = sc.nextInt();
			a = new int[n+1][n+1];
			int dem = 1;
			for(int i = 0 ; i < m ; i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				int z = sc.nextInt();
				int u = sc.nextInt();
				for(int j = y ; j <= u ; j++){
					a[x][j] = dem;
				}
				dem++;
			}
			for(int i = 1 ; i <= n ; i++){
				int r = 1 , c = i;
				while(r <= n){
					if(a[r][c] == 0){
						r++;
					}
					else{
						if(c == 1){
							if(c+1 <= n && a[r][c+1]==a[r][c] ){
								int x = a[r][c];
								while(a[r][c] == x && c >= 1 && c <= n){
									c++;
								}
								c--;
								r++;
							}
						}
						else if(c == n){
							if(c-1 >= 1 && a[r][c-1] == a[r][c]){
								int x = a[r][c];
								while(a[r][c] == x && c >= 1 && c <= n){
									c--;
								}
								c++;
								r++;
							}
						}
						else if(c-1 >= 1 && c+1 <= n && a[r][c-1] == a[r][c] && a[r][c+1]==a[r][c] ){
							r++;
						}
						else if(c-1 >= 1 && c+1 <= n && a[r][c-1] != a[r][c] && a[r][c+1]==a[r][c]){
							int x = a[r][c];
							while(c >= 1 && c <= n && a[r][c] == x ){
								c++;
							}
							c--;
							r++;
						}
						else if(c-1 >= 1 && c+1 <= n && a[r][c-1] == a[r][c] && a[r][c+1]!=a[r][c]){
							int x = a[r][c];
							while(a[r][c] == x && c >= 1 && c <= n){
								c--;
							}
							c++;
							r++;
						}
					}
				}
				if(c == b){
					System.out.println("#"+tc+" "+i);
					break;
				}
			}
		}
	}

}
////////////////////////
package d2208;

import java.util.Scanner;

public class PhaHuyHeThongDien {
	static int t,n;
	static int[][] a = new int[n][n];
	static int[] visit = new int[n];
	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 void bfs(int u){
		Queue q=  new Queue();
		q.enQ(u);
		visit[u] = 1;
		while(!q.isEmpty()){
			int nx = q.deQ();
			for(int i = 0 ; i < n ; i++){
				if(a[nx][i] == 1 && visit[i] == 0){
					visit[i] = 1;
					q.enQ(i);
				}
			}
		}
	}
	public static void xoa(int u){
		for(int i = 0 ; i < n ; i++){
			if(a[u][i] == 1){
				a[u][i] = 2;
				a[i][u] = 2;
			}
		}
	}
	public static void quay(int u){
		for(int i = 0 ; i < n ; i++){
			if(a[u][i] == 2){
				a[u][i] = 1;
				a[i][u] = 1;
			}
		}
	}
	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];
			visit = new int[n];
			for(int i = 0 ; i < n ; i++){
				for(int j = 0 ; j < n ; j++){
					a[i][j]= sc.nextInt(); 
				}
			}
			int max = 0;
			for(int i = 0 ; i < n ; i++){
				if(visit[i] == 0){
					bfs(i);
					max++;
				}
			}
			
			int  id = -1;
			for(int i = 0 ; i < n ; i++){
				xoa(i);
				int dem = -1;
				visit = new int[n];
				for(int j = 0 ; j < n ; j++){
					if(visit[j] == 0){
						bfs(j);
						dem++;
					}
				}
				if(dem > max ){
					max = dem;
					id = i;
				}
				quay(i);
			}
			if(id == -1){
				System.out.println(0);
			}
			else{
				System.out.println(id+1);
			}
		}
	}

}
/////////////////////////
package luyentap2307;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class visitdepartment {
	static int N, E, K, T;
	static int len = 3000;
	static float[][] arr = new float[len][len];
	static float[][] timeXacSuat = new float[len][len];
	public static void reset() {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = 0;
				timeXacSuat[i][j] = 0;
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/luyentap2307/inputvisitdepartment.txt"));
		Scanner scanner = new Scanner(System.in);
		for (int tc = 1; tc <= 10; tc++) {
			N = scanner.nextInt();
			E = scanner.nextInt();
			K = scanner.nextInt();
			T = scanner.nextInt();
			reset();
			for (int i = 0; i < E; i++) {
				int dinh1 = scanner.nextInt();
				int dinh2 = scanner.nextInt();
				arr[dinh1][dinh2] = scanner.nextFloat();
			}
			//node
			timeXacSuat[1][0] = 1;
			for (int t = 1; t <= T; t++) {
				for (int i = 1; i <= N; i++) {
					if (timeXacSuat[i][t-1] != 0) {
						for (int j = 1; j <= N; j++) {
							timeXacSuat[j][t] += timeXacSuat[i][t-1]*arr[i][j];
						}
					}
				}
			}
			//Jang start tai 0, Kang tai K
			//10p di chuyen 1 lan
			int jangTime = T/10, kangTime = (T-K)/10;
			int jangD = 0, kangD = 0;
			float jangXS = 0, kangXS = 0;
			for (int i = 1; i <= N; i++) {
				if (timeXacSuat[i][jangTime] > jangXS) {
					jangXS = (float)timeXacSuat[i][jangTime];
					jangD = i;
				}
				if (timeXacSuat[i][kangTime] > kangXS) {
					kangXS = (float)timeXacSuat[i][kangTime];
					kangD = i;
				}
			}
			
			System.out.print("#" + tc + " ");
			System.out.println(String.format("%d %.6f %d %.6f", jangD, jangXS, kangD, kangXS));
		}
	}
}
Leave a Comment