Задание 26. Серии подряд идущих номеров – ЕГЭ по информатике

Что проверяет задание

Задание 26 – обработка файла с данными, где каждая строка описывает пару «кто – что»: спортсмен и контрольная точка, студент и решённая задача. В этом сюжете строки надо сгруппировать по одному столбцу, а в каждой группе найти самую длинную серию подряд идущих номеров – из них и складывается ответ.

2 балла, норматив 35 минут; одно верное число из двух – 1 балл.
Что нужно знать заранее:

чтение файла построчно и split – чтение файлов;
словарь и множества: здесь словарь хранит не числа, а множества номеров, и повторное посещение в них не считается;
sorted: серия ищется в отсортированном множестве, а обход точек по возрастанию решает вопрос равных рекордов;
проход по соседним элементам списка: people[i - 1] и people[i] – соседи, и вся серия считается одним проходом.

Типовой пример

Задача из банка kompege.ru (№ 23383).

На соревнованиях по спортивному ориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер – натуральное число, не превышающее 1 000 000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем.

Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее число спортсменов с идущими подряд номерами. Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки.

Входные данные
В первой строке входного файла находится число N (натуральное число, не превышающее 1 000 000) – количество посещений спортсменами контрольных точек в течение всего сезона соревнований. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: номер спортсмена и номер посещённой им контрольной точки.

Выходные данные
Два целых неотрицательных числа: максимальное число спортсменов с идущими подряд номерами, посетивших одну и ту же точку, и номер этой точки.

Типовой пример организации данных во входном файле

Для приведённого примера точку с номером 125 посетили спортсмены 41, 42, 43 – их номера идут подряд, и на этой точке серия самая длинная. Ответом является пара чисел: 3; 125.

Файл с данными: bank-26_23383_26_1.txt – 59 188 строк посещений и 9 653 различных контрольных точек. Положите его рядом со скриптом, не переименовывая: код ниже открывает bank-26_23383_26_1.txt – то самое имя, под которым файл скачивается.

Как рассуждать

Спрашивают про контрольную точку, а данные в файле – отдельные посещения, вперемешку. Чтобы искать серию на точке, сначала надо для каждой точки собрать, кто на ней был. Отсюда план:

Сгруппировать посещения по точкам: точка → номера спортсменов, которые на ней побывали.
Для одной точки найти самую длинную серию подряд идущих номеров.
Повторить это для всех точек и запомнить лучшую – с учётом того, что при равенстве нужна наименьшая точка.

Дальше – по шагу на каждый пункт.

Шаг 1. Группируем посещения по точкам

Сначала решите, по какому столбцу группировать. Ключ словаря – то, что просят назвать в ответе: спрашивают «номер точки», значит, ключ – точка, а серия ищется среди номеров спортсменов. В файле точка стоит вторым числом строки.

Значение – множество, а не список. Условие прямо говорит, что спортсмен может посетить одну и ту же точку несколько раз. В списке такой повтор останется дважды: ряд 41, 42, 42, 43 рвётся посередине, потому что одинаковые соседи не различаются на единицу. set повтор не считает, а важно именно кто был на точке, а не сколько раз.

Когда точка встречается впервые, ключа в словаре ещё нет, и visitors[point].add(...) упадёт с KeyError. Поэтому новой точке сначала заводим пустое множество, set().

with open('bank-26_23383_26_1.txt') as f:
    n = int(f.readline())
    visitors = {}                        # точка → множество побывавших спортсменов
    for line in f:
        athlete, point = map(int, line.split())
        if point not in visitors:        # точка встретилась впервые
            visitors[point] = set()
        visitors[point].add(athlete)     # set: повторное посещение не считается

Шаг 2. Самая длинная серия на одной точке

Возьмём одну точку. Номера спортсменов сортируем по возрастанию – тогда подряд идущие номера окажутся рядом в списке. Дальше идём по соседям: people[i - 1] и people[i].

Если следующий номер ровно на единицу больше предыдущего, серия продолжается: run += 1.
Иначе серия прервалась и начинается заново – с 1, а не с 0: один человек на точке это уже серия длины 1.

Самую длинную серию longest обновляем на каждом шаге. Цикл идёт с i = 1, потому что у первого номера предыдущего нет.

На примере: на точке 125 побывали 41, 42, 43 – каждый номер на единицу больше предыдущего, и серия растёт до 3.

