Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
2.1 kB
3
Indexable
Never
#include<iostream>
using namespace std;

int nTestcase, N, Min;
int train[3][2];
int seat[61];
bool visited[3];

int distancetoLeft(int start){
	for(int i = start; i > 0; i--){
		if(seat[i] == -1) return start - i;
	}
	return 10000;
}

int distancetoRight(int start){
	for(int i = start; i <= N; i++){
		if(seat[i] == -1) return i - start;
	}
	return 10000;
}

bool checkopen(){
	for(int i = 0; i < 3; i++){
		if(visited[i] == false) return false;
	}
	return true;
}

void backtrack(int sum){
	int left, right;
	if(checkopen()){
		Min = Min > sum ? sum : Min;
		return;
	}
	for(int i = 0; i < 3; i++){
		if(visited[i]) continue;
		visited[i] = true;
		//int add = train[i][0];
		int add = train[i][1];
		for(int j = 0; j < train[i][1] - 1; j++){
			left = distancetoLeft(train[i][0]);
			right = distancetoRight(train[i][0]);
			if(left < right){
				seat[train[i][0] - left] = i;
				add += left;
			}else{
				seat[train[i][0] + right] = i;
				add += right;
			}
		}
		left = distancetoLeft(train[i][0]);
		right = distancetoRight(train[i][0]);
		if(left != right){
			if(left < right){
				seat[train[i][0] - left] = i;
				add += left;
			}else{
				seat[train[i][0] + right] = i;
				add += right;
			}
			backtrack(sum + add);
		}else{
			add += left;
			seat[train[i][0] - left] = i;
			backtrack(sum + add);
			seat[train[i][0] - left] = -1;

			seat[train[i][0] + right] = i;
			backtrack(sum + add);
			seat[train[i][0] + right] = -1;
		}
		visited[i] = false;
		for(int j = 1; j <= N; j++){
			if(seat[j] == i)
				seat[j] = -1;
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for(int testcase = 1; testcase <= nTestcase; testcase++){
		cin >> N;
		for(int i = 0; i < 3; i++){
			cin >> train[i][0] >> train[i][1];
		}
		for(int i = 0; i < 3; i++){
			visited[i] = false;
		}
		for(int i = 1; i <= N; i++){
			seat[i] = -1;
		}
		Min = 1000000;
		backtrack(0);
		cout << "Case #" << testcase << endl << Min << endl;
	}
	return 0;
}
Leave a Comment