Навигация по странице
Тип 2
Задания второго типа нацелены исключительно на сортировку и отбор нужных значений. Никаких сложных алгоритмов и идей выдумывать здесь не требуется. Весь порядок сортировки описан уже в условии, от вас требуется только проследовать ему и отобрать часть значений по условию.
Этот тип очень хорошо и наглядно решается в редакторе электронных таблиц, но, как уже было сказано ранее – мы пойдём через решение кодом.
Подобные задания максимально приближены к реальным задачам, с которыми сталкиваются программисты, работающие в сфере анализа данных. Для работы с табличными данными в Python обычно применяется библиотека Pandas.
Но нам недоступен выбор сторонних библиотек, так что в своих решениях мы будем представлять данные в виде стандартного списка словарей. Словари позволяют явно отразить зависимость значений в таблице: названию столбца таблицы соответствуют ключи словаря, а данные из ячеек записываются в соответствующие этим ключам значения словаря.
Этот процесс проиллюстрирован ниже: словарь соответствует строке таблицы, ключами словаря являются заголовки столбцов, а значения словаря берутся из соответствующих ячеек.
Такой подход может быть непривычен вам, но он позволяет сделать код более читаемым и лучше ориентироваться в нём. В своих решениях вы можете отказаться от этого и считывать данные в обычные списки.
Перейдём к рассмотрению формулировки 26 задания второго типа:
Задание 2603
«Отбор кандидатов в матросы происходит по сумме баллов трех экзаменов. На заранее известное количество мест отбираются кандидаты, набравшие большую сумму баллов по результатам трех экзаменов. Все кандидаты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше, чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом. Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование, а при равенстве баллов за собеседование – приоритет имеют кандидаты с наименьшими ID.
Для данного множества кандидатов следует определить ID последнего кандидата с набранным проходным баллом, а также каково количество кандидатов, набравших полупроходной балл.
Входные данные
В первой строке входного файла находится два числа N – количество кандидатов (натуральное число, не превышающее 1000) и S – количество имеющихся мест. Каждая из следующих N строк содержит пять чисел: ID кандидата (натуральное число, не превышающее 10 000), соответственно три оценки по экзаменам (все числа целые неотрицательные, не превышающие 100) и балл за собеседование (целое неотрицательное число, не превышающее 10).
Запишите в ответе два целых числа: сначала ID последнего кандидата с набранным проходным баллом, а затем количество кандидатов, набравшие полупроходной балл.
Типовой пример организации данных во входном файле
6 3
1 90 90 90 10
3 60 70 80 8
5 63 60 90 6
8 50 80 100 4
4 40 95 80 7
11 80 63 72 6
При таких входных данных проходной балл равен 230, полупроходной 215, на оставшееся одно место будет назначен кандидат, набравший в сумме 215 баллов и получивший по собеседованию 7 баллов. Ответ для приведённого примера: 8 2»
Формулировка обширная, конечно, но давайте выделим из неё основные моменты, которые помогут нам в решении:
- в файле будет 5 чисел: ID, 3 значения баллов за каждый экзамен и балл за собеседование
- нужно подсчитать сумму баллов за три экзамена
- сначала будет сортировка по убыванию суммы баллов
- далее сортируем значения по убыванию баллов за собеседование: «Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование…»
- последняя сортировка будет по возрастанию ID: «…а при равенстве баллов за собеседование – приоритет имеют кандидаты с наименьшими ID»
- нужно будет определить полупроходной балл
- те, кто получили значения выше полупроходного – зачисляются сразу, ID последнего даём в ответ
- подсчитываем количество тех, кто получил полупроходной балл и даём это количество в качестве второго ответа
Теперь нам будет проще решать это задание. В целом, основная сложность в заданиях этого типа состоит именно в верной интерпретации условия.
Давайте разберём пример из условия и выведем алгоритм решения. Для большей наглядности сделаем это с использованием таблиц, а потом переложим все наши действия на решение кодом.
Сформируем таблицу со значениями из примера в условии:
Добавим еще одну колонку, в которой будем подсчитывать сумму за три экзамена:
Проведём три последовательные сортировки:
- По убыванию суммы баллов
- По убыванию балла за собеседование
- По возрастанию ID
Получим такую таблицу:
В этом примере у нас есть только 3 места. И теперь начинается самое сложное. На третьей позиции в таблице находится кандидат с ID 4. Но дело в том, что число 215 здесь будет полупроходным баллом.
То есть два кандидата с суммой баллов 215 будут конкурировать за последнее место в матросы.
Чтобы понять, кто из них пройдёт отбор, нужно отсортировать список с кандидатами по убыванию баллов за собеседование и возрастанию ID. Но мы это уже сделали заранее – в нашей таблице и так данные расположены в нужном порядке.
Тогда последним принятым в матросы будет кандидат с ID 4.
Теперь можем приступать к формированию ответов. Для ответа на первый вопрос нам нужно найти ID кандидата, сумма баллов которого больше полупроходного балла.
В нашем случае такой кандидат имеет ID 8.
Для ответа на второй вопрос нужно найти всех кандидатов, сумма баллов которых равна полупроходному баллу, то есть 215. Таких кандидатов двое: с ID 4 и 11.
Итак, наши ответы сошлись с теми, что даны к примеру в условии, следовательно, алгоритм составлен верно. Давайте теперь реализуем его в коде.
Сначала создаём список data, в котором будем хранить считанные с файла данные. Открываем нужный файл, первые два числа считываем в переменные N и S.
data = []
with open('2603.txt') as file:
N, S = map(int, file.readline().split())
Далее мы будем в цикле формировать словарь под каждого кандидата с ключами: id, exam_1, exam_2, exam_3 и interview. Каждое значение будем приводить к целому числу.
for line in file:
parts = line.strip().split()
candidate = {
"id" : int(parts[0]),
"exam_1" : int(parts[1]),
"exam_2" : int(parts[2]),
"exam_3" : int(parts[3]),
"interview": int(parts[4])}
В этом же цикле будем вычислять пятый элемент словаря – сумму баллов за экзамены. В конце будем добавлять каждый словарь в список data.
candidate["result"] = candidate["exam_1"] + candidate["exam_2"] + candidate["exam_3"]
data.append(candidate)
Список с данными готов, настало время отсортировать его. Используем функцию sorted() и в качестве ключей передаём кортеж значений – ключей сортировки.
data = sorted(data, key=lambda x: (-x["result"], -x["interview"], x["id"]))
Вычислим полупроходной балл: для этого достаточно будет получить значение по ключу result S-го элемента списка data.
half_pass_mark = data[S]["result"]
Подготовим себе две переменные под ответ:
answer_1 = {}
answer_2 = 0
Проходимся в цикле по словарям-кандидатам из data и сравниваем сумму баллов каждого кандидата с проходным: если сумма баллов, набранная кандидатом, больше полупроходного балла, то перезаписываем словарь answer_1.
Если эта сумма равна полупроходному баллу, то увеличиваем значение в переменной-счётчике answer_2.
При значениях суммы баллов меньших полупроходного балла завершаем цикл – нам эти кандидаты больше неинтересны.
Получаем такой цикл:
for candidate in data:
if candidate["result"] > half_pass_mark:
answer_1 = candidate
if candidate["result"] == half_pass_mark:
answer_2 += 1
if candidate["result"] < half_pass_mark:
break
В конце выводим значения переменных на экран:
print(f'ID последнего кандидата: {answer_1["id"]}')
print(f'Набрали полупроходной балл: {answer_2}')
Полный код для решения этого задания будет следующим:
data = []
with open('2603.txt') as file:
N, S = map(int, file.readline().split())
for line in file:
parts = line.strip().split()
candidate = {
"id" : int(parts[0]),
"exam_1" : int(parts[1]),
"exam_2" : int(parts[2]),
"exam_3" : int(parts[3]),
"interview" : int(parts[4])}
candidate["result"] = candidate["exam_1"] + candidate["exam_2"] + candidate["exam_3"]
data.append(candidate)
data = sorted(data, key=lambda x: (-x["result"], -x["interview"], x["id"]))
half_pass_mark = data[S]["result"]
answer_1 = {}
answer_2 = 0
for candidate in data:
if candidate["result"] > half_pass_mark:
answer_1 = candidate
if candidate["result"] == half_pass_mark:
answer_2 += 1
if candidate["result"] < half_pass_mark:
break
print(f'ID последнего кандидата: {answer_1["id"]}')
print(f'Набрали полупроходной балл: {answer_2}')
Пример
Задание 2604
«Во время сессии студенты сдают 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 студентов в порядке, указанном в условии задачи.
Типовой пример организации данных во входном файле
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»
Аналогичным образом выделим ключевые моменты из условия:
- в файле будет 5 чисел: ID, 4 значения оценок
- нужно подсчитать количество двоек среди всех оценок и вычислить средний балл (среднее арифметическое всех оценок)
- сначала будет сортировка по убыванию среднего балла
- далее сортируем значения по возрастанию количества «двоек»: «Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки»…»
- последняя сортировка будет по возрастанию ID: «Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания»
- нужно найти первую четверть студентов без двоек «первые 25 % мест, при условии отсутствия у них «двоек»», но проверять количество «двоек» не требуется, в первой четверти и так будут только те, у которых нет «двоек» «Гарантируется, что без «двоек» сессию сдали не менее 25 % студентов»
- в конце требуется найти первого студента, у которого больше двух «двоек»
Считывание данных здесь будет почти таким же, как и в прошлом примере, но перед этим импортируем модуль statistics, чтобы не вычислять самостоятельно средний балл.
import statistics
data = []
with open('2604.txt') as file:
N = int(file.readline())
В цикле записываем все оценки и ID каждого студента в словарь, формируем кортеж из всех оценок и ищем в нём количество «двоек». Также на основе данных из этого кортежа вычислим средний балл функцией mean() из модуля statistics.
for line in file:
parts = line.strip().split()
student = {
"id" : int(parts[0]),
"m_1": int(parts[1]),
"m_2": int(parts[2]),
"m_3": int(parts[3]),
"m_4": int(parts[4])}
marks = (student["m_1"], student["m_2"],
student["m_3"], student["m_4"])
student["twos"] = marks.count(2)
student["mean"] = statistics.mean(marks)
data.append(student)
Отсортируем данные:
data = sorted(data, key=lambda x: (-x["mean"], x["twos"], x["id"]))
Определим последнего студента среди первых 25%:
quart = N // 4
answer_1 = data[quart - 1]["id"]
print(answer_1)
И найдём первого студента, у которого больше двух «двоек»:
for student in data:
if student["twos"] > 2:
print(student["id"])
break
Код к этому заданию получается такой:
import statistics
data = []
with open('2604.txt') as file:
N = int(file.readline())
for line in file:
parts = line.strip().split()
student = {
"id" : int(parts[0]),
"m_1": int(parts[1]),
"m_2": int(parts[2]),
"m_3": int(parts[3]),
"m_4": int(parts[4])}
marks = (student["m_1"], student["m_2"],
student["m_3"], student["m_4"])
student["twos"] = marks.count(2)
student["mean"] = statistics.mean(marks)
data.append(student)
data = sorted(data, key=lambda x: (-x["mean"], x["twos"], x["id"]))
quart = N // 4
answer_1 = data[quart - 1]["id"]
print(answer_1)
for student in data:
if student["twos"] > 2:
print(student["id"])
break
А в ответ запишем два числа – 52326 и 635.