## Google Code Jam '22 Round 2 Problem D - I, O Bot

View as PDF

Points: 35 (partial)
Time limit: 40.0s
Memory limit: 1G

Problem type

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 or a , 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 in the middle, stations to the right, and stations 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 -shaped balls and the other can only hold -shaped balls. (The -shaped balls are more oblong than the -shaped balls, so neither shape of ball will fit in the other shape's compartment.)

BALL-E initially has both the and compartments empty, and it starts off at station . 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 -shaped ball becomes a -shaped ball, or vice versa. It takes 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.

#### Input Specification

The first line of the input gives the number of test cases, . test cases follow. The first line of each test case contains two integers, and : the number of balls and the amount of power units needed to change the shape of a ball, respectively. The next lines describe the positions (i.e., station numbers) and the shapes of the balls. The -th line contains two integers, and : the position and the shape of the -th ball, respectively.

#### Output Specification

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

#### Limits

Time limit: 40 seconds.

Memory limit: 1 GB.

.

, for all .

, for all .

.

, for all .

All are distinct.

##### Test Set 1

For at most 15 cases:

.

For the remaining cases:

.

##### Test Set 2

For at most 15 cases:

.

For the remaining cases:

.

#### Sample Input

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

#### Sample Output

Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000

In Sample Case #1 (illustrated in the statement), there are balls and . One optimal strategy is to make three round trips from (and back to) the warehouse:

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

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

Sample Case #2 is like Sample Case #1, but now with . Now BALL-E has to use at least units of power:

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

Sample Case #3 is also like Sample Case #1, but now with . Here, BALL-E needs at least units of power:

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

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