Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.6 kB
0
Indexable
Never
/////giao hang
package bla;

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

public class Solution {
	static int x_start;
	static int y_start;
	static int x_end;
	static int y_end;
	static int n;
	static long ans;
	static int [][] map;
	static int [] vis;
	public static long kc(int x , int y , int a, int b){
		int sum = Math.abs(x-a) + Math.abs(y-b);
		return sum;
	}
	public static void backTrack (int x , int y, int k, long sum){
		if(sum > ans){
			return;
		}
		if(k==n){
			sum += kc(x_end, y_end,x,y);
			ans = Math.min(sum, ans);
			return;
		}
		for (int i = 0; i < n; i++) {
			if(vis[i] == 0){
				vis[i] = 1;
				backTrack(map[i][0] , map[i][1] , k+1 , sum + kc(x,y,map[i][0], map[i][1]));
				vis[i] = 0;
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			x_start = sc.nextInt();
			y_start = sc.nextInt();
			x_end = sc.nextInt();
			y_end = sc.nextInt();
			n = sc.nextInt();
			map = new int [n][2];
			vis = new int [n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < 2; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			ans = Long.MAX_VALUE;
			backTrack(x_start,y_start,0,0);
			System.out.println("Case #"+tc+" "+ans);
		}
	}
}


/////
hugo thi chay

package bla;

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

public class Solution {
	static int nangLuong;
	static int quangDuong;
	static long ans;
	static int [][] arr;
	public static void backTrack(int k , int qd , int nl , int time){
		if(nl > nangLuong){
			return;
		}
		if(time > ans){
			return;
		}
//		if(qd > quangDuong){
//			return;
//		}
		if(k == 5){
			if(qd == quangDuong && time < ans){
				ans = time;
			}
			return;
		}
		for (int i = 0; i <= quangDuong; i++) {
			backTrack(k+1, qd + i, nl + (i*arr[k][1]), time + (i*arr[k][0]));
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			nangLuong = sc.nextInt();
			quangDuong = sc.nextInt();
			arr = new int [5][2];
			for (int i = 0; i < 5; i++) {
				int phut = sc.nextInt();
				int giay = sc.nextInt();
				int nl = sc.nextInt();
				arr[i][0] = phut*60 + giay;
				arr[i][1] = nl;
			}
			ans = Long.MAX_VALUE;
			backTrack(0, 0, 0, 0);
			if(ans == Long.MAX_VALUE){
				System.out.println("Case #"+tc);
				System.out.println("-1");
			}else{
				System.out.println("Case #"+tc);
				System.out.println(ans/60+" "+ans%60);
			}
		}
	}
}


///
hugo ve nha

package bla;

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

public class Solution {
	static int soCong;
	static int ans;
	static int arr[][];
	static int quanLinh[];
	
	public static void backTrack(int k,int chiPhi){
		if(chiPhi > ans){
			return;
		}
		if(k==soCong){
			if(chiPhi < ans){
				ans = chiPhi;
			}
			return;
		}
		for (int i = 1; i <= 3; i++) {
			if(i==1){
				chiPhi += arr[k][1];
				backTrack(k+1, chiPhi);
				chiPhi -= arr[k][1];
			}
			else if(i==2){
				quanLinh[0] += arr[k][0];
				chiPhi += arr[k][1] * 2;
				backTrack(k+1, chiPhi);
				chiPhi -= arr[k][1] * 2;
				quanLinh[0] -= arr[k][0];
			}else if(i==3){
				int t0 = quanLinh[0];
				int t1 = quanLinh[1];
				int t2 = quanLinh[2];
				if(t0+t1+t2 >= arr[k][0]){
					if(t2 >= arr[k][0]){
						quanLinh[2] = t1;
						quanLinh[1] = t0;
						quanLinh[0] = 0;
					}else if(t1 >= arr[k][0] - t2){
						quanLinh[2] = t1  - (arr[k][0] - t2);
						quanLinh[1] = t0;
						quanLinh[0] = 0;
					}else if(t0 >= arr[k][0] - t2 - t1){
						quanLinh[2] = 0 ;
						quanLinh[1] = t0 - (arr[k][0]-t1 - t2);
						quanLinh[0] = 0;
					}
					backTrack(k+1, chiPhi);
					quanLinh[0] = t0;
					quanLinh[1] = t1;
					quanLinh[2] = t2;
				}
			}
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			soCong = sc.nextInt();
			arr = new int [soCong][2];
			quanLinh = new int [3];
			ans = 1000000;
			for (int i = 0; i < soCong; i++) {
				for (int j = 0; j < 2; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			backTrack(0,0);
			System.out.println("#"+tc+" "+ans);
		}
	}
}