Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
2.8 kB
2
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, gate[][], visit[], seat[], dis, min;

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			gate = new int[3][2];

			for (int i = 0; i < 3; i++) {
				gate[i][0] = sc.nextInt();
				gate[i][1] = sc.nextInt();
			}

			seat = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				seat[i] = -1;
			}

			visit = new int[3];
			dis = 0;
			min = 1000;

			open();

			System.out.println("Case #" + tc);
			System.out.println(min);

		}
		sc.close();
	}

	private static void open() {
		// TODO Auto-generated method stub
		if(dis>=min) return;
		if (check()) {
			min = dis < min ? dis : min;
			return;
		}
		for (int g = 0; g < 3; g++) {
			if (visit[g] == 0) {
				visit[g] = 1;
				int tmp = dis;
				int l, r;
				for (int i = 1; i <= gate[g][1] - 1; i++) {
					l = getLeft(gate[g][0]);
					r = getRight(gate[g][0]);

					if (l <= r) {
						seat[gate[g][0] - l] = g;
						dis += l + 1;
					} else {
						seat[gate[g][0] + r] = g;
						dis += r + 1;
					}
				}
				// last person
				l = getLeft(gate[g][0]);
				r = getRight(gate[g][0]);

				if (l < r) {
					seat[gate[g][0] - l] = g;
					dis += l + 1;
					open();
				} else if (l > r) {
					seat[gate[g][0] + r] = g;
					dis += r + 1;
					open();
				} else {
					for (int j = 0; j < 2; j++) {
						int tmp2;
						if (j == 0) {
							tmp2 = dis;
							dis += l + 1;
							seat[gate[g][0] - l] = g;
							open();
							dis = tmp2;
							seat[gate[g][0] - l] = -1;
						} else {
							tmp2 = dis;
							dis += r + 1;
							seat[gate[g][0] + r] = g;
							open();
							dis = tmp2;
							seat[gate[g][0] + r] = -1;
						}
					}
				}

				dis = tmp;
				for (int i = 1; i <= n; i++) {
					if (seat[i] == g) {
						seat[i] = -1;
					}
				}
				visit[g] = 0;
			}
		}

	}

	private static boolean check() {
		// TODO Auto-generated method stub
		for (int i = 0; i < 3; i++) {
			if (visit[i] == 0)
				return false;
		}
		return true;
	}

	private static int getRight(int s) {
		// TODO Auto-generated method stub
		for (int i = s; i <= n; i++) {
			if (seat[i] == -1) {
				return i - s;
			}
		}

		return 10000;
	}

	private static int getLeft(int s) {
		// TODO Auto-generated method stub
		for (int i = s; i >= 1; i--) {
			if (seat[i] == -1) {
				return s - i;
			}
		}
		return 10000;
	}

}
Leave a Comment