Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: Во время сессии студенты сдают 4 экзамена, за каждый из которых можно…

Задание #298066
Решено верно
Решено неверно
Сообщить о проблеме

Во время сессии студенты сдают $4$ экзамена, за каждый из которых можно получить от $2$ до $5$ баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по $2$ балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.

Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые $25,%$ мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее $25,%$ студентов. Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».

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

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

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

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

Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.

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

8
4 4 4 4 4
7 5 5 5 2
10 3 4 4 5
1 4 4 4 3
6 3 5 5 3
2 2 2 2 2
13 2 2 2 3
3 3 3 3 3

При таких исходных данных рейтинговый список ID имеет вид: $4$ $6$ $10$ $1$ $3$ $7$ $13$ $2$. Ответ: $6$ $13$.

Строить весь рейтинг целиком не обязательно, но проще всего именно так и сделать — он собирается из двух независимо отсортированных частей.

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

Вторая часть: студенты с «двойками». Сортируем по количеству «двоек» по возрастанию, при равенстве — по ID. Ровно так и описан порядок в условии: сначала одна «двойка», потом две, три и четыре.

Дальше два ответа. Повышенную стипендию получают первые $N/4$ мест, и по условию гарантируется, что все они попадают в первую часть. Значит нужен элемент рейтинга с номером $N/4$, то есть индекс $N/4 - 1$. Второй ответ — первый в списке студент с более чем двумя «двойками», то есть первый элемент второй части, у которого «двоек» три или четыре.

f = open('26-18.txt')
n = int(f.readline())

passed, failed = [], []
for _ in range(n):
    v = list(map(int, f.readline().split()))
    sid, marks = v[0], v[1:]
    twos = marks.count(2)
    if twos == 0:
        passed.append((-sum(marks), sid))   # балл по убыванию, ID по возрастанию
    else:
        failed.append((twos, sid))          # число двоек, затем ID

passed.sort()
failed.sort()
rating = [sid for _, sid in passed] + [sid for _, sid in failed]

top = rating[n//4 - 1]                                    # последнее место среди 25 %
first_bad = next(sid for twos, sid in failed if twos > 2)

print(top, first_bad)   # 52326 635

Проверка. Студентов $9964$, из них без «двоек» — $6682$, что заметно больше четверти, так что граница стипендии действительно попадает в первую часть. Четверть мест — это $2491$, и на этом месте стоит студент с ID $52326$ и суммой баллов $17$; соседи по рейтингу имеют ту же сумму, но ID $52268$ и $52380$, то есть тай-брейк по возрастанию ID здесь сработал. С тремя «двойками» в файле $195$ студентов, с четырьмя — $15$, и первый из них по ID — $635$. На типовом примере из условия программа выдаёт $6$ и $13$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение