Задание 26. Рейтинг: проходной и полупроходной балл – ЕГЭ по информатике

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

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

2 балла, норматив 35 минут.
Что нужно знать заранее:

sort с ключом-кортежем и минус для убывания;
чтение файла построчно и split – чтение файлов;
обращение к элементу списка по месту: граница списка – это пара соседних индексов k - 1 и k, и вся задача держится на них.

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

Задача из банка kompege.ru.

Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительно от 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) – натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов – с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.

Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, в противном случае полупроходной балл отсутствует.

В ответе запишите два целых числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл. Если полупроходной балл отсутствует, то второе число в ответе должно быть равно нулю.

Входные данные
В первой строке входного файла находятся два натуральных числа, не превышающих 10 000, через пробел: число N – количество кандидатов и число K – количество мест в отряде. В следующих N строках находятся по 5 чисел через пробел: ID кандидата (натуральное число, не превышающее 100 000) и четыре целых неотрицательных числа – сначала результаты испытаний, затем результат собеседования.

Выходные данные
Два числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл.

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

6 4
4 80 80 80 0
7 50 80 100 10
11 80 80 70 10
10 100 100 100 2
6 90 90 90 9
2 70 80 80 8

При таких исходных данных рейтинговый список из ID составлен следующим образом: 10 6 7 11 4 2. 2 кандидата с баллами 302 и 279 зачислены, проходной балл 279. На оставшиеся 2 места претендуют 3 человека, набравшие по 240 баллов, хотя зачислить из них можно только 2. Таким образом, 240 – полупроходной балл.

Ответ для приведённого примера: 6 3.

Файл с данными: bank-26_20815_26_1.txt – 9996 строк: строка на каждого кандидата. Положите его рядом со скриптом, не переименовывая: код ниже открывает bank-26_20815_26_1.txt – то самое имя, под которым файл скачивается.

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

Условие длинное, но задача в нём одна: построить рейтинговый список и посмотреть, что происходит на его границе – там, где кончаются места. Отсюда план:

Прочитать кандидатов и сразу посчитать каждому сумму баллов так, как требует условие.
Упорядочить их по правилам из условия – это и есть рейтинговый список.
Посмотреть на границу списка: хватило ли мест всем, у кого одинаковая сумма, или нет. Отсюда станет ясно, есть ли полупроходной балл.
Пройти по списку и собрать ответ: кто последний с проходным баллом и сколько человек набрали полупроходной.

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

Шаг 1. Читаем кандидатов

В первой строке – N и K: сколько кандидатов и сколько мест. Дальше в каждой строке пять чисел: ID, три испытания и собеседование. map(int, line.split()) превращает строку сразу в пять чисел, и их удобно разложить по именам.

Каждого кандидата храним кортежем (сумма, собеседование, ID) – ровно в том порядке, в каком по ним строится рейтинг. Больше ничего от строки не понадобится: отдельные испытания в условии нужны только ради суммы.

Сумма включает собеседование. В нашей задаче сказано «по убыванию суммы набранных баллов, включая баллы за собеседование», поэтому сумма – a + b + c + talk.

with open('bank-26_20815_26_1.txt') as f:
    n, k = map(int, f.readline().split())
    people = []                          # кандидаты: (сумма, собеседование, ID)
    for line in f:
        pid, a, b, c, talk = map(int, line.split())
        people.append((a + b + c + talk, talk, pid))   # сумма – вместе с собеседованием

Шаг 2. Строим рейтинговый список

Условие перечисляет признаки по очереди, и каждый следующий работает только при равенстве предыдущего: сумма, потом баллы за собеседование, потом ID. Python сравнивает кортежи точно так же – слева направо, до первого различия. Значит, правила условия записываются одним ключом-кортежем.

key=lambda p: (...) – это маленькая функция: для каждого кандидата p она говорит, по чему его сравнивать. p[0] – сумма, p[1] – собеседование, p[2] – ID.

Сумма и собеседование нужны по убыванию, а ID – по возрастанию. Один reverse=True на всё тут не годится: он развернул бы и ID. Поэтому убывающие признаки берём с минусом: чем больше сумма, тем меньше (минус сумма), и такой кандидат встаёт раньше.

На примере из условия список получается таким: 10 6 7 11 4 2 – ровно как в условии.

# сумма и собеседование – по убыванию, ID – по возрастанию
people.sort(key=lambda p: (-p[0], -p[1], p[2]))

Шаг 3. Смотрим на границу списка

Мест всего K, значит, последний, кому хватило места, стоит на K-м месте. Места считаются с 1, а индексы в Python – с 0: K-е место – это people[k - 1], а следующий за ним, первый не поместившийся, – people[k].

Сравниваем их суммы:

совпали – кандидатов с этой суммой больше, чем мест на них осталось: группа не влезла целиком. Эта сумма и есть полупроходной балл, а зачислены целиком все, у кого сумма больше;
разные – все с суммой K-го поместились, полупроходного балла нет, и второе число ответа – ноль. Чтобы шаг 4 это понял, запоминаем semi = None – «такого балла нет».

