Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме
того, можно получить дополнительное 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) - натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется
по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке
выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов - с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.
Если после зачисления всех кандидатов с проходным баллом в отряде остались места, на которые претендуют несколько кандидатов с одинаковой суммой баллов, то такая сумма баллов называется полупроходным баллом, противном случае полупроходной балл отсутствует.
В ответе запишите два целых числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл.
Если полупроходной балл отсутствует, то второе число в ответе должно быть равно нулю.
Входные данные
В первой строке входного файла находятся два натуральных числа, не превышающих 10 000, через пробел: число N - количество кандидатов и число К - количество мест в отряде. В следующих 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. Два кандидата с баллами 302 и 279 зачислены, проходной балл 279. На оставшиеся два места претендуют три человека, набравшие по 240 баллов, хотя из троих будут зачислены только двое. Таким образом, 240 - полупроходной балл.
Ответ: 6 3
Решение:
Решение на Python:
with open('E:/10/26_20815.txt') as f:
N, K = map(int, f.readline().split())
candidates = []
for _ in range(N):
data = list(map(int, f.readline().split()))
ID = data[0]
exams = data[1] + data[2] + data[3]
interview = data[4]
total = exams + interview
candidates.append((-total, -interview, ID))
candidates.sort()
rating = [(-t, -i, id_) for t, i, id_ in candidates]
passed = 0
i = 0
while i < N:
same_sum = []
j = i
while j < N and rating[j][0] == rating[i][0]:
same_sum.append(rating[j])
j += 1
if passed + len(same_sum) <= K:
passed += len(same_sum)
i = j
else:
passing_score = rating[i][0]
break
last_passing_id = rating[passed - 1][2]
semi_count = 0
if passed < K and i < N:
semi_score = rating[i][0]
while i < N and rating[i][0] == semi_score:
semi_count += 1
i += 1
print(last_passing_id, semi_count)Ответ: 45539 127