26. Прикладная задача: Во время сессии студенты сдают 4 экзамена, за каждый из которых можно…
Во время сессии студенты сдают $4$ экзамена, за каждый из которых можно получить от $2$ до $5$ баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по $2$ балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.
Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые $25,%$ мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее $25,%$ студентов. Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».
В ответе запишите два целых положительных числа: сначала ID студента, который занимает последнее место среди студентов с повышенной стипендией, затем ID первого в рейтинговом списке студента, который имеет более двух «двоек».
Строить весь рейтинг целиком не обязательно, но проще всего именно так и сделать — он собирается из двух независимо отсортированных частей.
Первая часть: студенты без «двоек». Сортируем их по убыванию среднего балла, при равенстве — по возрастанию ID. Средний балл делить на четыре не нужно: сравнение сумм даёт тот же порядок, а с целыми числами не будет проблем с точностью. Чтобы одной сортировкой получить «сумма по убыванию, ID по возрастанию», кладём в ключ сумму со знаком минус.
Вторая часть: студенты с «двойками». Сортируем по количеству «двоек» по возрастанию, при равенстве — по ID. Ровно так и описан порядок в условии: сначала одна «двойка», потом две, три и четыре.
Дальше два ответа. Повышенную стипендию получают первые $N/4$ мест, и по условию гарантируется, что все они попадают в первую часть. Значит нужен элемент рейтинга с номером $N/4$, то есть индекс $N/4 - 1$. Второй ответ — первый в списке студент с более чем двумя «двойками», то есть первый элемент второй части, у которого «двоек» три или четыре.
f = open('26-18.txt')
n = int(f.readline())
passed, failed = [], []
for _ in range(n):
v = list(map(int, f.readline().split()))
sid, marks = v[0], v[1:]
twos = marks.count(2)
if twos == 0:
passed.append((-sum(marks), sid)) # балл по убыванию, ID по возрастанию
else:
failed.append((twos, sid)) # число двоек, затем ID
passed.sort()
failed.sort()
rating = [sid for _, sid in passed] + [sid for _, sid in failed]
top = rating[n//4 - 1] # последнее место среди 25 %
first_bad = next(sid for twos, sid in failed if twos > 2)
print(top, first_bad) # 52326 635
Проверка. Студентов $9964$, из них без «двоек» — $6682$, что заметно больше четверти, так что граница стипендии действительно попадает в первую часть. Четверть мест — это $2491$, и на этом месте стоит студент с ID $52326$ и суммой баллов $17$; соседи по рейтингу имеют ту же сумму, но ID $52268$ и $52380$, то есть тай-брейк по возрастанию ID здесь сработал. С тремя «двойками» в файле $195$ студентов, с четырьмя — $15$, и первый из них по ID — $635$. На типовом примере из условия программа выдаёт $6$ и $13$.