Comments 5
UFO landed and left these words here
сами то решили? я тупил пол часа пока не понял зачем в условии неравенство.
для тех кому лень читать приведенное решение:
1. сортируем w[] чтобы получить w[1] <=...<= w[n]
2. для k = 1...N:
сумма элементов любого подмножества размера k принадлежит промежутку AB = [sum(MIN); sum(MAX)] = [сумма первых k элементов w[]; сумма последних k элементов w[]].
Если промежутки AB и [l, u] не пересекаются, то для текущего k решения нет, переходим к следующему
Если AB пересекает [l, u], то решение либо уже найдено (MIN или MAX), либо его легко найти, последовательно заменяя элементы из MIN на элементы из MAX, поскольку при каждой замене нельзя «перескочить» через промежуток [l,u] благодаря неравенству в условии.

А если неравенство в условии убрать, неужели быстрого решения не существует?
Прибор характеризуется интервалом обнаружения

Жесть… Какой чудак писал это условие?
Задача интересная, решение в теории тоже хорошо расписано. А вот сам код: Все что до сортировки и сама сортировка хорошо, а потом сделано не лучшим образом, можно переработать.
Это ж Олимпиада, а там, я так понимаю, время ограничено. Поэтому все верно, какие средства пришли в голову в тот момент автору те и использовал.
Only those users with full accounts are able to leave comments. Log in, please.