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

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

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

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

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

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

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

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

В первой строке входного файла находятся два натуральных числа, не превышающих 10 000, через пробел: число N – количество кандидатов и число K – количество мест в отряде. В следующих 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.

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

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

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

КЭС:

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

Тип ответа:

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

Номер: EB601E

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

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

Ответ: 45539 127

Решение.

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

В файле 9996 кандидатов и 1076 мест. Сумма рейтинга включает все четыре результата, в том числе собеседование. Сортируем по убыванию суммы, затем по убыванию результата собеседования, затем по возрастанию ID.

Зачисление рассматриваем от начала этого рейтинга, как указано в правиле убывания суммы и показано в примере условия. Кандидатов с одинаковой суммой объединяем в группы. Пока вся следующая группа помещается в оставшиеся места, зачисляем её целиком.

Последняя целиком помещающаяся группа задаёт проходной балл. Первый ответ — ID последнего кандидата именно этой группы с учётом собеседования и ID. Если после неё остались места, но следующая группа целиком не помещается, её сумма полупроходная. Во втором ответе нужно количество всех кандидатов этой группы, включая тех, кому мест не хватило.

Если граница мест совпала с концом группы, полупроходного балла нет и второе число равно 0. Нельзя автоматически считать последнего зачисленного кандидата последним с проходным баллом: он может принадлежать частично зачисленной группе. Сортировка O(N log N), проход по группам O(N), память O(N).

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

from itertools import groupby
with open("data.txt", encoding="utf-8-sig") as f:
    n, places = map(int, f.readline().split())
    people = [list(map(int, f.readline().split())) for _ in range(n)]
people.sort(key=lambda row: (-sum(row[1:]), -row[4], row[0]))
admitted = 0
last_passing = None
semi_count = 0
for score, iterator in groupby(people, key=lambda row: sum(row[1:])):
    group = list(iterator)
    if admitted + len(group) <= places:
        admitted += len(group)
        last_passing = group[-1][0]
    else:
        if admitted < places:
            semi_count = len(group)
        break
print(last_passing, semi_count)

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

Целиком зачислено 955 кандидатов; проходная сумма 280. Последний кандидат этой суммы имеет запись 45539, 95, 95, 90, 0. Следующая группа имеет сумму 279 и состоит из 127 кандидатов; оставшихся 121 мест на всю группу не хватает.

Ответ: 45539 127.

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

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

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

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