Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
9.4 kB
1
Indexable
Never
#include<iostream>

using namespace std;

int N;
int cua[3][2]; // 0: vitri cua,, 1: so nguoi truoc cua
int visit[61];
int visit_cua[3];
int ans;

int distance_left(int vitricong){
	for (int i = vitricong; i > 0; i--){
		if(visit[i] == 0)
			return vitricong - i;
	}
	return 1000000;
}

int distance_right(int vitricong){
	for (int i = vitricong; i <= N; i++){
		if(visit[i] == 0)
			return i - vitricong;
	}
	return 1000000;
}

void Backtrack(int sum){


	if(visit_cua[1] == 1 && visit_cua[2] == 1 && visit_cua[0] == 1){
		if(ans > sum)
			ans = sum;
		return;
	}


	for (int i = 0; i < 3; i++){
		if(visit_cua[i] == 0){
			visit_cua[i] = 1;
			int sum_dis = 0;

			// xet n-1 nguoi
			for (int j = 0; j < cua[i][1] - 1; j++){
				
				int left = distance_left(cua[i][0]);
				int right = distance_right(cua[i][0]);
				if(left > right){
					visit[cua[i][0]+right] = i+1;
					sum_dis += right+1;
				}
				else{
					visit[cua[i][0]-left] = i+1;
					sum_dis += left+1;
				}
			}


			//xet nguoi cuoi cung
			int left = distance_left(cua[i][0]);
			int right = distance_right(cua[i][0]);
			if(left != right){
				if(left > right){
					visit[cua[i][0]+right] = i+1;
					sum_dis += right+1;
				}
				else{
					visit[cua[i][0] - left] = i+1;
					sum_dis += left+1;
				}
				Backtrack(sum + sum_dis);


			}
			else {
				for (int i = 0; i < 2; i++){
					if(i == 0){ // chay trai
						visit[cua[i][0] - left] = i+1;
						sum_dis += left + 1;
						Backtrack(sum+sum_dis);
						visit[cua[i][0] - left] = 0;
						sum_dis -= (left+1);
					}
					if(i == 1){ // chay phai
						visit[cua[i][0] + right] = i+1;
						sum_dis += right +1;
						Backtrack(sum+sum_dis);
						visit[cua[i][0] + right] = 0;
						sum_dis -= (right +1);
					}
				}
			}
			visit_cua[i] = 0;
			for (int k = 1; k <= N; k++){
				if(visit[k] == i+1)
					visit[k] = 0;
			}
		}
	}
}

