Untitled

#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 << "#" << tc << " " << answer << endl;

	}
	return 0;
}