Thành phố Gridtopia là một ma trận các ô vuông, hay “khu phố”, gồm \(R\) hàng và \(C\) cột. Hàng được đánh số từ trên xuống dưới, cột từ trái sang phải, đều bắt đầu từ \(1\). Thành phố có \(S\) đồn cảnh sát. Đồn thứ \(i\) nằm ở hàng \(R_i\), cột \(C_i\), và không ô nào chứa quá một đồn.

Mỗi đồn chỉ có thể tuần tra các ô cách nó không quá \(D_i\) ô theo cả chiều ngang lẫn chiều dọc. Nói chính xác, đồn \(i\) chỉ tuần tra được ô ở hàng \(R'\), cột \(C'\) nếu

Tương đương, đồn \(i\) chỉ tuần tra được các ô trong hình vuông cạnh \(2D_i+1\) có tâm tại đồn ấy.

Là cảnh sát trưởng mới, bạn cần phân công một số ô trong thành phố cho đúng một đồn có khả năng tuần tra chúng. Không phân công ô chứa đồn và ô không có đồn nào tuần tra được; mọi ô khác bắt buộc phải được phân công. Đồng thời, cần chia tải đều nhất có thể. Gọi \(A_i\) là số ô được giao cho đồn \(i\); mục tiêu là tối thiểu hóa hiệu giữa giá trị lớn nhất và nhỏ nhất trong các \(A_i\). Với cách phân công tối ưu, hiệu nhỏ nhất là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số nguyên \(R,C,S\): số hàng, số cột và số đồn. Tiếp theo là \(S\) dòng; dòng thứ \(i\) chứa \(R_i,C_i,D_i\): vị trí đồn thứ \(i\) và tham số phạm vi tuần tra như trên.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là hiệu nhỏ nhất cần tìm.

Ràng buộc

• \(1\le T\le100\).
• \(2\le S\le15\).
• \(1\le R_i\le R\) và \(1\le C_i\le C\) với mọi \(i\).
• Với mọi \(i\ne j\), \(R_i\ne R_j\) hoặc \(C_i\ne C_j\); không hai đồn nào cùng ô.
• \(1\le D_i<\max(R,C)\) với mọi \(i\).

Phân nhóm

Test Set 1 (Visible): \(1\le R,C\le20\).

Test Set 2 (Hidden): \(1\le R,C\le10^9\).

Đ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ụ

2
3 4 2
1 1 1
3 3 2
5 5 2
4 1 2
3 2 2

Case #1: 4
Case #2: 0

@@@@.
!!!@.
!2!@.
1!!@.
!@!@.

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Jurisdiction Restrictions.

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