Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
3.2 kB
2
Indexable
Never
package Hugo_Di_Tau;

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

public class Solution {
	static int n;
	static int[] c;
	static int[] p;
	static int[] tham;
	static int[] res;
	static int[] visit;
	static int[] mt;
	static int[] d = {-1,1};
	static int min;
	static int[] temp;
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("src/Hugo_Di_Tau/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			c = new int[3];
			p = new int[3];
			tham = new int[3];
			res = new int[3];
			visit = new int[n+1];
			mt = new int[n+1];
			temp = new int[n+1];
			for(int i = 0; i < 3; i++){
				c[i] = sc.nextInt();
				p[i] = sc.nextInt();
			}
			min = 100007;
			Try(0);
			//Trai(0);
			//Trai(1);
			//Trai(2);
			/*for(int i1 = 1; i1 <= n; i1++){
				System.out.print(mt[i1] + " ");
			}*/
			System.out.println("Case #" + test_case);
			System.out.println(min);
		}
	}
	
	public static void Trai(int k){
		int u = c[k];
		int v = p[k];
		
		int m = 0;
		if(visit[u] == 0){
			visit[u] = 1;
			mt[u] = 1;
			m++;
		}
		
		if(m < v){
			for(int i = 1; i <= n; i++){
				
				if(u-i >= 1 && u-i <= n && visit[u-i] == 0){
					visit[u-i] = 1;
					mt[u-i] = Math.abs(i)+1;
					m++;
				}
				if(m == v){
					break;
				}
				if(u+i >= 1 && u+i <= n && visit[u+i] == 0){
					visit[u+i] = 1;
					mt[u+i] = Math.abs(i)+1;
					m++;
				}
				if(m == v){
					break;
				}
			}
		}
	}
	
	public static void Phai(int k){
		int u = c[k];
		int v = p[k];
		
		int m = 0;
		if(visit[u] == 0){
			visit[u] = 1;
			mt[u] = 1;
			m++;
		}
		
		if(m < v){
			for(int i = 1; i <= n; i++){
				if(u+i >= 1 && u+i <= n && visit[u+i] == 0){
					visit[u+i] = 1;
					mt[u+i] = Math.abs(i)+1;
					m++;
				}
				if(m == v){
					break;
				}
				if(u-i >= 1 && u-i <= n && visit[u-i] == 0){
					visit[u-i] = 1;
					mt[u-i] = Math.abs(i)+1;
					m++;
				}
				if(m == v){
					break;
				}
			}
		}
		
	}
	

	public static void update(){
		for(int i = 1; i <= n; i++){
			mt[i] = 0;
			visit[i] = 0;
		}
	}
	
	public static void BTrack(int k){
		if(k == 3){
			for(int i = 0; i < 3; i++){
				if(temp[i] == 0){
					Trai(res[i]);
				}else if(temp[i] == 1){
					Phai(res[i]);
				}
				//System.out.println(temp[i]);
				/*for(int i1 = 1; i1 <= n; i1++){
					System.out.print(mt[i1] + " ");
				}
				System.out.println();*/
			}
			
			int tong = 0;
			for(int i = 1; i <= n; i++){
				tong += mt[i];
			}
			
			
			
			if(tong < min){
				min = tong;
			}
			update();
			//System.out.println(tong);
		}else{
			for(int i = 0; i < 2; i++){
				temp[k] = i;
				BTrack(k+1);
				temp[k] = 0;
			}
		}
	}
	
	public static void Try(int k){
		if(k == 3){
			BTrack(0);
			return;
		}else{
			for(int i = 0; i < 3; i++){
				if(tham[i] == 0){
					res[k] = i;
					tham[i] = 1;
					Try(k+1);
					tham[i] = 0;
				}
			}
		}
	}
}