Решение задачи Таможня с Яндекс Контест

Без пояснения   Просмотров: 1159

Идёт 2163 год. Мишу, который работает в отделении таможни при космодроме города Нью-Питер, вызвал в кабинет шеф.

Как оказалось, недавно Министерство Налогов и Сборов выделило отделению определённую сумму денег на установку новых аппаратов для автоматического досмотра грузов. Естественно, средства были выделены с таким расчётом, чтобы грузы теперь находились на таможне ровно столько времени, сколько требуется непосредственно на их досмотр.

В руках шефа каким-то образом оказались сведения о надвигающейся ревизии – список из N грузов, которые будут контролироваться Министерством. Для каждого груза известны время его прибытия, отсчитываемое с некоторого момента, хранимого в большом секрете, и время, требуемое аппарату для обработки этого груза. Шеф дал Мише задание по этим данным определить, какое минимальное количество аппаратов необходимо заказать на заводе, чтобы все грузы Министерства начинали досматриваться сразу после прибытия. Необходимо учесть, что конструкция тех аппаратов, которые было решено установить, не позволяет обрабатывать два груза одновременно на одном аппарате. Напишите программу, которая поможет Мише справиться с его задачей.

Код 

n = int(input())
a = []
dict = {}
mx = 0
for i in range(n):
    x, y = map(int, input().split())
    a += ([[x, '('], [x + y, ')']])
    if x + y in dict:
        dict[x + y] += 1
    else:
        dict[x + y] = 1
k = 0
a.sort()
i = 0
while True:
    if i > len(a):
        break
    if i < len(a) and a[i][0] in dict:
        k -= dict[a[i][0]]
        dict[a[i][0]] = 0
    mx = max(mx, k)
    if i < len(a) and a[i][1] == '(':
        k += 1
    mx = max(mx, k)
    i += 1
print(mx)

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp