|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|20 초 (추가 시간 없음)||1024 MB||1||1||1||100.000%|
N people from an elementary school — one teacher and N-1 kids — are on a field trip. They are exploring a grassy field that is an infinite two-dimensional grid of unit cells. Each person is currently occupying one of the cells; there may be multiple people in the same cell.
When it is time to go home, the teacher and kids must all gather in one cell; it does not matter which one, since their bus can pick them up anywhere. The kids have been taught an algorithm that makes it easier to gather:
If the teacher makes choices that minimize the number of turns, what is that number of turns?
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with an integer N: the number of people on the field trip. Then, there are N more lines. The i-th of these represents the i-th person, and has two integers Ri and Ci: the row and column numbers (on the grid) of the cell that the i-th person initially occupies.
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 smallest possible number of turns required, as described above.
5 3 3 2 0 2 0 0 3 2 2 2 2 2 2 9 1 1 0 0 0 1 0 2 1 0 1 2 2 0 2 1 2 2 2 8 0 0 8 4 1 0 1 3 2 2 0 2
Case #1: 2 Case #2: 0 Case #3: 1 Case #4: 4 Case #5: 2
In Sample Case #1, the teacher is at (3, 2) — that is, row 3 and column 2. Kid 2 is at (0, 2), and Kid 3 is at (0, 0). One optimal strategy for the teacher is as follows:
In Sample Case #2, the teacher and the two kids start off in the same cell, so no turns are required.
In Sample Case #3, the teacher can remain in place, and all of the kids will move to the teacher's cell by the end of the first turn.
In Sample Case #4, the teacher should move diagonally four times to reach (4, 4).
In Sample Case #5, the teacher should begin by moving to (1, 1); then kids 2, 3, and 4 will all move to (1, 2). Note that even though all the kids are now in the same cell, the teacher is not, and must start another turn. On the second turn, the teacher can move to (1, 2) to join the kids, and the kids will not move.
Contest > Google > Code Jam > Google Code Jam 2018 > Round 3 A번