题目描述

You are playing Zombie Smash: a game where the objective is to smash zombies with your trusty Zombie Smasher as they pop out of graves at the graveyard. The graveyard is represented by a flat 2D grid. Each zombie will pop out of a grave at some $(X, Y)$ cell on the grid, stand in place for 1000 milliseconds (ms), and then disappear back into the grave. At most one zombie can stand around a grave at a time.

You can move to any one of the 8 cells adjacent to your location in 100ms; i.e., you can move North, East, South, West, NW, NE, SW, and SE of your current location. You may move through or stand on a cell even if it is currently occupied by a zombie. You can smash a zombie instantly once you reach the cell that the zombie is standing on, but once you smash a zombie it takes 750ms for your Zombie Smasher to recharge before you can smash another zombie. You may move around while Zombie Smasher is recharging. For example, immediately after smashing a zombie at $(0, 0)$:

• It will take 750ms to reach and smash a zombie at $(1, 1)$ or
• 2000ms to reach and smash a zombie at $(20, 20)$.

You start at cell $(0, 0)$ at the beginning of the game (time=0). After you play a level you would like to know how many zombies you could have smashed, if you had played optimally.

输入格式

The first line will contain a single integer $T$, the number of test cases. It is followed by $T$ test cases, each starting with a line containing a single integer $Z$, the number of zombies in the level.

The next $Z$ lines contain 3 space-separated integers each, representing the location and time at which a given zombie will appear and disappear. The $i^{th}$ line will contain the integers $X_i$, $Y_i$ and $M_i$, where:

• $X_i$ is the X coordinate of the cell at which zombie $i$ appears,
• $Y_i$ is the Y coordinate of the cell at which zombie $i$ appears,
• $M_i$ is the time at which zombie $i$ appears, in milliseconds after the beginning of the game. The time interval during which the zombie can smashed is inclusive: if you reach the cell at any time in the range $[M_i, M_i + 1000]$ with a charged Zombie Smasher, you can smash the zombie in that cell.

输出格式

For each test case, output one line containing "Case #$c$: $d$", where $c$ is the case number (starting from 1), and $d$ is the maximum number of zombies you could have smashed in this level.

3
4
1 0 0
-1 0 0
10 10 1000
10 -10 1000
3
1 1 0
2 2 0
3 3 0
5
10 10 1000
-10 10 1000
10 -10 1000
-10 -10 1000
20 20 2000

Case #1: 3
Case #2: 2
Case #3: 2

提示

Limits

• $1 \leq T \leq 100.$
• $-1000 \leq X_i, Y_i \leq 1000.$
• $0 \leq M_i \leq 100000000 = 10^8.$
• Two zombies will never be in the same location at the same time. In other words, if one zombie appears at $(x, y)$ at time $t$, then any other zombie that appears at $(x, y)$ must appear at or before $(t - 1001)$, or at or after $(t + 1001)$.

Test set 1 (7 Pts, Visible Verdict)

• $1 \leq Z \leq 8.$

Test set 2 (18 Pts, Hidden Verdict)

• $1 \leq Z \leq 100.$