eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Виявлення молекул

Виявлення молекул

Петро працюєт в компанії, яка створює прилад для виявлення молекул. Кожна молекула має цілу додатнб вагу. Пристрій характеризується інтервалом виявлення $[l; u]$, де $l$ і $u$ цілі додатні числа. Пристрій може виявити множину молекул тоді і тільки тоді, коли ця множина містить таку підмножину, що сумарна вага молекул в ній належить інтервалу виявлення пристрою. Більш формально, разглянемо $n$ молекул з вагою $w_0, ..., w_{n-1}$. Виявлення вважається успешним, якщо існує множина різних індексів I = {$i_1, ..., i_m$} така що $l ≤ w_{i_1} + .. + w_{i_m} \le u$. В силу особливості роаботи пристрою різниця між $l$ і $u$ гарантовано більша або дорівнює різниці мас між самою важкою і самою легкою молекулами. Більш формально $u - l \ge w_{max} - w_{min}$, де $w_{max} = max(w_0, ..., w_{n-1})$ та $w_{min} = min(w_0, ..., w_{n-1})$. Потрібно написати програму, яка або знаходит будь-яку підмножину молекул з сумарною вагою, що належить інтервалу виявлення пристрою, або визначає, що такогї підмножини не існує. \InputFile Перший рядок містить три цілих числа: кількість молекул $n~(1 \le n \le 200000)$ і границі інтервалу виявлення $l$ і $u~(1 \le l, u < 2^{31})$. Другий рядок містить $n$ ціелих чисел: $w_0, ..., w_{n-1}~(1 \le w_i < 2^{31})$. \OutputFile В першому рядку вивести розмір подмножини $m$. У другому рядку вивести індекси молекул, які формують будь-яку таку підмножину. Якщо існує декілька правильних відповідей, виведіть будь-яку з них.
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 15 17
6 8 8 7
Вихідні дані #1
2
2 1 
Вхідні дані #2
4 14 15
5 5 6 6
Вихідні дані #2
0

Вхідні дані #3
4 10 20
15 17 16 18
Вихідні дані #3
1
3 
Джерело 2016 IOI Казань, Россия, День 1