Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.4 kB
0
Indexable
Never
*** De ***
There are N spots for fishing in the fishing center.
The center has 3 gates, and a number of customers standing before each gate.
 
To avoid disorder, the customers must enter the center follow these rules :
 1. Only one Gate is open at a time, and it will be closed after all customers of that gate entered.
 2. When open a gate, the customers stand before that gate will enter one by one, and go to the closest & empty spot from their position.
	- The distance from a gate to the spot right above it is 1m
	- Whenever a customer goes further one spot (to left or right), it takes additionally 1m further.
	- Ex : The distance from Gate 1 to spot 4 is 1m, and to spot 3, 5 is 2m
 3. If there are 2 two spots that closest to a customer, he can choose any one of them (you should consider this case)
4. After all customers enter the gate, choose the next gate to open and proceed same as above

You should find a way so that the sum of the moving distance of all customers is minimum and print out that sum.
Ex) In above figure :
- The number of fishing spots : 10
- Gate 1 : location is 4, number of waiting customer is 5
- Gate 2 : location is 6, number of waiting customer is 2
- Gate 3 : location is 10, number of waiting customer is 2

Case 1) We open the gate by the order : Gate 1 > Gate 2 > Gate 3
 
 
 
For this case, the sum of moving distance is : 3+2+1+2+3+2+3+2+1 = 19

Case 2) We open the gate by the order : Gate 2 > Gate 1 > Gate 3
When open Gate 3, the 1st customer will go to spot 6, the second one can go to spot 5 or 7
 OR  
Case 2-1)
 
In this case, the sum is : 4+3+2+1+2+1+4+2+1 = 20

Case 2-2)
 
In this case, the sum is : 4+3+2+1+2+1+2+2+1 = 18

[Input]
- The first line given the number of test case T (T <= 50)
- For each test case:
	+ The first line given the number of spots N (10 <= N <= 60)
	+ The next three lines give the information of 3 gates :
		> Gate's position P ( 1 <= P <= N)
		> The number of customers standing before that gate C ( 1 <= C <= 20 )

[Output]
The minimum moving distance of all customers
Case #1
18
Case #2
25
Case #3
57
Case #4
86
Case #5
339

*** input ***
Case #1
18
Case #2
25
Case #3
57
Case #4
86
Case #5
339
Case #6
11
Case #7
13
Case #8
33
Case #9
9
Case #10
9
Case #11
33
Case #12
25
Case #13
42
Case #14
21
Case #15
64
Case #16
31
Case #17
27
Case #18
21
Case #19
18
Case #20
14
Case #21
85
Case #22
150
Case #23
41
Case #24
60
Case #25
23
Case #26
42
Case #27
34
Case #28
104
Case #29
202
Case #30
39
Case #31
20
Case #32
112
Case #33
433
Case #34
227
Case #35
79
Case #36
163
Case #37
155
Case #38
147
Case #39
163
Case #40
62
Case #41
87
Case #42
35
Case #43
89
Case #44
133
Case #45
229
Case #46
235
Case #47
416
Case #48
51
Case #49
604
Case #50
206

*** output ***
Case #1
18
Case #2
25
Case #3
57
Case #4
86
Case #5
339
Case #6
11
Case #7
13
Case #8
33
Case #9
9
Case #10
9
Case #11
33
Case #12
25
Case #13
42
Case #14
21
Case #15
64
Case #16
31
Case #17
27
Case #18
21
Case #19
18
Case #20
14
Case #21
85
Case #22
150
Case #23
41
Case #24
60
Case #25
23
Case #26
42
Case #27
34
Case #28
104
Case #29
202
Case #30
39
Case #31
20
Case #32
112
Case #33
433
Case #34
227
Case #35
79
Case #36
163
Case #37
155
Case #38
147
Case #39
163
Case #40
62
Case #41
87
Case #42
35
Case #43
89
Case #44
133
Case #45
229
Case #46
235
Case #47
416
Case #48
51
Case #49
604
Case #50
206

*** code ***

*** my code ***
#include<iostream>
using namespace std;

int N; // so toa tau
int Gates[5][2];
int spot[65];
int visitGate[5];
int ans;

int distance2Left(int k){
	for (int i = k; i >= 1; i--){
		if (spot[i] == -1) return k - i;
	}
	return 1000000;
}

int distance2Right(int k){
	for (int i = k; i <= N; i++){
		if (spot[i] == -1) return i - k;
	}
	return 1000000;
}

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

void Try(int sum){
	if (isFull()){
		if (ans > sum) ans = sum;
		return;
	}
	for (int g = 1; g <= 3; g++){
		if (visitGate[g] == 1) {
			continue;
		}
		visitGate[g] = 1;
		int add = Gates[g][1];
		// cho G-1 nguoi len tau
		for (int p = 1; p < Gates[g][1]; p++){
			int left = distance2Left(Gates[g][0]);
			int right = distance2Right(Gates[g][0]);
			if (left < right){
				spot[Gates[g][0] - left] = g;
				add += left;
			}
			else {
				spot[Gates[g][0] + right] = g;
				add += right;
			}
		}
		int left = distance2Left(Gates[g][0]);
		int right = distance2Right(Gates[g][0]);
		if (left < right){
			spot[Gates[g][0] - left] = g;
			add += left;
			Try(sum+add);
		}
		else if (right < left){
			spot[Gates[g][0] + right] = g;
			add += right;
			Try(sum+add);
		}
		else {
			add += right;
			// backtrack nguoi cuoi cung
			spot[Gates[g][0] - left] = g;
			Try(sum+add);
			spot[Gates[g][0] - left] = -1;

			spot[Gates[g][0] + right] = g;
			Try(sum+add);
			spot[Gates[g][0] + right] = -1;
		}
			
		// backtrack cong
		visitGate[g] = 0;
		for (int i = 1; i <= N; i++){
			if (spot[i] == g) spot[i] = -1;
		}
	}
}

void reset(){
	ans = 1000000;
	for (int i = 1; i <= N; i++){
		spot[i] = -1;
	}
	for (int i = 1; i <= 3; i++){
		visitGate[i] = 0;
		Gates[i][0] = Gates[i][0] = 0; 
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		cin >> N;
		reset();
		for (int i = 1; i <= 3; i++){
			cin >> Gates[i][0] >> Gates[i][1];
		}

		Try(0);

		cout << "Case #" << tc << endl << ans << endl;
	}
}