12357번 - Zombie Smash (Large) 다국어

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 Ttest 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.

Limits

• 1 ≤ T ≤ 100.
• -1000 ≤ X_i, Y_i ≤ 1000.
• 0 ≤ M_i ≤ 100000000 = 10⁸.
• 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).
• 1 ≤ Z ≤ 100.

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.