В одном городе есть более 100 жилых домов. Все дома пронумерованы, начиная с единицы. Управляющая компания получила заявки на капитальный ремонт от жителей домов. В заявке указан номер дома и номер подъезда, где требуется ремонт, при этом каждой заявке присваивается уникальный идентификатор — натуральное число, не превышающее 1 000 000. На один и тот же подъезд могут быть заявки сразу от нескольких жителей.
Определите номер дома, который имеет наибольшее количество подряд идущих подъездов с заявками на капитальный ремонт. Если есть несколько домов с одинаковым максимальным количеством подъездов, необходимо выбрать тот дом, у которого наименьший искомый подъезд имеет максимальный номер заявки.
Входные данные.
В первой строке входного файла находится натуральное число N (N ≤ 200 000) — количество полученных заявок на капитальный ремонт.
Следующие N строк содержат три числа: номер заявки, номер дома и номер подъезда (все числа натуральные, не превышающие 1 000 000).
Выходные данные.
Запишите в ответе два натуральных числа: сначала номер дома с максимальным количеством подряд идущих подъездов, затем номер первого найденного подъезда из максимального числа подряд идущих подъездов в этом доме.
Ответ:
Откроем файл с помощью редактора электронных таблиц.
Удалим значение в первой строке.
Отсортируем таблицу сначала по номеру дома, потом по номеру квартиры, последнее по номеру заявки.
Получим таблицу:
Чтобы убрать дубликаты применим фильтр по условию
Скопируем получившуюся таблицу на отдельный лист.
В столбце D будем считать номер подъезда по порядку, чтобы увидеть максимальное число идущих подряд подъездов.
В ячейку D1 напишем значение 1. В ячейку D2 запишем формулу =ЕСЛИ(И(C2-C1=1;B2=B1);D1+1;1) и скопируем ее до конца списка.
Применим фильтр для столбца D и выберем максимальное число идущих подъездов - 7:
Получим таблицу:
Так как есть несколько домов с одинаковым максимальным количеством подъездов, выбираем тот дом, у которого наименьший искомый подъезд имеет максимальный номер заявки. Наименьшие подъезды будут 701 (так для группы из 7 подъездов, где 707 последний, 701 будет точкой отчета) для первой найденной заявки и 805 для второй.
Отсортируем заявки по номеру дома и номеру подъезда. У первой найденной конфигурации номер заявки будет больше, следовательно, ответ: номер дома - 171 и номер подъезда - 701
Ответ: 171 701.
Приведём решение Юрия Красильникова на языке Python.
a=[list(map(int,s.split())) for s in open('26.txt')][1:]
dic={} # словарь с ключами (№ дома, № подъезда)
for x in a:
dompod=(x[1],x[2])
dic[dompod]=max(dic.get(dompod,0),x[0]) # максимальный номер заявки в подъезде
b=sorted(list(dic.items()),key=lambda x:x[0]) # по возрастанию № дома и № подъезда
groups=[] # группы подряд идущих подъездов в одном доме
gr=[b[0]] # текущая группа
for x in b[1:]:
if x[0][0]==gr[-1][0][0] and x[0][1]-gr[-1][0][1]==1:
gr.append(x)
else:
groups.append(gr)
gr=[x]
groups.append(gr)
mgl=max([len(x) for x in groups]) # максимальная длина группы
ans=[x[0] for x in groups if len(x)==mgl] # минимальные подъезды из групп с максимальной длиной
mnz=max([x[1] for x in ans]) # максимальный номер заявки
for x in ans:
if x[1]==mnz: print(*x[0])