Bạn phụ trách xử lý tín hiệu cho một công ty khai khoáng ngoài Trái Đất, và tàu của bạn đang tiến đến một tiểu hành tinh. Các lần quét sơ bộ cho thấy có \(k\) mỏ khoáng sản trên tiểu hành tinh, nhưng chưa biết vị trí chính xác của chúng.

Bề mặt tiểu hành tinh có thể được xem như một lưới tọa độ nguyên. Mỗi mỏ khoáng sản nằm tại một vị trí có tọa độ nguyên chưa biết. Mỏ thứ \(i\) có tọa độ \((x_i,y_i)\) thỏa mãn \(-b\le x_i\le b\) và \(-b\le y_i\le b\), với \(b\) là một số nguyên tương ứng với phạm vi quét ban đầu.

Để xác định chính xác vị trí các mỏ khoáng sản, bạn có thể gửi các thiết bị thăm dò xuống bề mặt tiểu hành tinh. Các thiết bị được gửi theo từng đợt, mỗi đợt gồm nhiều thiết bị được gửi cùng lúc.

Giả sử bạn gửi một đợt gồm \(d\) thiết bị đến các tọa độ \((s_j,t_j)\) với \(1\le j\le d\). Khi đến nơi, mỗi thiết bị xác định khoảng cách Manhattan từ vị trí của nó đến từng mỏ trong số \(k\) mỏ khoáng sản và gửi các khoảng cách về tàu. Tất cả các gói dữ liệu đến cùng lúc, nên không thể xác định khoảng cách nào do thiết bị nào gửi về. Vì vậy, đợt thăm dò trả về \(k\cdot d\) khoảng cách nguyên

Bạn cần tìm vị trí các mỏ khoáng sản với số đợt thăm dò ít nhất có thể.

Giao diện lập trình

Bài này sử dụng giao diện hàm C++17. Hãy nộp mã nguồn có #include "mineraldeposits.h" và cài đặt hàm sau; tệp tiêu đề mineraldeposits.h được cung cấp kèm bài:

std::vector<std::pair<long long, long long>> find_deposits(int b, int k, int w);

Bộ chấm gọi find_deposits(b, k, w) đúng một lần cho mỗi bộ kiểm thử. Các tham số lần lượt là giới hạn tọa độ ban đầu \(b\), số mỏ khoáng sản \(k\) và số đợt thăm dò tối đa \(w\). Các vị trí mỏ khoáng sản đôi một khác nhau và đã được cố định trước khi gọi hàm.

Trong khi thực hiện find_deposits, bạn có thể gọi hàm do bộ chấm cung cấp:

std::vector<long long> probe(const std::vector<std::pair<long long, long long>>& points);

Mỗi lần gọi probe(points) gửi một đợt gồm \(d=\texttt{points.size()}\) thiết bị. Mỗi phần tử của points là một cặp tọa độ \((s_j,t_j)\), trong đó first là hoành độ và second là tung độ. Tọa độ và khoảng cách dùng kiểu long long (số nguyên có dấu 64 bit).

• Mỗi đợt phải có \(1\le d\le 2000\) thiết bị tại các vị trí đôi một khác nhau trong đợt đó. Bạn được phép thăm dò lại một vị trí ở đợt sau, kể cả vị trí trùng với một mỏ khoáng sản.
• Mỗi tọa độ thăm dò phải thuộc \([-10^8,10^8]\); không bắt buộc thuộc \([-b,b]\).
• Bạn được gọi probe nhiều nhất \(w\) lần. Tổng số thiết bị trong tất cả các lần gọi không được vượt quá \(2\cdot 10^4\).

Hàm probe trả về một std::vector<long long> gồm đúng \(k\cdot d\) khoảng cách Manhattan, sắp xếp theo thứ tự không giảm. Các khoảng cách trùng nhau vẫn xuất hiện đủ số lần; không có thông tin cho biết khoảng cách nào thuộc về thiết bị hay mỏ nào.

Để kết thúc, find_deposits phải trả về một std::vector<std::pair<long long, long long>> gồm đúng \(k\) vị trí mỏ khoáng sản, mỗi vị trí xuất hiện đúng một lần, theo thứ tự bất kỳ. Trả về đáp án không tính là một đợt thăm dò. Không bắt buộc phải gọi probe nếu bạn đã xác định được đáp án đúng.

Không cài đặt main, không đọc stdin, không ghi stdout và không chèn mã nguồn bộ chấm vào bài nộp. Chỉ gọi probe trong lúc find_deposits đang chạy. Một lời gọi không hợp lệ (kể cả đợt thứ \(w+1\)) làm bộ chấm kết thúc chương trình ngay lập tức và bộ kiểm thử nhận \(0\) điểm; lời gọi đó không trả về giá trị báo lỗi và không ném ngoại lệ để bạn bắt. Nếu hàm trả về sai số lượng hoặc sai vị trí, bộ kiểm thử cũng nhận \(0\) điểm. Sau khi hàm trả về, bộ chấm kiểm tra đáp án rồi kết thúc chương trình; bạn không cần gọi hàm kết thúc nào khác.

Ràng buộc

• \(1\le b\le 10^8\).
• \(1\le k\le 20\).
• \(2\le w\le 10^4\).
• Tọa độ các mỏ khoáng sản và các thiết bị thăm dò là số nguyên; các giới hạn tọa độ, số thiết bị trong mỗi đợt và tổng số thiết bị được nêu ở trên.

Phân nhóm

Các bộ kiểm thử được chia thành các nhóm, mỗi nhóm có một số điểm. Để nhận được điểm của một nhóm, chương trình phải giải đúng tất cả các bộ kiểm thử trong nhóm đó. Điểm cuối cùng là điểm cao nhất của một lần nộp bài.

1. \(9\) điểm: \(k=1\) và \(w=10^4\).
2. \(19\) điểm: \(w\ge 500\).
3. \(11\) điểm: \(w\ge 210\).
4. \(7\) điểm: \(w\ge 130\).
5. \(20\) điểm: \(w\ge 3\) và \(b\le 10^4\).
6. \(15\) điểm: \(w\ge 3\) và \(b\le 10^7\).
7. \(19\) điểm: không có ràng buộc bổ sung.

Ví dụ gọi hàm

Bản ghi dưới đây giữ nguyên các tham số, hai đợt thăm dò, các khoảng cách và đáp án của ví dụ. Bộ chấm gọi: chỉ lời gọi hàm của bạn; Bạn gọi: chỉ lời gọi probe; Bộ chấm trả về: chỉ kết quả của lời gọi đó; Bạn trả về: chỉ giá trị trả về cuối cùng của find_deposits. Dấu ngoặc nhọn biểu diễn các vector và cặp tọa độ theo cú pháp C++; các nhãn chỉ để minh họa, không phải dữ liệu cần đọc hoặc in.

Bộ chấm gọi: find_deposits(4, 2, 10)
Bạn gọi: probe({{-4, -3}, {-1, 0}, {2, -1}})
Bộ chấm trả về: {2, 4, 4, 4, 6, 10}
Bạn gọi: probe({{1, 2}, {0, -2}})
Bộ chấm trả về: {0, 3, 5, 8}
Bạn trả về: {{1, 2}, {-3, -2}}