Question

Отбор абитуриентов в вуз происходит по сумме баллов трех экзаменов: по русскому языку, математике и информатике. На заранее известное количество мест зачисляются абитуриенты, набравшие большую сумму баллов по результатам трех экзаменов. Все абитуриенты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест абитуриентами с проходным баллом остаются незаполненные места, но абитуриентов, набравших следующую сумму баллов, больше, чем вакантных мест, набранная этими абитуриентами сумма баллов называется полупроходным баллом. Из числа абитуриентов, набравших полупроходной балл, на имеющиеся места принимаются абитуриенты, имеющие более высокий балл по математике, а при равенстве баллов по математике — по информатике.Для данного множества абитуриентов следует определить, какая сумма баллов является проходным баллом и какой полупроходной балл по информатике, чтобы быть зачисленным на имеющиеся места.

Задание 26

Входные данные.В первой строке входного файла находятся два числа: N — количество поданных заявлений о приеме (натуральное число, не превышающее 1000) и S — количество имеющихся мест. В следующих N строках три оценки: по русскому языку, математике и информатике, соответственно, разделенные пробелами (все числа натуральные, не превышающие 100).Запишите в ответе два числа без пробела: сначала проходной балл, затем оценку по информатике, необходимую для зачисления при условии набранного полупроходного балла.Пример входного файла:4 260 75 9065 70 9050 80 10040 95 80При таких исходных данных проходной балл равен 230, полупроходной 225, на оставшееся одно место будет зачислен абитуриент, набравший в сумме 225 баллов и получивший по информатике 90 баллов.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

Приём абитуриентов в вуз осуществляется по сумме баллов трёх экзаменов: русский язык, математика и информатика. На фиксированное количество мест зачисляются кандидаты с наибольшей суммой баллов.

**Проходной балл** — минимальная сумма, при которой абитуриент гарантированно зачисляется (все с этой суммой и выше занимают первые S мест).

**Полупроходной балл** — сумма баллов, при которой остаются вакантные места, но кандидатов с этой суммой больше, чем свободных мест. Из них зачисляются те, кто имеет наивысший балл по математике, а при равенстве — по информатике.

**Входные данные:** первая строка содержит N (количество заявлений, не превышает 1000) и S (количество мест). Далее N строк с тремя оценками (русский, математика, информатика), каждая не превышает 100.

**Требуется найти:** проходной балл и минимальный балл по информатике для зачисления при полупроходном балле.

**Пример:**
```
4 2
60 75 90
65 70 90
50 80 100
40 95 80
```

После сортировки по сумме (225, 225, 230, 215) проходной балл = 225, полупроходной = 225. На второе место претендуют два абитуриента с суммой 225; по математике оба имеют 75 и 70, поэтому зачисляется первый (балл по информатике 90).

---

### РЕШЕНИЕ

Идея решения: отсортировать абитуриентов по убыванию суммы баллов (с учётом приоритета по математике и информатике), найти проходной балл на позиции S, затем среди кандидатов с полупроходным баллом выбрать того, кто займёт последнее место по критериям сортировки.

**Шаг 1.** Прочитаем данные и вычислим сумму баллов для каждого абитуриента.

**Шаг 2.** Отсортируем по убыванию суммы, затем по убыванию баллов по математике, затем по убыванию баллов по информатике.

**Шаг 3.** Проходной балл — это сумма баллов абитуриента на позиции S (индекс S-1).

**Шаг 4.** Полупроходной балл — минимальная сумма среди всех, кто набрал больше, чем абитуриент на позиции S.

**Шаг 5.** Среди абитуриентов с полупроходным баллом найдём того, кто займёт первое место по критериям сортировки (максимум по математике, затем по информатике). Его балл по информатике — ответ.

```python
f = open('26.txt')
n, s = map(int, f.readline().split())
applicants = []
for _ in range(n):
    scores = list(map(int, f.readline().split()))
    total = sum(scores)
    applicants.append((scores[0], scores[1], scores[2], total))
f.close()

# Сортируем по сумме (убыв), затем по математике (убыв), 
# затем по информатике (убыв)
applicants.sort(
    key=lambda x: (x[3], x[1], x[2]),
    reverse=True
)

# Проходной балл — сумма на позиции s-1
passing_score = applicants[s - 1][3]

# Полупроходной балл — минимальная сумма, 
# которая больше суммы на позиции s-1
semi_passing = min(
    x[3] for x in applicants if x[3] > applicants[s - 1][3]
)

# Среди абитуриентов с полупроходным баллом 
# найдём первого по критериям сортировки
for x in applicants:
    if x[3] == semi_passing:
        info_score = x[2]
        break

print(str(passing_score) + str(info_score))
```

**Сложность:** $O(n \log n)$ (сортировка).

---

### ОТВЕТ

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=228350)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=228351)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=228352)

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=228353)

Задание №26ПрограммированиеЕГЭ по информатике