Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.6 kB
8
Indexable
#include <iostream>
#include <stdio.h>
using namespace std;
int T, n;
int ad[3][2], as[3][2], visit[1000], timet[1000], xep[3];
int visit_hv[3] = {0,0,0}, con[3];
int kq, people;

void reset() {
	for(int i = 0; i < n; i ++) {
		timet[i] = 0;
		visit[i] = 0;
	}
}
int abs(int a) {
	if (a < 0) a = -a;
	else a = a;
	return a;
}

int dkb(int i) {
	if(i >= 0 && i < n) return 1;
	return 0;
}

int sumt() {
	int sum = 0;
	for(int i = 0; i < n; i ++) {
		sum += timet[i];
	}
	return sum;
}
void cost() {
	int k, h, sav=0, nguoi, t;
	for(int i = 0; i < 3; i ++) {
		if(con[i] == 0) k = -1;
		else k = 1;

		h = 1; t = 1;
		nguoi = as[i][1];
		int mid = as[i][0]-1;
		sav = mid;
		if(visit[sav] == 0 && dkb(sav)) {
			visit[sav] = i+1;
			timet[sav] = 1;
			nguoi--;
		}
		while(nguoi > 0) {
			if(visit[sav + k*h]==0 && dkb(sav + k*h)) {
				visit[sav + k*h]=i+1;
				timet[sav+ k*h] = abs(k*h) + 1;
				nguoi --;
			}
			if(k == -1) k = 1;
			else k = -1;
			if(k == -1 && con[i] == 0) h ++;
			else if(k == 1 && con[i] == 1) h++;
		}
	}
}

void tapcon(int ket) {
	if(ket == 3) {
		reset();
		cost();
		if(kq > sumt()) kq = sumt();
		//for(int i = 0; i < 3; i ++) cout << con[i] << " ";
		//cout << endl;
		//for(int i = 0; i < n; i ++) cout << visit[i] << " ";
		//cout << endl;
		//cout << kq << endl;
		return;
	}
	for(int i = 0; i < 2; i ++) {
		con[ket] = i;
		tapcon(ket+1);
		con[ket] = 0;
	}
	
}

void hoanvi(int ket) {
	if(ket == 3) {
		for(int i = 0; i < 3; i++) {
			int j = xep[i];
			as[i][0] = ad[j][0];
			as[i][1] = ad[j][1];
		}
		//for(int i = 0; i < 3; i ++) cout << xep[i] << " ";
		//cout << endl << endl;
		tapcon(0);
		return;
	}
	for(int i = 0; i < 3; i++) {
		if(visit_hv[i] == 0) {
			visit_hv[i] = 1;
			xep[ket] = i;
			hoanvi(ket+1);
			visit_hv[i] = 0;
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (int stt = 1; stt <= T; stt++) {  
		people = 0;
		cin >> n;
		for(int i = 0; i < 3; i ++) {
			cin >> ad[i][0] >> ad[i][1];
			people += ad[i][1];
			visit_hv[i] = 0;
			con[i] = 0;
		}
		kq = 100000;
		reset();
		hoanvi(0);
		//con[0] = 0; con[1] = 1; con[2] = 0;
		//as[0][0] = ad[0][0]; as[0][1] = ad[0][1];
		//as[1][0] = ad[2][0]; as[1][1] = ad[2][1];
		//as[2][0] = ad[1][0]; as[2][1] = ad[1][1];
		//
		//cost();
		//for(int i = 0; i < n; i ++) cout << timet[i] << " ";
		//cout << endl;
		//for(int i = 0; i < n; i ++) cout << visit[i] << " ";
		cout << "Case #" << stt << endl << kq << endl;
	}
	return 0;
}