Место	ID	Сумма	Собеседование	Итог
1	10	302	2	зачислен
2	6	279	9	зачислен
3	7	240	10	полупроходной
4	11	240	10	полупроходной
5	4	240	0	полупроходной
6	2	238	8	ниже проходного

Подсвечена строка с ответом – кандидат 6. Проходной балл примера – 279, полупроходной – 240: его набрали 3 кандидата (7, 11, 4), а мест на них осталось 2.

edge = people[k - 1][0]                  # сумма последнего, кому хватило места
if people[k][0] == edge:                 # у следующего та же сумма – мест не хватило
    semi = edge                          # это полупроходной балл
else:
    semi = None                          # полупроходного балла нет

Шаг 4. Собираем ответ

«Последний, набравший проходной балл» – не последний зачисленный. Часть группы с полупроходным баллом тоже попадает в отряд, и на K-м месте стоит как раз кто-то из них. Спрашивают же того, кто стоит последним среди зачисленных целиком.

Поэтому идём по списку и каждого кандидата относим к одной из групп:

сумма равна полупроходному баллу – прибавляем к semi_count;
иначе, если сумма не меньше edge, – кандидат зачислен с проходным баллом, запоминаем его ID. Список упорядочен, поэтому к концу цикла в last_id останется последний такой.

Почему >= edge работает в обоих случаях шага 3. Если полупроходной балл есть, кандидаты с суммой edge уже забрала первая ветка, и во вторую попадают только те, у кого больше. Если его нет (semi = None), первая ветка не сработает ни разу, и зачисленными считаются все с суммой не меньше edge.

На примере: последним с проходным баллом 279 стоит кандидат 6, полупроходной балл 240 набрали 3. Ответ примера – 6 3, как в условии.

semi_count = 0                           # сколько набрали полупроходной балл
for total, talk, pid in people:
    if total == semi:
        semi_count += 1
    elif total >= edge:                  # зачислен с проходным баллом
        last_id = pid                    # к концу цикла – последний такой
print(last_id, semi_count)               # 45539 127

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

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

На файле банка арифметика та же, только чисел больше: на месте 1076 стоит кандидат с суммой 279, и у следующего за ним сумма та же – 279. Значит, все, кто набрал больше, зачислены – их 955, и они заняли 955 из 1076 мест. Осталось 121 место, а претендуют на них 127 кандидатов с суммой 279. Проходной балл – 280: столько набрал последний в списке, кто его набрал, – кандидат 45539.

Решение

with open('bank-26_20815_26_1.txt') as f:
    n, k = map(int, f.readline().split())
    people = []                          # кандидаты: (сумма, собеседование, ID)
    for line in f:
        pid, a, b, c, talk = map(int, line.split())
        people.append((a + b + c + talk, talk, pid))   # сумма – вместе с собеседованием

# сумма и собеседование – по убыванию, ID – по возрастанию
people.sort(key=lambda p: (-p[0], -p[1], p[2]))

edge = people[k - 1][0]                  # сумма последнего, кому хватило места
if people[k][0] == edge:                 # у следующего та же сумма – мест не хватило
    semi = edge                          # это полупроходной балл
else:
    semi = None                          # полупроходного балла нет

semi_count = 0                           # сколько набрали полупроходной балл
for total, talk, pid in people:
    if total == semi:
        semi_count += 1
    elif total >= edge:                  # зачислен с проходным баллом
        last_id = pid                    # к концу цикла – последний такой
print(last_id, semi_count)               # 45539 127

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

Что в условии	Что править в коде
матросы: собеседование в сумму не входит, а только упорядочивает кандидатов с равной суммой	`people.append((a + b + c, talk, pid))` – сумма без собеседования, остальное как было
сессия, повышенная стипендия первым 25 % мест: четыре оценки, у сдавших без двоек – средний балл по убыванию	сначала число двоек, потом средний балл только у сдавших, потом ID: `key=lambda r: (r.count(2), -sum(r) if r.count(2) == 0 else 0, pid)`, где `r` – четыре оценки; стипендиаты – первые `n // 4` строк списка
лидер продаж среди дорогих	рейтинг не обязательно строить сортировкой: словарь «артикул → продано и осталось», затем `min` по тому же ключу-кортежу `(-продано, -цена, осталось)`

Третий вариант стоит запомнить отдельно: когда нужен один лидер, а не весь список, min или max с тем же ключом делают то же самое и без сортировки.

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

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

Собеседование не включили в сумму. В ключе осталась сумма трёх испытаний, а собеседование только упорядочивает кандидатов с равной суммой.
При равной сумме смотрели только на ID. Ключ (-сумма, ID) теряет второй признак условия: при равенстве сумм выше стоит тот, у кого больше баллов за собеседование.
Назвали ID последнего, кому хватило места. На месте 1076 стоит кандидат с суммой 279 – он последний зачисленный, а не последний с проходным баллом: часть группы с полупроходным баллом тоже попадает в отряд.
Вторым числом посчитали оставшихся без места. Условие просит количество кандидатов, набравших полупроходной балл, а не тех, кому мест не хватило.