Задача по олимпиаде по информатике

Question

Задача по олимпиаде по информатике

Иван Мазикин Ученик (87), на голосовании 1 неделю назад

Фонари
Вдоль прямой улицы на равном расстоянии располагаются
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. В результате все дома освещены. Во втором примере фонарей недостаточно.

Примеры

Answer 1

Вдоль прямой улицы на равном расстоянии располагаются N домов. Расстояние между домами — единица длины. Около каждого дома можно поставить один фонарь. Всего имеется А фонарей, которые могут освещать дома на расстоянии Х (включительно), и В фонарей, которые могут освещать дома на расстоянии Y (включительно). При этом при X = 0 или Y = 0 такой фонарь освещает только тот дом, у которого он установлен. 3

Необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно. 3

Формат входных данных: первая строка содержит целое число N (1 ≤ N ≤ 100). Следующие четыре строки содержат целые неотрицательные числа А, Х, В и Y соответственно, которые не превосходят 105

Answer 2

Решение на 20/100 балов
N = int(input(''))
A = int(input(''))
X = int(input(''))
B = int(input(''))
Y = int(input(''))
hs = (A * 3) + (B * 5)
if hs < N:
print(-1)

Answer 3

Кирилл Ракитин Ученик (104) 1 месяц назад

n, a, x, b, y = int(input()), int(input()), int(input()), int(input()), int(input())
k = 1
l = list()
if x > y:
for i in range(a):
if k + x <= n:
k += 2 * x + 1
l.append(f'{k - x - 1} {x}')
for i in range(b):
if k + y <= n:
k += 2 * y + 1
l.append(f'{k - y - 1} {y}')
else:
for i in range(b):
if k + y <= n:
k += 2 * y + 1
l.append(f'{k - y - 1} {y}')
for i in range(a):
if k + x <= n:
k += 2 * x + 1
l.append(f'{k - x - 1} {x}')
if k < n:
print(-1)
else:
for i in l:
print(i)

70 баллов

Даниял ТагировУченик (148) 1 месяц назад

это пайтон?

Кирилл Ракитин Ученик (104) Даниял Тагиров, да

Михаил АфонинЗнаток (322) 1 месяц назад

12
3
1
1
2
ВЕРНЕТ НЕВЕРНО

Артём БутенкоУченик (110) 1 месяц назад

у тебя маленькая ошибка , if k == n:
print(-1)
так должно быть

Артём БутенкоУченик (110) 1 месяц назад

вообще код не самый правильный , 40 баллов пошёл

Lilit KhananushyanУченик (89) 1 месяц назад

Solnishco27Ученик (220) 3 недели назад

надо сделать обработку последнего дома, в случае, если он не освещен (для случая, когда 12 домов)
n, a, x, b, y = int(input()), int(input()), int(input()), int(input()), int(input())
k = 1 #кол-во освещенных домов
l = []#список: номер дома и яркость фонаря(на сколько домов в сторону светит)
if x < y:
a,x,b,y = b,y,a,x #обмен, если яркость фонаря А < яркости фонаря B
for i in range(a):
if k + x <= n:
k += 2 * x + 1; l.append(f'{k - x - 1} {x}')

for i in range(b):
if k + y <= n:
k += 2 * y + 1 ; l.append(f'{k - y - 1} {y}')

if k - 1 < n and len(l) < a + b: #обработка последнего дома, в случае, если он не освещен
l.append(f'{n} {y}')

if k < n:
print(-1)
else:
for i in l:
print(i)