hugo_quanlitau

 avatar
duyvan
plain_text
7 months ago
9.4 kB
5
Indexable
Never
//


#include <iostream>
using namespace std;

#define INF 2000000

int T, tc;
int N;
int visit[61][2];
int pos[4];
int cus[4];
int opened[4];
int min_cnt;

void clr_opened(){
	for(int i=1; i<=3; i++){
		opened[i]=0;
	}
}

void clr_visit(){
	for(int i=1; i<=N; i++){
		visit[i][0]=0;
		visit[i][1]=0;
	}
}

void open(int d)
{
	for(int i=0; i<cus[d]; i++)
	{
		int dx=0;
		while(1)
		{
			if(pos[d]+dx>=1 && pos[d]+dx<=N){
				if(visit[pos[d]+dx][0]==0){
					visit[pos[d]+dx][0]=dx+1;
					visit[pos[d]+dx][1]=d;
					break;
				}
			}
			if(pos[d]-dx>=1 && pos[d]-dx<=N){
				if(visit[pos[d]-dx][0]==0){
					visit[pos[d]-dx][0]=dx+1;
					visit[pos[d]-dx][1]=d;
					break;
				}
			}
			dx++;
		}
	}
}

void openL(int d)
{
	for(int i=0; i<cus[d]; i++)
	{
		int dx=0;
		while(1)
		{
			if(pos[d]-dx>=1 && pos[d]-dx<=N){
				if(visit[pos[d]-dx][0]==0){
					visit[pos[d]-dx][0]=dx+1;
					visit[pos[d]-dx][1]=d;
					break;
				}
			}
			if(pos[d]+dx>=1 && pos[d]+dx<=N){
				if(visit[pos[d]+dx][0]==0){
					visit[pos[d]+dx][0]=dx+1;
					visit[pos[d]+dx][1]=d;
					break;
				}
			}
			dx++;
		}
	}
}

void unopen(int d){
	for(int i=1; i<=N; i++){
		if(visit[i][1]==d){
			visit[i][0]=0;
			visit[i][1]=0;
		}
	}
}

void backtrack(int d, int cnt)
{
	for(int l=0; l<2; l++)
	{
		if(l==0)
		{
			//Uu tien phai
			open(d);
			if(cnt==3){
				int sum=0;
				for(int i=1; i<=N; i++){
					sum+=visit[i][0];
				}
				min_cnt = (min_cnt < sum) ? min_cnt : sum;
			}
			for(int i=1; i<=3; i++){
				if(opened[i]==0){
					opened[i]=1;
					backtrack(i, cnt+1);
					opened[i]=0;
				}
			}
			unopen(d);
		}
		if(l==1)
		{
			//Uu tien trai
			openL(d);
			if(cnt==3){
				int sum=0;
				for(int i=1; i<=N; i++){
					sum+=visit[i][0];
				}
				min_cnt = (min_cnt < sum) ? min_cnt : sum;
			}
			for(int i=1; i<=3; i++){
				if(opened[i]==0){
					opened[i]=1;
					backtrack(i, cnt+1);
					opened[i]=0;
				}
			}
			unopen(d);
		}
	}
}

int main()
{
//	freopen("input.txt", "r", stdin);
	cin >> T;
	for(tc=1; tc<=T; tc++)
	{
		cin >> N;
		for(int i=1; i<=3; i++){
			cin >> pos[i];
			cin >> cus[i];
		}
		//Solve
		clr_visit();
		clr_opened();
		min_cnt=INF;
		for(int i=1; i<=3; i++){
			opened[i]=1;
			backtrack(i, 1);
			opened[i]=0;
		}
		cout << "Case #" << tc << endl;
		cout << min_cnt << endl;
	}
	return 0;
}




=============================
Hugo quản lý tàu
Trên một con tàu có N vị trí ngồi, Có 3 cửa để lên tàu. Hành khách đang đợi ở mỗi cửa là khác nhau

 

 

1

2

3

4

5

6

7

8

9

10

Vị trí

 

 

 

 

 

 

 

 

 

 

Khoảng cách

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Để tránh xung đột và rối loạn, hành khách lên tàu cần thực hiện như sau:
1. Chỉ 1 cửa được mở tại một thời điểm, khi cửa mở tất cả hành khách sẽ được lên tàu.

