fishing

 avatar
unknown
plain_text
2 years ago
4.0 kB
10
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


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


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

Editor is loading...