Фонари. Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины. Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен. Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно. 2

Для решения этой задачи можно воспользоваться жадным алгоритмом. Начнем с того, что поставим фонари в каждом доме. Затем начнем двигаться по улице и смотреть, можно ли объединить фонари так, чтобы они освещали сразу несколько домов.

Пусть текущий рассматриваемый дом имеет номер i. Если существует фонарь, который может освещать дом с номером i на расстоянии не больше X, то мы можем использовать этот фонарь и не ставить новый. Иначе, если существует фонарь, который может освещать дом с номером i на расстоянии не больше Y, то мы можем использовать этот фонарь и не ставить новый. Если ни один из фонарей не подходит, то мы ставим новый фонарь в текущем доме.

Повторяем этот процесс для каждого дома и в конце получаем минимальное количество фонарей, которые позволят осветить все дома.

Сложность данного алгоритма составляет O(N), где N - количество домов на улице.