#P12996. [GCJ 2022 #2] I, O Bot

    ID: 12795 Type: RemoteJudge 40000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>动态规划 DP2022Google Code Jam

[GCJ 2022 #2] I, O Bot

题目描述

To welcome attendees to a developers' conference on Jupiter's moon of Io, the organizers inflated many giant beach balls. Each ball is in roughly the shape of either a 1 or a 0, since those look sort of like the letters I and O. The conference just ended, and so now the beach balls need to be cleaned up. Luckily, the beach ball cleanup robot, BALL-E, is on the job!

The conference was held on an infinite horizontal line, with station 0 in the middle, stations 1, 2, … to the right, and stations 1,2,-1, -2, \ldots to the left. Station 0 contains the conference's only beach ball storage warehouse. Each other station contains at most one beach ball.

BALL-E has two storage compartments, each of which can hold a single beach ball. One compartment can only hold 1-shaped balls and the other can only hold 0-shaped balls. (The 1-shaped balls are more oblong than the 0-shaped balls, so neither shape of ball will fit in the other shape's compartment.)

BALL-E initially has both the 0 and 1 compartments empty, and it starts off at station 0. The robot can do the following things:

  • Move left one station or right one station. This costs 1 unit of power.
  • If there is a ball at the current station, and BALL-E is not already storing a ball of that shape, it can put the ball in the appropriate compartment. This takes 0 units of power.
  • If there is a ball at the current station, BALL-E can compress it so that its shape becomes the other shape. That is, a 1-shaped ball becomes a 0-shaped ball, or vice versa. It takes C\mathbf{C} units of power to do this. Note that BALL-E may not change the shape of a ball that it has already put into one of its compartments.
  • If BALL-E is at station 0 and is storing at least one ball, it can deposit all balls from its compartment(s) into the beach ball storage warehouse. This takes 0 units of power and leaves both compartments empty.

Notice that if BALL-E moves to a station and there is a ball there, BALL-E is not required to pick it up immediately, even if the robot has an open compartment for it. Also, if BALL-E moves to the station with the warehouse, it is not required to deposit any balls it has.

Find the minimum number of units of power needed for BALL-E to transfer all of the balls to the warehouse, using only the moves described above.

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow.

The first line of each test case contains two integers, N\mathbf{N} and C\mathbf{C}: the number of balls and the amount of power units needed to change the shape of a ball, respectively.

The next N\mathbf{N} lines describe the positions (i.e., station numbers) and the shapes of the balls. The ii-th line contains two integers, Xi\mathbf{X}_{\mathbf{i}} and Si\mathbf{S}_{\mathbf{i}}: the position and the shape of the ii-th ball, respectively.

输出格式

For each test case, output one line containing case # xx: yy, where xx is the test case number (starting from 1) and yy is the minimum number of units of power needed to transfer all of the balls to the warehouse, as described above.

4
5 0
3 0
6 0
8 0
10 1
15 1
5 10
3 0
6 0
8 0
10 1
15 1
5 1
3 0
6 0
8 0
10 1
15 1
2 0
1000000000 0
-1000000000 1
Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000

提示

Sample Explanation

In Sample Case #1 (illustrated in the statement), there are N=5\mathbf{N} = 5 balls and C=0\mathbf{C} = 0. One optimal strategy is to make three round trips from (and back to) the warehouse:

  • First round trip: Move to station 3, pick up the 0 ball there and store it in the 0 compartment, move back to station 0, and deposit the ball in the warehouse. This takes 6 units of power.
  • Second round trip: Move to station 8, pick up the 0 ball there, and store it in the 0 compartment. Move to station 6, change the 0 ball there into a 1 ball, and pick it up and store it in the 1 compartment. Move to station 0 and deposit both balls in the warehouse. This takes 16 units of power. (Recall that in this case, it takes 0 units of power to change a ball's shape.)
  • Third round trip: Move to station 10. Change the 1 ball there into a 0 ball, and pick it up and store it in the 0 compartment. Move to station 15. Pick up the 1 ball there and store it in the 1 compartment. Move to station 0 and deposit both balls in the warehouse. This takes 30 units of power.

The total number of units of power needed to collect all the balls is 52.

Sample Case #2 is like Sample Case #1, but now with C=10\mathbf{C} = 10. Now BALL-E has to use at least 56 units of power:

  • First round trip: Get the ball from station 3. This takes 6 units of power.
  • Second round trip: Get the differently-shaped balls from stations 6 and 10. (These are a 0 and a 1, respectively, so there is no need to change the shape of either of them.) This takes 20 units of power.
  • Third round trip: Get the differently-shaped balls from stations 8 and 15. This takes 30 units of power.

Sample Case #3 is also like Sample Case #1, but now with C=1\mathbf{C} = 1. Here, BALL-E needs at least 54 units of power:

  • First round trip: Get the ball from station 3. This takes 6 units of power.
  • Second round trip: Get the ball from station 8. When passing through station 6 on the way back, change the shape of the ball there and get it. This takes 17 units of power.
  • Third round trip: Do the same with the balls at stations 15 and 10. This takes 31 units of power.

In Sample Case #4, one optimal strategy is for BALL-E to move to station 1000000000-1000000000, get the 1 ball there, move to station 10000000001000000000, get the 0 ball there, and then return to station 0 to deposit both of them.

Limits

  • 1T1001 \leq \mathbf{T} \leq 100.
  • 0Si10 \leq \mathbf{S}_{\mathbf{i}} \leq 1, for all ii.
  • 109Xi109-10^{9} \leq \mathbf{X}_{\mathbf{i}} \leq 10^{9}, for all ii.
  • 0C1090 \leq \mathbf{C} \leq 10^{9}.
  • Xi0\mathbf{X}_{\mathbf{i}} \neq 0, for all ii.
  • All Xi\mathbf{X}_{\mathbf{i}} are distinct.

Test Set 1 (11 Pts, Visible Verdict)

For at most 15 cases:

  • 1N50001 \leq \mathbf{N} \leq 5000.

For the remaining cases:

  • 1N1001 \leq \mathbf{N} \leq 100.

Test Set 2 (20 Pts, Hidden Verdict)

For at most 15 cases:

  • 1N1051 \leq \mathbf{N} \leq 10^{5}.

For the remaining cases:

  • 1N50001 \leq \mathbf{N} \leq 5000.