Задача #1693
Сортировка
(И.Карпачев) Дед мороз и снеговик играют в следующую игру. Перед ними лежат шары для украшения ёлки различного радиуса, на которых записаны числа. Данные числа обозначают позицию центра шара на специальной ленте с числовой разметкой. Дед мороз и снеговик друг за другом ставят шары на ленту так, чтобы стенки шаров соприкасались друг с другом.
Определите, какое максимальное количество шаров могут поставить на ленту два игрока, и какую минимальную конечную отметку должна иметь лента, чтобы при максимальном размещении шаров, они все уместились на ней.
Входные данные:
В первой строке файла находиться натуральное число N – количество всех шаров в наборе. В следующих N строках по два числа – позиция центра шара на ленте и радиус шара.
Выходные данные:
В ответе укажите два числа: максимальное количество шаров могут поставить на ленту два игрока и минимальная конечная отметка ленты, чтобы поместить на ней максимальное количество шаров.
Типовой пример организации данных во входном файле:
5
6 2
3 1
4 2
12 4
8 2
При таких исходных данных, игроки смогут разместить на ленте максимум 3 шара: (3, 1) -> (6, 2) -> (12, 4). Тогда минимальная конечная отметка ленты для такого размещения шаров будет равна 16.
Решение
Ответ
f = open('26.txt')
N = int(f.readline())
a = []
for s in f:
c,r = [int(x) for x in s.split()]
a.append([c-r,c+r])
a.sort()
max_zep =[0]*N
for i in range(N):
prev_zep = [max_zep[j] for j in range(N) if a[i][0] == a[j][1]]
if prev_zep:
max_zep[i] = max(prev_zep)+1
else:
max_zep[i] = 1
mx = max(max_zep)
print(mx, min([a[i][1] for i in range(N) if max_zep[i]==mx]))