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

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

Алгоритм:

1. Определим параметры: У нас есть N домов, A фонарей с радиусом X и B фонарей с радиусом Y. Основная задача заключается в том, чтобы минимально использовать имеющиеся фонари для освещения всех домов.

2. Перебор и установка фонарей: Будем проходить по всем домам, начиная с первого. Если дом не освещен, мы должны установить фонарь. Лучше использовать фонарь с большим радиусом, так как он осветит больше домов.

3. Обработка освещения: При установке фонаря в дом i с радиусом R мы освещаем дома в диапазоне от max(1, i - R) до min(N, i + R). После установки фонаря необходимо уменьшить количество доступных фонарей.

4. Проверка: Если на каком-то этапе мы не можем установить фонарь для освещения дома, выводим -1.

5. Вывод результата: Для каждого установленного фонаря мы записываем его местоположение и радиус, затем выводим эти данные.

Пример реализации:

def light_street(N, A, X, B, Y):
    result = []
    lights = [0] * (N + 1)  # массив для отслеживания, какой дом освещен

    for i in range(1, N + 1):
        if lights[i] == 0:  # если дом не освещен
            if A > 0 and (X >= Y or B == 0):
                # Устанавливаем фонарь с радиусом X
                result.append((i, X))
                A -= 1
                for j in range(max(1, i - X), min(N + 1, i + X + 1)):
                    lights[j] = 1
            elif B > 0:
                # Устанавливаем фонарь с радиусом Y
                result.append((i, Y))
                B -= 1
                for j in range(max(1, i - Y), min(N + 1, i + Y + 1)):
                    lights[j] = 1

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

# Пример использования функции
N = int(input().strip())
A = int(input().strip())
X = int(input().strip())
B = int(input().strip())
Y = int(input().strip())
light_street(N, A, X, B, Y)

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

• Мы используем массив lights для отслеживания, какие дома освещены.
• В цикле проходим по каждому дому. Если дом не освещен, выбираем, какой фонарь установить — с радиусом X или Y — в зависимости от доступных фонарей и их радиуса.
• После этого обновляем массив освещения и уменьшаем количество доступных фонарей.
• В конце проверяем, освещены ли все дома. Если все дома освещены, выводим параметры фонарей, иначе выводим -1.

Этот алгоритм будет эффективно работать в пределах заданных ограничений.