Этот фрагмент считает серию для одной точки point; в шаге 3 он встанет внутрь цикла по всем точкам.

people = sorted(visitors[point])         # номера спортсменов по возрастанию
run = 1                                  # длина текущей серии
longest = 1                              # самая длинная серия на этой точке
for i in range(1, len(people)):
    if people[i] == people[i - 1] + 1:   # номер идёт сразу за предыдущим
        run += 1
    else:                                # серия прервалась – начинаем новую
        run = 1
    longest = max(longest, run)

Шаг 3. Лучшая точка

Теперь повторяем шаг 2 для каждой точки и запоминаем рекорд: самую длинную серию best и точку best_point, где она нашлась.

Равные рекорды. В файле 166 точек с серией длины 56: условие требует назвать наименьшую. Две детали решают это вместе:

обходим точки по возрастанию, sorted(visitors) – тогда из равных первой встретится наименьшая;
рекорд обновляем только при строго большей серии, longest > best, – тогда следующая равная точка его не перебьёт.

Точка	Побывали (множество)	Самая длинная серия
3	41	1
33	50	1
125	41, 42, 43	3
126	42, 50	1
127	42	1

Ответ примера – 3 125, как в условии.

best = 0                                 # самая длинная серия среди всех точек
best_point = 0                           # и точка, где она нашлась
for point in sorted(visitors):           # по возрастанию: при равенстве победит меньшая
    people = sorted(visitors[point])         # номера спортсменов по возрастанию
    run = 1                                  # длина текущей серии
    longest = 1                              # самая длинная серия на этой точке
    for i in range(1, len(people)):
        if people[i] == people[i - 1] + 1:   # номер идёт сразу за предыдущим
            run += 1
        else:                                # серия прервалась – начинаем новую
            run = 1
        longest = max(longest, run)
    if longest > best:                   # строго: равный рекорд точку не меняет
        best = longest
        best_point = point

print(best, best_point)                  # 56 30113

Программа целиком

Шаг 1 и шаг 3 подряд – это и есть решение: шаг 2 уже стоит внутри шага 3. Перед запуском на файле прогоните программу на примере из условия: сохраните пример в отдельный файл и подставьте это имя в open. Должно выйти 3 125.

Решение

with open('bank-26_23383_26_1.txt') as f:
    n = int(f.readline())
    visitors = {}                        # точка → множество побывавших спортсменов
    for line in f:
        athlete, point = map(int, line.split())
        if point not in visitors:        # точка встретилась впервые
            visitors[point] = set()
        visitors[point].add(athlete)     # set: повторное посещение не считается

best = 0                                 # самая длинная серия среди всех точек
best_point = 0                           # и точка, где она нашлась
for point in sorted(visitors):           # по возрастанию: при равенстве победит меньшая
    people = sorted(visitors[point])         # номера спортсменов по возрастанию
    run = 1                                  # длина текущей серии
    longest = 1                              # самая длинная серия на этой точке
    for i in range(1, len(people)):
        if people[i] == people[i - 1] + 1:   # номер идёт сразу за предыдущим
            run += 1
        else:                                # серия прервалась – начинаем новую
            run = 1
        longest = max(longest, run)
    if longest > best:                   # строго: равный рекорд точку не меняет
        best = longest
        best_point = point

print(best, best_point)                  # 56 30113

Если спрашивают другое

Что в условии	Что править в коде
«студент, решивший больше всего задач с подряд идущими номерами; при равенстве – наименьший ID»	группировать по студенту: ключ – первое число строки, серия ищется среди номеров задач, печатать `best_student, best`
«задачи через одну: одну решил, следующую нет»	условие продолжения серии – `people[i] == people[i - 1] + 2`
«при равенстве – наибольший номер»	`>=` вместо `>` в обновлении рекорда или обход `sorted(visitors, reverse=True)`

Во всех вариантах программа сначала запускается на примере из условия.

Типичные ошибки

Список вместо множества. visitors[point] = [] и .append(...) вместо set() и .add(...) – повторное посещение остаётся в отсортированном ряду дважды и рвёт серию посередине.
>= при обновлении рекорда. Условие просит наименьшую из точек с наибольшей серией, а нестрогое сравнение оставляет последнюю по обходу.
Счётчик серии сбрасывали в 0, а не в 1. run = 0 в начале и после разрыва считает шаги, а не людей: в серии из 56 человек шагов 55, и первым числом выходит 55.