Untitled
unknown
plain_text
a year ago
9.5 kB
11
Indexable
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
*** test case
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
*** 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 mau
#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;
}
}