# fishing

unknown

plain_text

a year ago

4.0 kB

2

Indexable

Never

^{}

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