Comments 5
UFO just landed and posted this 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] благодаря неравенству в условии.
А если неравенство в условии убрать, неужели быстрого решения не существует?
для тех кому лень читать приведенное решение:
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] благодаря неравенству в условии.
А если неравенство в условии убрать, неужели быстрого решения не существует?
Прибор характеризуется интервалом обнаружения
Жесть… Какой чудак писал это условие?
Задача интересная, решение в теории тоже хорошо расписано. А вот сам код: Все что до сортировки и сама сортировка хорошо, а потом сделано не лучшим образом, можно переработать.
Sign up to leave a comment.
Разбор задачи с Международной олимпиады по информатике IOI 2016