Задача по олимпиаде по информатике Фонари Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины. Около каждого дома…
Задача по олимпиаде по информатике Фонари Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины. Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен. Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.Входные данные Первая строка входных данных содержит целое число N ( 1≤N≤10 5 ). Следующие четыре строки содержат целые неотрицательные числа A , X , B и Y соответственно, которые не превосходят 10 5 . Выходные данные Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел — координату фонаря и расстояние, которое он освещает (то есть одно из чисел 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. В результате все дома освещены. Во втором примере фонарей недостаточно. Примеры
Для решения задачи о расстановке фонарей вдоль улицы, необходимо продумать стратегию, как эффективно использовать доступные фонари для освещения всех домов. Рассмотрим пронумерованные дома от 1 до N, и использовать два типа фонарей — А с радиусом X и B с радиусом Y.
Шаги для решения задачи:
Инициализация: Создайте массив для отслеживания состояния освещения каждого дома, например,
освещено, где каждый дом изначально не освещен.Функция для установки фонарей: Напишите функцию, которая будет принимать параметры: позицию установки фонаря и его радиус. Эта функция должна обновлять массив
освещенодля всех домов, попадающих в радиус освещения фонаря, и регистрировать использование фонаря.Жадный алгоритм: Используйте жадный подход, чтобы сначала устанавливать фонари с большим радиусом (например,
Y), чтобы покрыть как можно большее количество домов. Это уменьшит общее количество установленных фонарей. Пройдите по каждому дому и:- Если этот дом не освещен, установите фонарь рядом с максимально возможным домом, учитывая радиус.
- Обновите состояние освещения.
Проверка полного освещения: После попытки установки всех фонарей, проверьте, освещены ли все дома. Если нет, выведите
-1.Форматирование ответа: Если все дома освещены, выведите координаты и радиус каждого установленного фонаря.
Пример алгоритма:
N = int(input())
A = int(input()) # Количество фонарей с радиусом X
X = int(input()) # Радиус освещения фонарей A
B = int(input()) # Количество фонарей с радиусом Y
Y = int(input()) # Радиус освещения фонарей B
освещено = [False] * (N + 1) # Массив освещенности домов
фонари = [] # Для хранения данных об установленных фонарях
# Настройка фонарей с радиусом Y
for i in range(1, N + 1):
if not освещено[i]: # Если дом не освещен
if B > 0: # Есть ли еще фонари типа B
позиция = min(i + Y, N) # Позиция установки фонаря
фондари.append((позиция, Y))
B -= 1
# Обновляем освещенность домов
for j in range(max(1, позиция - Y), min(N, позиция + Y) + 1):
освещено[j] = True
# Настройка фонарей с радиусом X
for i in range(1, N + 1):
if not освещено[i]: # Если дом не освещен
if A > 0: # Есть ли еще фонари типа A
позиция = min(i + X, N) # Позиция установки фонаря
фонари.append((позиция, X))
A -= 1
# Обновляем освещенность домов
for j in range(max(1, позиция - X), min(N, позиция + X) + 1):
освещено[j] = True
# Проверка на освещенность
if all(освещено[1:]): # Проверяем освещены ли все дома
for фонарь in фонари:
print(фонарь[0], фонарь[1])
else:
print(-1)
Объяснение кода:
- Мы используем два цикла: первый для фонарей с радиусом
Y, второй — сX. - При установке фонаря мы обновляем состояние освещенности, а также следим за количеством доступных фонарей.
- В конце проверяем, есть ли неосвещенные дома, и выводим результат.
Эта стратегия обеспечивает эффективное покрытие домов минимальным количеством фонарей.
