15 ЗАДАЧА и ПРОГРАММИРОВАНИЕ
В этом посте речь про работу с множествами и отрезками. Отрезки в рамках задач из сборников рассматриваются по сути, как множества целых чисел, поэтому данный прием вполне применим для нахождения ответа.
Сразу стоит обозначить, то способ работает на ЕГЭшных задачах, так как мы имеем дело с однозначно определенным множеством и количество целых чисел в отрезке или множестве не уходят в бесконечность.
ПОИСК МИНИМАЛЬНОГО МНОЖЕСТВА
1) В качестве начального множества берем пустое.
2) Если находим элемент, при котором выражение имеет ненужный знак (0 при искомой 1 или наоборот), то добавляем данное значение в множество.
3) Профит, в нашем множестве теперь только нужные элементы.
ПОИСК МАКСИМАЛЬНОГО МНОЖЕСТВА
1) В качестве начального множества берем множество, в котором элементов заведомо больше, чем в заданных.
2) Если находим элемент, при котором выражение имеет ненужный знак (0 при искомой 1 или наоборот), то удаляем данное значение из множества.
3) Вуа-ля, в нашем множестве остались только подходящие элементы.
PS: да, такой способ чувствителен к концам промежутка. Например, когда ищется длина промежутков типа a; b) или (a; b. Подумай, как можно его модернизировать, чтобы учитывать выколотые точки.
