В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы. По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно 11 идущих подряд свободных мест для посадки новых сосен, таких, что непосредственно слева и справа от них в том же ряду растут сосны. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа через пробел: наибольший номер ряда и наименьший номер места для посадки из числа найденных в этом ряду подходящих последовательностей из 11 свободных мест.
Входные данные. В первой строке входного файла находится число N – количество прижившихся саженцев сосны (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места в этом ряду, на котором растёт деревце.
Выходные данные. Два целых неотрицательных числа через пробел: наибольший номер ряда и наименьший номер места в выбранной последовательности из 11 мест, подходящих для посадки новых сосен.
Решение (Excel/LibreOffice)
Открываем программу Excel и загружаем в неё наш файл. Сортируем данные столбца А и В по возрастанию.
В ячейку впишем формулу:
ЕСЛИ(И
и растянем её вниз. Далее выберем с помощью фильтра про столбцу С те строки, в которых значения равны 1. Наибольший номер ряда будет находится в самом низу таблицы и равен 59966. Наибольший номер в выбранной последовательности будет отличаться на 1 от номера места для ряда найденного 59966, то есть 81345.
Решение (Python)
f = open(’264__1vi92.txt’)
n = int(f.readline())
a = [] # список координат прижившихся саженцев
for i in range(n):
x, y = [int(_) for _ in f.readline().split()] # считывание текущей строки
a.append([x, y])
a.sort()
ans = [0, 0]
for i in range(n-1): # проход по всем координатам саженцев
# если ряд двух рядом стоящих в списке саженцев совпадает и при этом между ними есть 11 свободных мест
if a[i][0] == a[i + 1][0] and a[i][1]+12 == a[i+1][1]:
row = a[i][0] # вычисляем ряд
place = a[i][1] + 1 # вычисляем минимальное свободное место
if row > ans[0]:
ans[0] = row
ans[1] = place
print(*ans)