Задание 26 ЕГЭ по информатике

Question

В банке дистанционной проверяющей системы имеется более 100000 заданий. Все задачи пронумерованы начиная с единицы. Эти задания в течение учебного периода решают участники различных курсов. Каждому студенту при регистрации присваивается уникальный идентификатор – натуральное число, не превышающее 1000000. Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно их них.
Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество задач из банка с идущими подряд номерами, не пропустив ни одной.
Определите идентификационный номер студента, который решил наибольшее количество задач с идущими подряд номерами, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите наименьший идентификационный номер.
Входные данные
В первой строке входного файла находится число $N$ – количество зачтённых решений (натуральное число, не превышающее 60000) за некоторый период времени. Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих 100000: идентификатор студента и номер правильно решённой задачи.
Выходные данные
Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество успешно решённых задач с подряд идущими номерами.
Типовой пример организации входных данных
9
40 3
60 33
60 33
50 125
50 126
50 127
40 4
50 72
50 126
Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач с идущими подряд номерами (3 задачи). Ответом является пара чисел: 50; 3.
Типовой пример носит иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Файл к заданию: https://drive.google.com/file/d/11OGYMUR9VVhFYzsxpRk3mxAxP7GVVs_A/view?usp=sharing

Accepted Answer

f = open('26.txt')

N = int(f.readline())

data = []

for i in range(N):

sid, t = map(int, f.readline().split())

data.append((sid, t))

data.sort() # сортировка по sid, потом по t

best_id = 10**10

best_len = 0

i = 0

while i < len(data):

sid = data[i][0]

# собираем задачи этого студента

tasks = []

last_task = -1

while i < len(data) and data[i][0] == sid:

t = data[i][1]

if t != last_task:

tasks.append(t)

last_task = t

i += 1

cur = 1

cur_best = 1

for j in range(1, len(tasks)):

if tasks[j] == tasks[j - 1] + 1:

cur += 1

else:

if cur > cur_best:

cur_best = cur

cur = 1

if cur > cur_best:

cur_best = cur

if cur_best > best_len or (cur_best == best_len and sid < best_id):

best_len = cur_best

best_id = sid

print(best_id, best_len)

Задание 26 ЕГЭ по информатике

Задания на обработку данных с помощью сортировки