Có một chiếc tàu nghiên cứu đại dương được giao nhiệm vụ tìm kiếm những kho báu nằm sâu dưới đáy biển. Sau nhiều ngày dò quét bằng hệ thống sonar hiện đại, thủy thủ đoàn cuối cùng cũng xác định được vị trí của một kho báu lớn. Ngay lập tức, thuyền trưởng quyết định cử một tàu ngầm không người lái xuống để thu thập toàn bộ số báu vật này.

Sau khi tiếp cận kho báu, tàu ngầm phát hiện có ~N~ báu vật được đánh số từ ~0~ đến ~N - 1~. Báu vật thứ ~i~ có khối lượng là ~w_i~ và giá trị là ~v_i~.

Tuy nhiên, kho báu nằm ở độ sâu hàng nghìn mét dưới mặt nước. Ở độ sâu này, sóng vô tuyến gần như không thể truyền đi, còn hệ thống liên lạc bằng sóng âm dưới nước chỉ có băng thông rất nhỏ. Nếu gửi trực tiếp toàn bộ dữ liệu về khối lượng và giá trị thì sẽ mất quá nhiều thời gian, thậm chí có thể khiến tàu ngầm cạn kiệt năng lượng trước khi nhận được phản hồi.

Để tiết kiệm băng thông truyền tải, anh ~T~ — người điều khiển tàu ngầm — quyết định mã hóa toàn bộ thông tin về các báu vật thành một xâu nhị phân duy nhất rồi gửi lên tàu mẹ. Sau khi nhận được thông điệp, hệ thống trên tàu mẹ phải giải mã để khôi phục lại dữ liệu và tính toán phương án chọn báu vật tối ưu.

Do sức chứa của tàu ngầm có hạn, tổng khối lượng các báu vật mang về không được vượt quá ~W~. Tàu mẹ cần nhanh chóng gửi ngược lại danh sách chỉ số các báu vật cần lấy sao cho tổng giá trị thu được là lớn nhất có thể trước khi tàu ngầm buộc phải nổi lên vì giới hạn oxy và năng lượng.

Hãy giúp thủy thủ đoàn giải mã thông điệp và xác định những báu vật nên được mang về để tổng giá trị thu được là lớn nhất.

Chi tiết cài đặt

Bạn cần cài đặt hai chương trình độc lập tương ứng với hai quá trình:

1. Quá trình gửi dữ liệu (Mã hóa):

string send(int N, long long w[], int v[]);

• ~N~ là số lượng món báu vật được đánh chỉ số từ ~0~ đến ~N - 1~.
• ~w~ là danh sách khối lượng của các báu vật.
• ~v~ là danh sách giá trị của các báu vật.
• Hàm send phải trả về một xâu nhị phân (chỉ gồm các ký tự '0' và '1').

2. Quá trình nhận và xử lý (Giải mã):

vector<int> take(long long W, tring message);

• ~W~ là trọng lượng tối đa của tàu ngầm.
• message là xâu nhị phân nhận được từ hàm send.
• Hàm take phải trả về danh sách chỉ số các món báu vật cần lấy.

Trình chấm (Grader)

Code của thí sinh phải khai báo thư viện:

#include "treasure.h"

Trình chấm sẽ chạy hàm send trước, sau đó lấy thông điệp truyền vào hàm take để kiểm tra kết quả.

Dữ liệu đầu vào của Grader mẫu:

• Dòng đầu tiên gồm hai số nguyên dương ~N, W~ là số lượng báu vật và trọng lượng tối đa của tàu ngầm.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~w_i, v_i~ là trọng lượng và giá trị của báu vật thứ ~i~ (~0 \le i < N~).

Ràng buộc

• Trong tất cả các test: ~1 \le w_i \le W~, ~1 \le v_i \le 10^9~.
• Subtask 1 (50% số điểm): ~1 \le N \le 100~, ~1 \le W \le 10^5~.
• Subtask 2 (50% số điểm): ~1 \le N \le 40~, ~10^9 \le W \le 10^{18}~.

Cách tính điểm

Nếu thí sinh không nén thành xâu nhị phân, danh sách sai định dạng hoặc lấy tổng khối lượng các món báu vật lớn hơn ~W~ thì nhận được 0 điểm.

Nếu hợp lệ:

• Gọi ~len_P, len_Q~ là độ dài xâu nén của thí sinh và ban tổ chức.
• Gọi ~max_P, max_Q~ là tổng giá trị lớn nhất các món báu vật của thí sinh và ban tổ chức.
• Gọi ~w_{\max} = \max(w_i)~ và ~v_{\max} = \max(v_i)~.

Đặt:

$$K = \min\left(\frac{max_P}{max_Q}, 1\right)$$

$$L = 8 + \lceil N \log_2(w_{\max} + 1) \rceil + \lceil N \log_2(v_{\max} + 1) \rceil$$

$$R = 32 + 96N$$

Điểm nhận được trên mỗi test (trên thang điểm của Subtask đó):

• Nếu ~len_P \le len_Q~: nhận ~\frac{K}{2}~ điểm.
• Nếu ~len_Q < len_P \le L~: nhận ~60\% \times \frac{K}{2}~ điểm.
• Nếu ~L < len_P \le R~: nhận ~30\% \times \frac{K}{2}~ điểm.
• Còn lại: nhận ~15\% \times \frac{K}{2}~ điểm.