Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вдоль прямой улицы на равном расстоянии располагаются № домов. Будем считать расстояние между домами за…
Ограничение по времени: 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 Решите задачу на Python
Данная задача может быть решена с использованием жадного алгоритма. Основная идея заключается в том, чтобы установить фонари таким образом, чтобы максимизировать освещение, используя доступные фонари с учетом их радиуса действия.
Вот подробный шаг для решения этой задачи на Python:
- Сначала мы будем отслеживать, какие дома уже освещены.
- Мы будем пытаться установить фонари, начиная с самых правых домов, чтобы покрыть максимальную часть улицы.
- Если фонари одного типа не могут быть установлены, мы будем использовать другие фонари.
Ниже приведен код для решения задачи:
def place_lanterns(N, A, X, B, Y):
lamps = [] # Список для хранения установленных фонарей
lit = [False] * (N + 1) # Массив освещенных домов (1-indexed)
# Попытка установки фонарей от N до 1
for house in range(N, 0, -1):
if not lit[house]:
if A > 0 and (house - X >= 1): # Если можем установить фонарь A
lamps.append((house, X))
for i in range(max(1, house - X), min(N + 1, house + X + 1)):
lit[i] = True
A -= 1
elif B > 0 and (house - Y >= 1): # Если можем установить фонарь B
lamps.append((house, Y))
for i in range(max(1, house - Y), min(N + 1, house + Y + 1)):
lit[i] = True
B -= 1
# Проверка, освещены ли все дома
if all(lit[1:]): # игнорируем 0-й индекс
for lamp in lamps:
print(lamp[0], lamp[1])
else:
print(-1)
# Пример использования функции
N = int(input())
A = int(input())
X = int(input())
B = int(input())
Y = int(input())
place_lanterns(N, A, X, B, Y)
Пояснение коду:
- Мы используем список
lit, чтобы отслеживать, освещены ли дома. - Мы идем в обратном порядке по домам от N до 1 и пытаемся установить фонарь, если дом не освещен.
- Если есть возможность установить фонарь типа A, мы устанавливаем его, затем помечаем освещенные дома.
- Если фонарей типа A не хватает, пробуем установить фонарь типа B.
- В конце проверяем, освещены ли все дома. Если да, то выводим координаты установленных фонарей и их радиус освещения. Если нет, выводим -1.
Этот алгоритм работает с учетом ограничений задачи и обеспечивает решение в адекватное время.