2. Khi cửa mở, lần lượt hành khách sẽ được lên tàu, và hành khách sẽ đi tới vị trí trống gần nhất từ vị trí cửa

+ Khoảng cách từ cửa tới vị trí ngồi đối diện cửa là 1m. (Vị trí ngồi tại vị trí cửa)

+ Khi hành khách đi xa hơn một vị trí (sang trái hoặc sang phải), sẽ mất thêm 1m

Ví dụ: Vị trí cửa là 4, khoảng cách đến vị trí ngồi 4 là 1m, đến vị trí ngồi 3, 5 là 2m

3. Nếu có 2 vị trí ngồi trống gần nhất, hành khách có thể chọn bất kỳ chỗ nào (Bạn cần xem xét trường hợp này).

4. Sau khi 1 cửa được mở và hành khách đã lên tàu hết thì tiếp tục mở cửa tiếp theo cho hành khách lên tàu theo cách bên trên

 

Bạn cần tìm cách để tổng khoảng cách tất cả hành khách di chuyển là nhỏ nhất và viết ra..

Ex) Trong bảng bên dưới :

- Số lượng vị trí ngồi của tàu là : 10

- Cửa 1 : vị trí là 4, Số hành khác đang chờ lên tàu là 5

- Cửa 2 : vị trí là 6, Số hành khách đang chờ lên tàu là 2

- Cửa 3 : vị trí là 10, Số hành khách đang chờ lên tàu là 2

 

Trường hợp 1) Chúng ta mở các cửa theo thứ tự : Cửa 1 > Cửa 2 > Cửa 3

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

Vị trí

 

G1

G1

G1

G1

G1

 

 

 

 

Khoảng cách

 

3

2

1

2

3

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

 

G1

G1

G1

G1

G1

G2

G2

 

 

Khoảng cách

 

3

2

1

2

3

2

3

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

 

G1

G1

G1

G1

G1

G2

G2

G3

G3

Khoảng cách

 

3

2

1

2

3

2

3

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này tổng khoảng cách hành khách di chuyển là : 3+2+1+2+3+2+3+2+1 = 19

 

Trường hợp 2) Chúng ta mở cửa theo thứ tự : Cửa 2 > Cửa 1 > Cửa 3

Khi mở cửa 2, hành khách đầu tiên sẽ chọn vị trí số 6, hành khách thứ 2 có thể chọn vị trí số 5 hoặc 7

 

 

5

6

7

Position

 

G2

G2

Khoảng cách

 

1

2

 

 

Cửa 2

 

 Hoặc

 

5

6

7

Position

G2

G2

 

Khoảng cách

2

1

 

 

 

Cửa 2

 

 

Trường hợp 2-1)

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu (hành khách thứ 2 chọn vị trí số 5)

 

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

G2

G2

 

 

 

 

Khoảng cách

 

 

 

 

2

1

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G2

G2

G1

 

 

 

Khoảng cách

4

3

2

1

2

1

4

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G2

G2

G1

 

G3

G3

Khoảng cách

4

3

2

1

2

1

4

 

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này, tổng là : 4+3+2+1+2+1+4+2+1 = 20

 

Trường hợp 2-2)

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu (hành khách thứ 2 chọn vị trí số 7)

 

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

 

G2

G2

 

 

 

Khoảng cách

 

 

 

 

 

1

2

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G1

G2

G1

 

 

 

Khoảng cách

4

3

2

1

2

1

2

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G1

G2

G1

 

G3

G3

Khoảng cách

4

3

2

1

2

1

2

 

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này, tổng là : 4+3+2+1+2+1+2+2+1 = 18

 

[Đầu vào]

- Dòng đầu tiên chứa số trường hợp thử nghiệm T (T <= 50)

- Mỗi trường hợp thử nghiệm:

          + Dòng đầu tiên chưa số ghế trên tàu N (10 <= N <= 60)

          + 3 dòng tiếp theo chưa thông tin của 3 cửa lên tàu :

                    > Vị trí cửa P ( 1 <= P <= N)

                    > Số lượng hành khách đang chờ ở cửa C ( 1 <= C <= 20 )

 

[Đầu ra]

Tổng di chuyển nhỏ nhất của tất cả các hành khách

Case #1

18

Case #2

25

Case #3

57

Case #4

86

Case #5

339
Leave a Comment