eolymp
bolt
Try our new interface for solving problems
Məsələlər

Обнаружение молекул

Обнаружение молекул

Петр работает в компании, которая создала прибор для обнаружения молекул. Каждая молекула имеет целый положительный вес. Прибор характеризуется интервалом обнаружения $[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$. Во второй строке следует вывести индексы молекул, которые формируют любое такое подмножество. Если существует несколько правильных ответов, выведите любой из них.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 15 17
6 8 8 7
Çıxış verilənləri #1
2
2 1 
Giriş verilənləri #2
4 14 15
5 5 6 6
Çıxış verilənləri #2
0

Giriş verilənləri #3
4 10 20
15 17 16 18
Çıxış verilənləri #3
1
3 
Mənbə 2016 IOI Казань, Россия, День 1