26. Прикладная задача: #298078

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

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

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

Входные данные

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

Выходные данные

Два числа: сначала 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$. Два кандидата с баллами $302$ и $279$ зачислены, проходной балл $279$. На оставшиеся два места претендуют три человека, набравшие по $240$ баллов, хотя из троих будут зачислены только двое. Таким образом, $240$ – полупроходной балл. Ответ: $6$ $3$.

f = open('26-23.txt')
n, K = map(int, f.readline().split())

c = []
for _ in range(n):
    v = list(map(int, f.readline().split()))
    c.append((-(v[1] + v[2] + v[3] + v[4]), -v[4], v[0]))   # сумма, собеседование, ID
c.sort()

admitted, i, last = 0, 0, None
while i < n:
    j = i
    while j < n and c[j][0] == c[i][0]:      # группа с одинаковой суммой
        j += 1
    if admitted + (j - i) > K:               # группа целиком не влезает
        break
    admitted, last, i = j, c[j-1][2], j

half = (j - i) if (i < n and admitted < K) else 0

print(last, half)   # 45539 127