Фонари Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вдоль прямой улицы на равном расстоянии располагаются № домов. Будем считать расстояние между домами за единицу длины. Около каждого дома можно поставить один фонарь. Всего имеется А фонарей, которые могут освещать дома на расстоянии Х (включительно), и В фонарей, которые могут освещать дома на расстоянии У (включительно). В частности, при Х 0 или У 0 такой фонарь освещает только тот дом, у которого он установлен. Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно. Формат входных данных Первая строка входных данных содержит целое число № (1 ≤ N ≤ 105). Следующие четыре строки содержат целые неотрицательные числа А, Х, В и У соответственно, которые не превосходят 105. Формат выходных данных Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел - координату фонаря и расстояние, которое он освещает (то есть одно из чисел Х или У). Координаты представляют из себя целые числа от 1 до №, рядом с каждым домом можно поставить только один фонарь. При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа дллжна вывести одно число -1. Система оценки Решения, правильно работающие при А 0 или В = 0, будут оцениваться в 30 баллов. Решения, правильно работающие при А ≠ 0, В ≠ 0, n ≤ 1000, будут оцениваться в 40 баллов. Замечание В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 также дома 3, 4, 6 и 7, а фонарь у дома 9 также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно. Ввод 10 3 1 1 2 — 10 1 1 1 2 Вывод 2 1 5 2 9 1 — -1

Чтобы решить эту задачу, давайте разработаем стратегию расстановки фонарей для освещения всех домов на улице. Мы будем использовать жадный алгоритм, который будет стараться максимально эффективно использовать имеющиеся фонари.

Описание алгоритма:

1. Параметры задачи:

   • N – количество домов.
   • A – количество фонарей с расстоянием X.
   • B – количество фонарей с расстоянием Y.
   • X – максимальное расстояние, которое может освещать фонарь типа A.
   • Y – максимальное расстояние, которое может освещать фонарь типа B.

2. Инициализация:

   • Создадим массив, который будет хранить информацию о том, какие дома уже освещены.

3. Расстановка фонарей:

   • Начнем с того, что будем ставить фонари с самым большим радиусом освещения (Y), так как они эффективнее охватывают большее количество домов.
   • Затем будем использовать фонари с меньшим радиусом (X), если необходимо.

4. Проверка и вывод результата:

   • Если после расстановки всех доступных фонарей все дома освещены, выведем координаты фонарей и их радиусы. Если нет, выведем -1.

Пример кода:

N = int(input().strip())
A = int(input().strip())
X = int(input().strip())
B = int(input().strip())
Y = int(input().strip())

illuminated = [False] * (N + 1)  # Массив для отметки освещенных домов
result = []

# Сначала ставим фонари типа B (с радиусом Y)
for house in range(1, N + 1):
    if not illuminated[house] and B > 0:
        # Ставим фонарь
        result.append((house, Y))
        B -= 1
        for i in range(max(1, house - Y), min(N + 1, house + Y + 1)):
            illuminated[i] = True

# Затем ставим фонари типа A (с радиусом X)
for house in range(1, N + 1):
    if not illuminated[house] and A > 0:
        # Ставим фонарь
        result.append((house, X))
        A -= 1
        for i in range(max(1, house - X), min(N + 1, house + X + 1)):
            illuminated[i] = True

# Проверка, все ли дома освещены
if all(illuminated[1:]):  # Игнорируем индекс 0
    for coord, rad in result:
        print(coord, rad)
else:
    print(-1)

Объяснение кода:

• Мы инициализируем массив illuminated, который будет отслеживать, какие дома освещены.
• Сперва ставим фонари большего радиуса, а затем меньшего, если есть необходимость.
• В конце мы проверяем, все ли дома освещены и выводим результаты или -1.

Используя этот подход, вы сможете справиться с задачей и понять, как организовывать освещение на данной улице. Удачи в учебе!