[Solution] I, O Bot Solution Round 2 2022 - Code Jam 2022

[Solution] I, O Bot Solution Round 2 2022 - Code Jam 2022

Problem

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

Solution Click Below:-  CLICK HERE

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

Spiraling Into Control Solution Round 2 2022

Pixelated Solution Circle Round 2 2022 

Saving the Jelly Solution Round 2 2022

I, O Bot Solution Round 2 2022 

• 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

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
The first line of each test case contains two integers, N$N$ and C$C$: the number of balls and the amount of power units needed to change the shape of a ball, respectively.
The next N$N$ lines describe the positions (i.e., station numbers) and the shapes of the balls. The i$i$-th line contains two integers, Xi${\mathbf{X}}_{\mathbf{i}}$ and Si${\mathbf{S}}_{\mathbf{i}}$: the position and the shape of the i$i$-th ball, respectively.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ 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.
1≤T≤100$1\le \mathbf{T}\le 100$.
0≤Si≤1$0\le {\mathbf{S}}_{\mathbf{i}}\le 1$, for all i$i$.
−109≤Xi≤109$-{10}^9\le {\mathbf{X}}_{\mathbf{i}}\le {10}^9$, for all i$i$.
0≤C≤109$0\le \mathbf{C}\le {10}^9$.
Xi≠0${\mathbf{X}}_{\mathbf{i}}\ne 0$, for all i$i$.
All Xi${\mathbf{X}}_{\mathbf{i}}$ are distinct.

Test Set 1 (Visible Verdict)

For at most 15 cases:
1≤N≤5000$1\le \mathbf{N}\le 5000$.
For the remaining cases:
1≤N≤100$1\le \mathbf{N}\le 100$.

Test Set 2 (Hidden Verdict)

For at most 15 cases:
1≤N≤105$1\le \mathbf{N}\le {10}^5$.
For the remaining cases:
1≤N≤5000$1\le \mathbf{N}\le 5000$.