시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
40 초 (추가 시간 없음) | 1024 MB | 25 | 6 | 6 | 25.000% |
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, \dots$ to the right, and stations $-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$-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:
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, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains two integers, $\mathbf{N}$ and $\mathbf{C}$: the number of balls and the amount of power units needed to change the shape of a ball, respectively. The next $\mathbf{N}$ lines describe the positions (i.e., station numbers) and the shapes of the balls. The $i$-th line contains two integers, $\mathbf{X_i}$ and $\mathbf{S_i}$: the position and the shape of the $i$-th ball, respectively.
For each test case, output one line containing Case #x: y
, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of units of power needed to transfer all of the balls to the warehouse, as described above.
For at most 15 cases:
For the remaining cases:
For at most 15 cases:
For the remaining cases:
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
In Sample Case #1 (illustrated in the statement), there are $\mathbf{N} = 5$ balls and $\mathbf{C} = 0$. One optimal strategy is to make three round trips from (and back to) the warehouse:
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 $\mathbf{C} = 10$. Now BALL-E has to use at least $56$ units of power:
Sample Case #3 is also like Sample Case #1, but now with $\mathbf{C} = 1$. Here, BALL-E needs at least $54$ units of power:
In Sample Case #4, one optimal strategy is for BALL-E to move to station $-1000000000$, get the $1$ ball there, move to station $1000000000$, get the $0$ ball there, and then return to station $0$ to deposit both of them.
Contest > Google > Code Jam > Google Code Jam 2022 > Round 2 D번