Код по информатике

Петя живет на проспекте, который является координатной прямой. Дом Пети находится в точке х, а его школа в точке у. Поскольку Петя живет на севере, то когда он идет в школу из дома, на улице еще темно. Зима длинная, солнца мало, поэтому в каждой точке проспекта, координата которой нацело делится на k, стоит фонарь. Например, если k = 3, то фонари есть в точках -6, -3, 0, 3, 6 и так далее в обе стороны.
Каждый фонарь светит злево и вправо на l. Например, если фонарь стоит в точке 2, и 1 = 4, то фонарь освещает участок прямой от —2 до 6.
Петя не любит ходить по темным участкам проспекта. Он хочет разработать план установки дополнительных фонарей (с таким же параметром l), чтобы путь от дома до школы был полностью освещен. Помогите Пете и определите минимальное число фонарей, которое нужно добавить, чтобы путь от дома до школы был полностью освещен.
Путь от дома до школы называется освещенным, если каждая его точка освещена хотя бы одним фонарем.

Только авторизированные пользователи могут оставлять свои ответы

Дата

Популярность

shi_143

Оракул

6мес

1234567891011121314151617181920212223242526272829303132333435363738

 import math 
 
x, y, k, l = map(int, input().split()) 
if x > y: 
    x, y = y, x 
  
s = math.ceil((x - l) / k) * k 
e = math.floor((y + l) / k) * k 
 
a = [] 
pos = s 
while pos <= e: 
    a.append([pos - l, pos + l]) 
    pos += k 
  
a.sort() 
m = [] 
for i in a: 
    if not m or m[-1][1] < i[0]: 
        m.append(i) 
    else: 
        m[-1][1] = max(m[-1][1], i[1]) 
 
u = [] 
p = x 
for i in m: 
    s = max(i[0], x) 
    e = min(i[1], y) 
    if p < s: 
        u.append([p, s]) 
    p = max(p, e) 
if p < y: 
    u.append([p, y]) 
  
r = 0 
for s, e in u: 
    r += math.ceil((e - s) / (2 * l)) 
print(r)