Задание 26. Информатика. ЕГЭ. ЕГКР. 21.12.2024
- Просмотры: 561
- Изменено: 29 января 2025
В банке дистанционной проверяющей системы имеется более \(100~000\) заданий. Все задачи пронумерованы начиная с единицы. Эти задания в течение учебного периода решают участники различных курсов. Каждому студенту при регистрации присваивается уникальный идентификатор — натуральное число, не превышающее \(1~000~000.\) Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.
Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество задач из банка с идущими подряд номерами, не пропустив ни одной.
Определите идентификационный номер студента, который решил наибольшее количество задач с идущими подряд номерами, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите наименьший идентификационный номер.
Входные данные
В первой строке входного файла находится число \(N\) — количество зачтённых решений (натуральное число, не превышающее \(60~000\)) за некоторый период времени. Каждая из следующих \(N\) строк содержит два натуральных числа, не превышающих \(100~000\): идентификатор студента и номер правильно решённой задачи.
Выходные данные
Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество успешно решённых задач с подряд идущими номерами.
Решение:
Python
def pd(arr):
ans = 1
p = 0
while p < len(arr):
i = 1
while p + i < len(arr) and arr[p + i] == arr[p] + i:
i += 1
ans = max(ans, i)
p += i
return ans
base = ''
fd = open(base + '26.txt')
N = int(fd.readline())
tasks = {}
for line in fd:
i, n = map(int, line.split())
if tasks.get(i):
tasks[i].append(n)
else:
tasks[i] = [n]
arr = [(pd(sorted(v)), -k) for k, v in tasks.items()]
arr.sort(reverse=True)
print(-arr[0][1], arr[0][0])
Ответ: \(40031 \,\, 148\)