Bạn đang chơi Zombie Smash: một trò chơi mà mục tiêu là đập những con zombie bằng chiếc Búa Đập Zombie tin cậy khi chúng hiện ra từ các ngôi mộ trong nghĩa địa. Nghĩa địa được biểu diễn bằng một lưới 2D phẳng. Mỗi con zombie sẽ hiện ra từ một ngôi mộ tại một ô \((X, Y)\) trên lưới, đứng yên trong \(1000\) mili giây (ms), sau đó biến mất trở lại vào mộ. Tại một thời điểm, có tối đa một con zombie đứng quanh một ngôi mộ.

Bạn có thể di chuyển đến bất kỳ ô nào trong số 8 ô kề với vị trí hiện tại của mình trong \(100\) ms; tức là bạn có thể di chuyển theo hướng Bắc, Đông, Nam, Tây, Tây Bắc, Đông Bắc, Tây Nam và Đông Nam từ vị trí hiện tại. Bạn có thể đi xuyên qua hoặc đứng trên một ô ngay cả khi nó đang có zombie. Bạn có thể đập một con zombie ngay lập tức khi bạn đến ô mà zombie đó đang đứng, nhưng sau khi đập một con zombie, bạn phải mất \(750\) ms để Búa Đập Zombie sạc lại trước khi có thể đập con zombie tiếp theo. Bạn có thể di chuyển trong khi búa đang sạc. Ví dụ, ngay sau khi đập một con zombie tại \((0, 0)\):

• Sẽ mất \(750\) ms để đến và đập một con zombie tại \((1, 1)\) hoặc
• Mất \(2000\) ms để đến và đập một con zombie tại \((20, 20)\).

Bạn bắt đầu tại ô \((0, 0)\) khi bắt đầu trò chơi (thời điểm \(= 0\)). Sau khi chơi một màn, bạn muốn biết mình có thể đập được tối đa bao nhiêu con zombie nếu chơi một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất T, số lượng bộ thử nghiệm. Tiếp theo là T bộ thử nghiệm, mỗi bộ bắt đầu bằng một dòng chứa một số nguyên duy nhất Z, số lượng zombie trong màn chơi.

Z dòng tiếp theo, mỗi dòng chứa 3 số nguyên cách nhau bởi dấu cách, đại diện cho vị trí và thời điểm mà một con zombie cụ thể sẽ xuất hiện và biến mất. Dòng thứ i sẽ chứa các số nguyên X\(_i\), Y\(_i\) và M\(_i\), trong đó:

• X\(_i\) là tọa độ X của ô mà zombie i xuất hiện,
• Y\(_i\) là tọa độ Y của ô mà zombie i xuất hiện,
• M\(_i\) là thời điểm zombie i xuất hiện, tính bằng mili giây kể từ khi bắt đầu trò chơi. Khoảng thời gian mà zombie có thể bị đập là bao gồm cả hai đầu: nếu bạn đến ô đó tại bất kỳ thời điểm nào trong khoảng [M\(_i\), M\(_i\) + 1000] với chiếc búa đã sạc đầy, bạn có thể đập con zombie ở ô đó.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #c: d", trong đó c là số thứ tự bộ thử nghiệm (bắt đầu từ 1), và d là số lượng zombie tối đa bạn có thể đập được trong màn chơi này.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(-1000 \le \mathbf{X}_i, \mathbf{Y}_i \le 1000\).
• \(0 \le \mathbf{M}_i \le 100000000 = 10^8\).
• Hai con zombie sẽ không bao giờ ở cùng một vị trí tại cùng một thời điểm. Nói cách khác, nếu một con zombie xuất hiện tại \((x, y)\) vào thời điểm \(t\), thì bất kỳ con zombie nào khác xuất hiện tại \((x, y)\) phải xuất hiện vào hoặc trước \((t - 1001)\), hoặc vào hoặc sau \((t + 1001)\).

Phân nhóm

• Tập thử nghiệm 1 (Visible Verdict): \(1 \le \mathbf{Z} \le 8\).
• Tập thử nghiệm 2 (Hidden Verdict): \(1 \le \mathbf{Z} \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Zombie Smash.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.