MOLE  WhacaMole
While visiting a traveling fun fair you suddenly have an urge to break the high score in the WhacaMole game. The goal of the WhacaMole game is to... well... whack moles. With a hammer. To make the job easier you have ﬁrst consulted the fortune teller and now you know the exact appearance patterns of the moles. The moles appear out of holes occupying the n^{2} integer points (x, y) satisfying 0 ≤ x, y <n in a twodimensional coordinate system. At each time step, some moles will appear and then disappear again before the next time step. After the moles appear but before they disappear, you are able to move your hammer in a straight line to any position (x2 , y2 ) that is at ditance at most d from your current position (x1 , y1 ). For simplicity, we assume that yo can only move your hammer to a point having integer coordinates. A mole is whacke if the center of the hole it appears out of is located on the line between (x1 , y1 ) an (x2 , y2 ) (including the two endpoints). Every mole whacked earns you a point. Whe the game starts, before the ﬁrst time step, you are able to place your hammer anywher you see ﬁt.
Input
The input consists of several test cases. Each test case starts with a line containing three integers n, d and m, where n and d are as described above, and m is the total number of moles that will appear (1 ≤ n ≤ 20, 1 ≤ d ≤ 5, and 1 ≤ m ≤ 1000). Then follow m lines, each containing three integers x, y and t giving the position and time of the appearance of a mole (0 ≤ x, y < n and 1 ≤ t ≤ 10). No two moles will appear at the same place at the same time. The input is ended with a test case where n = d = m = 0. This case should not be processed.
Output
For each test case output a single line containing a single integer, the maximum possible score achievable.
Example
Input: 4 2 6 0 0 1 3 1 3 0 1 2 0 2 2 1 0 2 2 0 2 5 4 3 0 0 1 1 2 1 2 4 1 0 0 0 Output: 4 2
hide comments
oscarsierra12:
20171214 17:41:34
I got WA, help


:D:
20100303 07:35:48
It doesn't matter because there always exists an optimal solution starting form a integer coordinates. If You aren't hitting anything in the first time step, it is obvious. If You are wacking some moles in that step, all of them form a line. You might as well start on the coordinates of the first hit mole in that sequence. 

Dhruv M:
20091101 04:40:02
Does the start position of the hammer(x1,y1) also have to have integer coordinates or can it have real coordinates?


:D:
20090724 11:03:16
Remember that positions of the hammer can be outside of the region with holes (coordinates smaller that 0 or not smaller that N) 
Added by:  Abhilash I 
Date:  20070419 
Time limit:  0.297s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 