Petr làm việc cho một công ty đã chế tạo một chiếc máy phát hiện các phân tử. Mỗi phân tử có trọng lượng là một số nguyên dương. Máy có khoảng phát hiện \([l,u]\), trong đó \(l\) và \(u\) là các số nguyên dương. Máy phát hiện được một tập các phân tử khi và chỉ khi tập đó chứa một tập con có tổng trọng lượng thuộc khoảng phát hiện.

Xét \(n\) phân tử có trọng lượng \(w_0,\ldots,w_{n-1}\). Việc phát hiện thành công nếu tồn tại một tập các chỉ số phân biệt \(I=\{i_1,\ldots,i_m\}\) sao cho

Do đặc thù của máy, độ rộng khoảng phát hiện không nhỏ hơn chênh lệch trọng lượng giữa phân tử nặng nhất và nhẹ nhất:

Hãy tìm một tập con bất kỳ có tổng trọng lượng thuộc khoảng phát hiện, hoặc xác định rằng không tồn tại tập con như vậy.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong molecules.h:

std::vector<int> find_subset(int l, int u, std::vector<int> w);

Trong Java, cài đặt phương thức sau trong lớp molecules:

public int[] find_subset(int l, int u, int[] w)

Trong C, giao diện là:

int find_subset(int l, int u, int* w, int w_len, int* result);

• l, u: hai đầu mút của khoảng phát hiện, đều được tính trong khoảng.
• w: mảng trọng lượng của \(n\) phân tử; trong C, w_len bằng \(n\).
• Với C++ và Java, trả về mảng chỉ số của các phân tử thuộc một tập con thỏa mãn. Nếu không tồn tại, trả về mảng rỗng.
• Với C, ghi \(m\) chỉ số tìm được vào \(m\) phần tử đầu của mảng result được cấp sẵn và trả về \(m\). Nếu không tồn tại, không ghi vào result và trả về \(0\).

Các chỉ số phải đôi một khác nhau, thuộc đoạn \([0,n-1]\), và có thể được trả về theo thứ tự bất kỳ. Nếu có nhiều đáp án đúng, được phép trả về bất kỳ đáp án nào. Nộp phần cài đặt hàm, không viết hàm main; dùng các tệp mẫu tương ứng với ngôn ngữ trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "molecules.h" thay cho #include "molecules_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(1 \le w_i,l,u < 2^{31}\), với \(0 \le i < n\).
• \(l \le u\) và \(u-l \ge w_{\max}-w_{\min}\).

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các ràng buộc chung luôn áp dụng.

Ví dụ

Lời gọi thứ nhất:

find_subset(15, 17, [6, 8, 8, 7])

Ta có \(17-15 \ge 8-6\). Hàm có thể trả về [1, 3] vì \(w_1+w_3=8+7=15\). Các đáp án [1, 2] và [2, 3] cũng đúng, với tổng trọng lượng lần lượt là \(16\) và \(15\).

Lời gọi thứ hai:

find_subset(14, 15, [5, 5, 6, 6])

Ta có \(15-14 \ge 6-5\), nhưng không có tập con nào có tổng trọng lượng thuộc \([14,15]\). Hàm phải trả về mảng rỗng.

Lời gọi thứ ba:

find_subset(10, 20, [15, 17, 16, 18])

Ta có \(20-10 \ge 18-15\). Bất kỳ tập con chỉ chứa một phân tử nào cũng thỏa mãn, nên [0], [1], [2] và [3] đều là đáp án đúng.

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n,l,u\) và dòng tiếp theo chứa \(n\) số \(w_0,\ldots,w_{n-1}\). Chương trình in số lượng chỉ số được trả về trên dòng đầu, rồi in các chỉ số trên dòng tiếp theo nếu số lượng đó khác \(0\).

4 15 17
6 8 8 7

2
2 1

4 14 15
5 5 6 6

0

4 10 20
15 17 16 18

1
3

Nguồn

IOI 2016, ngày thi thứ nhất, bài Detecting Molecules. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.