int main(){
	freopen("input.txt","r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++){
		cin >> N;
		//reset all
		for (int i = 0; i <= N; i++){
			visit[i] = 0;
		}
		for (int i = 0; i < 3; i++){
			visit_cua[i] = 0;
		}
		//input
		for (int i = 0; i < 3; i++){
			cin >> cua[i][0] >> cua[i][1];
		}
		ans = 100000;
		Backtrack(0);
		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
}

//#include <iostream>
//
//using namespace std;
//
//// có 3 cổng. sắp xếp số người của mỗi cổng sao cho khoảng cách số người của cổng đó cách cổng đó ít nhất.
//
///* hướng giải bài toán : nếu bên trái còn vị trí gần hơn thì đẩy hết vào trái, bên phải còn vị trí gần hơn thì đẩy bên phải.Để lại người cuối cùng để check
//// xem: nếu mà khoảng cách từ cổng đó đến bên trái gần hơn thì ném vào trái, nếu khoảng cách từ cổng đó đến bên phải gần hơn thì ném vào bên phải. Nếu khoảng cách
//từ vị trí đó đến 2 bên trái phải bằng nhau thì ta phải thử đặt cả vào bên trái hoặc phái.
//Lưu ý: cứ đặt hết số người vào vị trí trái hoặc phải gần cổng đó nhát. chỉ để lại 1 người cuối cùng để backtrack, điều này sẽ tránh time limit và dễ dàng hơn.
//*/
//int n;
//
//// mảng spots lưu trạng thái vị trí đã có người ngồi hay chưa và nếu có người rồi thì vị trí đó lưu người của cổng số mấy ngồi 
//// -1 không có người ngồi
//// x  là người cổng bao nhiêu ngồi.
//
//int spots[100];
//
//// lưu trạng thái các cổng đã duyệt hay chưa
//bool visited[3];
//
//// mảng 2 chiều trả về số người sau cổng đó là bao nhiêu.
//int gates[3][2];
//
//// lưu kết quả
//int answer;
//
//// hàm kiểm tra xem cổng đó đã mở để người vào hết hay chưa.
//// true ~ là mở
//// false ~ chưa mở
//bool isOpened()
//{
//	for (int i = 0; i < 3; i++)
//	{
//		if (!visited[i]) return false;
//	}
//	return true;
//}
//
//// khoảng cách từ cổng đó đến vị trí bên phải còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
//int distanceToRightSpot(int start)
//{
//	for (int i = start; i <= n; i++)
//	{
//		if (spots[i] == -1) return i - start;
//	}
//	return 100000;
//}
//
//// khoảng cách từ cổng đó đến vị trí bên trái còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
//int distanceToLeftSpot(int start)
//{
//	for (int i = start; i >= 1; i--)
//	{
//		if (spots[i] == -1) return start - i;
//	}
//	return 100000;
//}
//
//void backtrack(int sum)
//{
//	// kiểm tra xem cổng đã mở hết chưa, nếu đã mở hết thì return giá trị.
//	if (isOpened())
//	{
//		if (sum < answer)answer = sum;
//		return;
//	}
//
//	for (int i = 0; i < 3; i++)
//	{
//		// nếu cổng đã được mở thì ta bỏ qua.
//		if (visited[i]) continue;
//
//		// nếu chưa mở thì ta thăm cổng đó và đánh dấu cổng đó đã thăm.
//		visited[i] = true;
//
//		// lưu khoảng cách tạm = số người tại cổng đó. vì khi người tại cổng X có vị trí là 3 đặt vào ô thứ 3 còn trống thì biến đếm tại ô thứ 3 là 1. ở 2 hàm
//		// check trái và phải thì mình chỉ check nó là 0 nên biến add cần được cộng thêm. tý cậu đọc 2 hàm check trái vs check phải là biết. nếu cậu bỏ cái add này
//		// đi và chạy thử kết quả nó sẽ tường minh hơn.
//		int add = gates[i][1];
//
//		// ta xếp hết người tại cổng đó vào vị trí. chỉ để lại 1 người cuối cùng để check.
//		for (int j = 0; j < gates[i][1] - 1; j++)
//		{
//			int left = distanceToLeftSpot(gates[i][0]); // khoảng cách cổng đó đến trái.
//			int right = distanceToRightSpot(gates[i][0]); // khoảng cách cổng đó đến phải.
//			// nếu trái nhỏ hơn phải thì thêm vào trái, nếu không thì thêm vào phải.
//			if (left < right)
//			{
//				spots[gates[i][0] - left] = i;
//				add += left;
//			}
//			else
//			{
//				spots[gates[i][0] + right] = i;
//				add += right;
//			}
//		}
//
//		//trả về khoảng cách người cuối cùng của cổng đó so với bên trái và phải. 
//		int left = distanceToLeftSpot(gates[i][0]);
//		int right = distanceToRightSpot(gates[i][0]);
//		// nếu khoảng cách đó khách nhau thì ta check xem trái nhỏ hơn hay phải nhỏ hơn để thêm vào.
//		if (left != right)
//		{
//			if (left < right)
//			{
//				spots[gates[i][0] - left] = i;
//				add += left;
//			}
//			else
//			{
//				spots[gates[i][0] + right] = i;
//				add += right;
//			}
//			backtrack(sum + add);
//		}
//		// nếu khoảng cách bằng nhau thì ta cần phải đặt thử cả 2 bên trái và bên phải. 
//		else
//		{
//			add += left;
//			spots[gates[i][0] + right] = i;
//			backtrack(sum + add);
//			spots[gates[i][0] + right] = -1;
//
//			spots[gates[i][0] - left] = i;
//			backtrack(sum + add);
//			spots[gates[i][0] - left] = -1;
//		}
//
//		// trả lại cổng chưa thăm để backtrack lại
//		visited[i] = false;
//
//		// trả lại những vị trí cổng đó đã ngồi.
//		for (int j = 1; j <= n; j++)
//		{
//			if (spots[j] == i) spots[j] = -1;
//		}
//
//	}
//
//}
//
//void readInput()
//{
//	cin >> n;
//	for (int i = 0; i < 3; i++)
//	{
//		cin >> gates[i][0] >> gates[i][1];
//	}
//}
//
//int main()
//{
//	int tcs;
//	cin >> tcs;
//
//	// reset toàn bộ mảng để đến test case sau
//	for (int i = 0; i < 100; i++) spots[i] = -1;
//	for (int i = 0; i < 3; i++) visited[i] = false;
//
//	for (int tc = 1; tc <= tcs; tc++)
//	{
//		readInput();
//		answer = 10000;
//		backtrack(0);
//		cout << "Case #" << tc << endl << answer << endl;
//
//	}
//	return 0;
//}

//input
50
10
4 5
6 2
10 2
10
8 5
9 1
10 2
24
15 3
20 4
23 7
39
17 8
30 5
31 9
60
57 12
31 19
38 16
10
2 2
8 3
5 2
10
9 3
3 3
5 2
10
8 8
2 1
6 1
10
2 2
5 2
3 2
10
2 2
5 2
4 2
20
12 5
19 6
10 2
20
16 4
15 3
4 4
20
14 2
5 6
2 5
20
8 4
5 4
3 2
20
4 5
2 5
10 6
20
11 5
3 5
9 3
20
5 4
9 3
7 4
20
11 4
7 3
2 4
20
4 1
5 3
15 5
20
17 1
12 4
9 3
30
14 9
18 3
29 10
30
12 10
4 9
6 5
30
1 4
28 7
27 2
30
6 1
15 10
23 8
30
4 7
28 1
13 2
30
7 6
6 5
18 2
30
23 2
21 5
11 7
30
11 8
28 8
12 8
30
18 10
4 10
6 9
30
12 7
19 7
3 1
40
14 1
9 4
21 5
40
11 11
40 8
25 10
40
36 11
2 12
3 17
40
15 2
21 9
37 20
40
29 3
5 2
2 11
40
19 6
21 13
29 11
40
14 11
9 4
4 11
40
18 10
14 12
35 8
40
12 10
1 6
10 10
40
24 8
25 6
9 1
50
3 6
46 8
36 12
50
38 9
15 1
4 3
50
19 15
31 2
47 6
50
49 9
10 7
8 11
50
43 15
39 10
30 7
60
12 17
16 12
29 3
60
55 20
33 20
16 20
60
27 10
36 3
54 5
60
37 20
42 20
19 20
60
60 13
18 10
37 16

//