Фонари
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.
Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен.
Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.
Формат входных данных
Первая строка входных данных содержит целое число N (1≤N≤105). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 105.
Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел координату фонаря и расстояние, которое он освещает (то есть одно из чисел 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
3
1
1
2
Вывод
2 1
5 2
9 1
Вывод
10
1
1
1
2
Вывод
-1
Ответы
Чтобы решить эту задачу, можно использовать следующий алгоритм:
Ввести целое число N, представляющее количество домов.
Ввести целые неотрицательные числа A, X, B и Y, представляющие количество фонарей, которые могут освещать дома на расстоянии X и Y соответственно.
Если A + B < N, то вывести -1, поскольку недостаточно фонарей, чтобы освещать все дома.
Иначе, начать с первого дома и пытаться устанавливать фонари, чтобы освещать дома.
Если есть фонарь, который может освещать дома на расстоянии X, то устанавливать его у дома, чтобы освещать дома в диапазоне [дом — X, дом + X].
Если нет фонаря, который может освещать дома на расстоянии X, то устанавливать фонарь, который может освещать дома на расстоянии Y.
Повторять шаги 5 и 6, пока все дома не будут освещены.
Вывести координаты фонарей и расстояния, которые они освещают.
Реализация на Python:
N = int(input())
A = int(input())
X = int(input())
B = int(input())
Y = int(input())
def calculate_lights(N, A, X, B, Y):
if A + B < N:
return -1
lights = []
i = 1
while i <= N: if A > 0 and i + X <= N: lights.append((i, X)) A -= 1 i += X + 1 elif B > 0 and i + Y <= N:
lights.append((i, Y))
B -= 1
i += Y + 1
else:
i += 1
return lights
lights = calculate_lights(N, A, X, B, Y)
if lights == -1:
print(-1)
else:
for light in lights:
print(light[0], light[1])
Эта программа вводит целое число N и целые неотрицательные числа A, X, B и Y, затем вызывает функцию calculate_lights, которая возвращает список координат фонарей и расстояния, которые они освещают. Если недостаточно фонарей, чтобы освещать все дома, то функция возвращает -1.
# Read input
N = int(input())
A, X = map(int, input().split())
B, Y = map(int, input().split())
# Calculate the number of fences needed
fences = []
for i in range(1, N + 1):
if i == 1 or i == N:
fences.append((i, 1))
else:
if A > 0:
fences.append((i, X))
A -= 1
else:
fences.append((i, Y))
B -= 1
# Check if all houses are covered
if B > 0 and Y > 1:
print(-1)
else:
# Print the result
for i in range(len(fences)):
print(fences[i][0], fences[i][1])