Решение: Рейтинг кандидатов-космонавтов
Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительно от 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) — натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов — с меньшим ID.
Минимальная сумма баллов, с которой зачисляются в отряд все её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.
Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, в противном случае полупроходной балл отсутствует.
Входные данные находятся в прилагаемом файле. В первой строке записаны числа N и K: количество кандидатов и количество мест в отряде. В следующих N строках находятся ID кандидата и четыре числа: результаты трёх испытаний и результат собеседования.
Определите ID кандидата, который последним из рейтингового списка набрал проходной балл, и количество кандидатов, набравших полупроходной балл.
Решение по шагам
4 шагаДля каждого кандидата вычисляем общий результат как сумму баллов за три испытания и собеседование.
$$S = b_1 + b_2 + b_3 + b_4$$Формируем рейтинговый список по трём ключам: общий результат по убыванию, баллы за собеседование по убыванию, ID по возрастанию.
Определяем группу кандидатов с общей суммой, соответствующей последнему месту K. Если число кандидатов в этой группе не превышает количество оставшихся мест, проходной балл равен этой сумме.
Находим ID последнего кандидата в рейтинговом списке с проходным баллом. Если после зачисления этой группы остаются места, то следующая группа с одинаковой суммой является полупроходной только при наличии нескольких претендентов; в ответ записываем размер этой группы.
Определяется по данным прилагаемого файла
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Сортируют ID по убыванию вместо сортировки по возрастанию при равенстве остальных показателей.
Не включают баллы за собеседование в общую сумму.
Считают полупроходной любую группу, пересекающую границу мест, не проверяя, что после проходной группы остались места.
Выводят ID кандидата, занявшего место K, вместо последнего кандидата, набравшего проходной балл.