BOI 2023 - Ngày 1

Nhà thiên văn học rất đam mê ngắm sao. Đặc biệt, ông vô cùng thích thú khi được ngắm đồng thời \(k\) ngôi sao qua kính thiên văn của mình. Chế tạo một kính thiên văn có bán kính \(r\) tốn \(t\cdot r\) krone. Khi vừa được chế tạo, kính thiên văn hướng đúng vào gốc tọa độ \((0,0)\). Việc chuyển kính sang hướng khác cũng tốn công sức: dịch chuyển điểm mà kính hướng tới một khoảng cách \(d\) tốn \(s\cdot d\) krone. Nhà thiên văn học có thể quan sát tất cả các ngôi sao cách điểm mà kính hướng tới không quá \(r\).

Chi phí nhỏ nhất để chế tạo và di chuyển kính thiên văn sao cho có thể quan sát đồng thời \(k\) ngôi sao là bao nhiêu?

Tất cả tọa độ và khoảng cách đều được xét trong mặt phẳng Euclid.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(k\), \(n\), \(s\), \(t\): số ngôi sao nhà thiên văn học muốn quan sát, số ngôi sao trên bầu trời đêm nay, chi phí dịch chuyển và chi phí chế tạo kính thiên văn.

\(n\) dòng tiếp theo mô tả các ngôi sao. Dòng thứ \(i\) chứa hai tọa độ nguyên \(x_i\) và \(y_i\) của ngôi sao thứ \(i\).

Dữ liệu ra

In một số thực: số krone ít nhất mà nhà thiên văn học cần chi trả.

Kết quả được chấp nhận nếu sai số tương đối hoặc sai số tuyệt đối so với đáp án đúng không vượt quá \(\epsilon=10^{-6}\), ngoại trừ phân nhóm 6 được nêu bên dưới.

Ràng buộc

• \(1\le k\le n\le 700\).
• \(x_i,y_i\in\{-10^9,\ldots,10^9\}\) với mọi \(i\in\{1,\ldots,n\}\).
• \(s,t\in\{0,\ldots,10^9\}\).

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. \(8\) điểm: \(t\le s\).
2. \(9\) điểm: \(n\le 50\) và \(s=0\).
3. \(18\) điểm: \(s=0\).
4. \(13\) điểm: \(n\le 50\).
5. \(14\) điểm: \(n\le 350\).
6. \(15\) điểm: ngưỡng sai số tương đối hoặc tuyệt đối là \(\epsilon=1/10\).
7. \(23\) điểm: không có ràng buộc bổ sung.

Ví dụ

2 3 1000 500
0 0
2 0
3 1

1000.0

2 3 500 3000
0 0
2 0
3 1

3387.277541898787

2 3 250 750
0 0
2 0
3 1

1000.0

2 3 0 500
0 0
2 0
3 1

353.55339059327395

3 4 0 10
0 0
10 0
5 10
5 5

50.0

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}}

Một dãy số nguyên dương \((x_1,\ldots,x_m)\) được gọi là tốt nếu \(x_1=1\) và với mỗi \(1<j\le m\), ta có \(x_j=x_{j-1}+1\) hoặc \(x_j=x_k\cdot x_l\) với một cặp chỉ số \(k,l\) nào đó thỏa mãn \(0<k\le l<j\).

Chẳng hạn, cả hai dãy \((1,1)\) và \((1,2)\) đều tốt, nhưng dãy \((1,3)\) không tốt.

Cho \(n\) số nguyên \(w_1,\ldots,w_n\). Trọng số của một dãy số nguyên \((x_1,\ldots,x_m)\) thỏa mãn \(1\le x_j\le n\) với mọi \(1\le j\le m\) được định nghĩa là

Chẳng hạn, với các trọng số \(w_1=10\), \(w_2=42\), \(w_3=1\), trọng số của dãy \((1,1)\) là \(20\) và trọng số của dãy \((1,3)\) là \(11\).

Với \(1\le v\le n\), gọi \(s_v\) là trọng số nhỏ nhất có thể của một dãy tốt chứa giá trị \(v\).

Nhiệm vụ của bạn là xác định các giá trị \(s_1,\ldots,s_n\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số lượng trọng số.

\(n\) dòng tiếp theo lần lượt chứa các trọng số nguyên \(w_1,\ldots,w_n\), mỗi dòng một số.

Dữ liệu ra

In \(n\) dòng lần lượt chứa \(s_1,\ldots,s_n\).

Ràng buộc

• \(1\le n\le 30\,000\).
• \(1\le w_i\le 10^6\) với mọi \(1\le i\le 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. \(11\) điểm: \(n\le 10\).
2. \(10\) điểm: \(n\le 300\) và \(w_1=\cdots=w_n=1\).
3. \(10\) điểm: \(n\le 300\) và \(w_1=\cdots=w_n\).
4. \(9\) điểm: \(n\le 1400\) và \(w_1=\cdots=w_n=1\).
5. \(45\) điểm: \(n\le 5000\).
6. \(15\) điểm: không có ràng buộc bổ sung.

Ví dụ

3
10
42
1

10
52
53