7257B4 — Сортировка, отбор и моделирование: ответ и решение

Впишите правильный ответ.

Рисунок из условия ФИПИ

Задание выполняется с использованием прилагаемых
файлов.

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

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

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

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

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

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

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

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

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.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Скачать файл задания (TXT, ФИПИ)

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве

Тип ответа:

Краткий ответ

Номер: 7257B4

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINF7257B4

Ответ: 52326 635

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

Количество студентов N = 9964. На стипендию претендуют первые 9964 : 4 = 2491 мест общего рейтинга. По условию столько студентов без двоек обязательно есть.

Разделим записи по наличию оценки 2. Для сдавших сортируем по убыванию суммы четырёх оценок, при равенстве по возрастанию ID. Деление суммы на 4 для среднего не требуется: одинаковый положительный делитель сохраняет порядок и равенства.

Для не сдавших сортировка другая: количество двоек по возрастанию, затем ID по возрастанию. Сумма оценок в этой части не является дополнительным критерием. Искомый второй студент — первый в таком списке с тремя или четырьмя двойками, а не просто с любой двойкой.

Первый ответ берём из списка сдавших на позиции N : 4 − 1 при индексации с нуля. Второй находим последовательным просмотром отсортированного списка не сдавших. Две независимые сортировки точно воспроизводят две части рейтинга. Время O(N log N), память O(N).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    students = [list(map(int, f.readline().split())) for _ in range(n)]
passed = [row for row in students if 2 not in row[1:]]
failed = [row for row in students if 2 in row[1:]]
passed.sort(key=lambda row: (-sum(row[1:]), row[0]))
failed.sort(key=lambda row: (row[1:].count(2), row[0]))
places = divmod(n, 4)[0]
first = passed[places - 1][0]
second = next(row[0] for row in failed if row[1:].count(2) > 2)
print(first, second)

Проверка результата.

Последний стипендиат имеет ID 52326 и оценки 4, 5, 3, 5, сумма 17. Его место 2491. Первый студент с более чем двумя двойками имеет ID 635 и оценки 2, 2, 5, 2; двоек 3. При равенствах проверен порядок ID.

Ответ: 52326 635.

Задание EGEINF7257B4: Сортировка, отбор и моделирование

Решение задания EGEINF7257B4

Помочь улучшить сайт

Комментарии к решению