Жадібні алгоритми
Обнаружение молекул
Петр работает в компании, которая создала прибор для обнаружения молекул. Каждая молекула имеет целый положительный вес. Прибор характеризуется интервалом обнаружения [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