MOLE - Whac-a-Mole
While visiting a traveling fun fair you
suddenly have an urge to break the high
score in the Whac-a-Mole game. The goal
of the Whac-a-Mole game is to... well...
whack moles. With a hammer. To make
the job easier you have first consulted
the fortune teller and now you know the
exact appearance patterns of the moles.
The moles appear out of holes occupying the n2 integer points (x, y)
satisfying 0 ≤ x, y
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.
For each test case output a single line containing a single integer, the maximum
possible score achievable.
Output
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:
2017-12-14 17:41:34
I got WA, help
|
|
:D:
2010-03-03 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:
2009-11-01 04:40:02
Does the start position of the hammer(x1,y1) also have to have integer co-ordinates or can it have real co-ordinates?
|
|
:D:
2009-07-24 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: | 2007-04-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |