Жадібні алгоритми
Виявлення молекул
Петро працюєт в компанії, яка створює прилад для виявлення молекул. Кожна молекула має цілу додатнб вагу. Пристрій характеризується інтервалом виявлення [l; u], де l і u цілі додатнічисла. Пристрій може виявити множину молекул тоді і тільки тоді, коли ця множина містить таку підмножину, що сумарна вага молекул в ній належить інтервалу виявлення пристрою.
Більш формально, разглянемо n молекул з вагою w0
, ..., wn-1
. Виявлення вважається успешним, якщо існує множина різних індексів I = {i1
, ..., im
} така що l ≤ wi1
+ .. + wim
≤ u.
В силу особливості роаботи пристрою різниця між l і u гарантовано більша або дорівнює різниці мас між самою важкою і самою легкою молекулами. Більш формально u - l ≥ wmax
- wmin
, де wmax
= max(w0
, ..., wn-1
) і wmin
= min(w0
, ..., wn-1
).
Потрібно написати програму, яка або знаходит будь-яку підмножину молекул з сумарною вагою, що належить інтервалу виявлення пристрою, або визначає, що такогї підмножини не існує.
Вхідні дані
Перший рядок містить три цілих числа: кількість молекул n (1 ≤ n ≤ 200000) і границі інтервалу виявлення l і u (1 ≤ l, u < 231
). Другий рядок містить n ціелих чисел: w0
, ..., wn-1
(1 ≤ wi
< 231
).
Вихідні дані
В першому рядку вивести розмір подмножини m. У другому рядку вивести індекси молекул, які формують будь-яку таку підмножину. Якщо існує декілька правильних відповідей, виведіть будь-яку з них.
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