В этой статье разберём решение некоторых прототипов задания № 26 из ЕГЭ по информатике с помощью сортировки целочисленной информации в Excel.

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

Шаг 1. Чтение данных из файла

Способ 1

Нам даётся текстовый файл. Сочетанием клавиш Ctrl + A и Ctrl + C копируем всё его содержимое, затем открываем лист в Excel и вставляем значения через Ctrl + V.

Чтобы несколько чисел не оказались в одной ячейке, на верхней панели заходим в «Данные» и выбираем «Текст по столбцам». Откроется окно, где нужно выполнить два действия: на шаге 1 выбрать вариант «С разделителями», на шаге 2 отметить среди разделителей все предложенные и нажать «Далее». Поскольку значения были вставлены до применения этих настроек, форматирование не отобразилось на столбце — нажимаем Ctrl + V ещё раз, и теперь всё разделяется по ячейкам.

Способ 2

На верхней панели выбираем «Файл» → «Открыть» и указываем нужный файл. После этого Excel сразу предложит разделить текст по столбцам — выполняем те же шаги, что и в первом способе.

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

Задание 1

Флэш устроился работать системным администратором и раз в неделю создаёт архив пользовательских файлов. Объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные
В первой строке входного файла 26_3.txt находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Выходные данные
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранен в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера: 2 50. [i]

Разберём логику задания на типовом примере.

Чтобы поместить в архив как можно больше пользователей, нужно брать наименьшие объёмы файлов. Для этого сортируем все объёмы по возрастанию и берём их подряд, пока не закончится свободное место (значение S).
Затем пытаемся увеличить объём последнего взятого файла — заменить его на файл побольше, который всё ещё помещается в оставшееся место.
Перед сортировкой вырежем первую строку (с числами S и N) и вставим её отдельно, чтобы сортировка её не затронула. Затем через вкладку «Данные» → «Сортировка» сортируем столбец A по возрастанию.
Выделяем несколько ячеек и начинаем медленно двигать мышку вниз — справа снизу начнёт увеличиваться сумма. Доходим до значения, при котором сумма максимально близка к S. Считаем, сколько чисел сложилось, чтобы получить эту сумму, — это и есть первый ответ; в нашем случае 3867.
Найдём, сколько места осталось: вычтем сумму первых 3867 значений из S: 77550 − 77524 = 26. Значит, самый большой файл, который можно взять вместо последнего, — это объём последнего взятого файла плюс оставшееся место: 40 + 26 = 66. Проверим, есть ли файл объёмом 66 в исходных данных: он есть. Значит, вместо последнего файла (объёмом 40) можно взять файл объёмом 66 — число сохранённых файлов не изменится, а максимальный объём при этом условии составит 66.

Ответ: 3867 66.

Подготовка к экзаменам в 100балльном репетиторе

Задание 2

Отбор абитуриентов в вуз происходит по сумме баллов трёх экзаменов: по русскому языку, математике и физике. На заранее известное количество мест зачисляются абитуриенты, набравшие большую сумму баллов по результатам трёх экзаменов. Все абитуриенты, набравшие определённую сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест абитуриентами с проходным баллом остаются незаполненные места, но абитуриентов, набравших следующую сумму баллов, больше, чем вакантных мест, набранная этими абитуриентами сумма баллов называется полупроходным баллом. Из числа абитуриентов, набравших полупроходной балл, на имеющиеся места принимаются абитуриенты, имеющие более высокий балл по математике, а при равенстве баллов по математике — по физике. Для данного множества абитуриентов следует определить, какая сумма баллов является полупроходным баллом и какой балл по математике необходимо набрать, чтобы быть зачисленным на имеющиеся места.
Входные данные
В первой строке входного файла находится два числа N — количество поданных заявлений о приёме (натуральное число, не превышающее 1000) и S — количество имеющихся мест. В следующих N строках три оценки по русскому языку, математике и физике соответственно, разделённые пробелами (все числа натуральные, не превышающие 100), оценки каждого абитуриента в отдельной строке.
Выходные данные
Запишите в ответе два целых числа: сначала полупроходной балл, затем оценку по математике, необходимую для зачисления при условии набранного полупроходного балла.
Типовой пример организации данных во входном файле:
4 2
60 70 80
65 60 90
50 80 100
40 95 80
При таких исходных данных проходной балл равен 230, полупроходной — 215, на оставшееся одно место будет зачислен абитуриент, набравший в сумме 215 баллов и получивший по математике 95 баллов. Ответ для приведённого примера: 215 95. [i]

В первую очередь, как и в реальной жизни, нас интересует общая сумма набранных баллов, поэтому в столбце D с помощью функции =СУММ() посчитаем её и отсортируем по убыванию. По условию, если количество набранных баллов окажется равным, вуз принимает того абитуриента, у которого больше баллов по математике (столбец B), а при их равенстве — по столбцу с баллами по физике (под буквой A). Сделаем несколько уровней сортировки, каждый из которых зависит от предыдущего:
Выбрав первые 224 места, заметим, что 256 — это проходной балл (с ним абитуриент проходит наверняка), а при 255 баллах часть абитуриентов проходит, а часть — нет. Это и есть полупроходной балл.
Поскольку сортировка уже сделана, смотрим на ячейку B224 — в ней минимальный балл по математике, с которым абитуриент с полупроходным баллом ещё проходит.

Ответ: 255 88.

Задание 3

Отбор космонавтов в космическую миссию происходит по сумме баллов за два теста и собеседование. На заранее известное количество мест отбираются космонавты, набравшие большую сумму баллов по результатам трёх испытаний. Все космонавты, набравшие определённую сумму баллов или больше, отбираются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест космонавтов с проходным баллом остаются незаполненные места, то космонавтов, набравших следующую сумму баллов, больше, чем вакантных мест, набранная этими космонавтами сумма баллов называется полупроходным баллом. Из числа космонавтов, набравших полупроходной балл, на имеющиеся места принимаются космонавты, имеющие более высокий балл за собеседование, а при равенстве баллов за собеседование — по id. Для данного множества космонавтов следует определить id последнего отобранного космонавта и количество космонавтов, отобранных с полупроходным баллом.
Входные данные
В первой строке входного файла находится два числа: N — количество поданных заявлений о приеме (натуральное число, не превышающее 1000) и S — количество имеющихся мест. В следующих N строках четыре значения: уникальный id космонавта, оценка за первый тест, за второй тест и за собеседование.
Выходные данные
Запишите в ответе два целых числа: сначала id последнего отобранного космонавта, затем — общее количество космонавтов, отобранных с полупроходным баллом. [i]

В первую очередь посчитаем общее количество набранных баллов в столбце E, не учитывая столбец А, так как в нём указан id. Затем сразу зададим полную сортировку по условию: по убыванию суммы баллов, далее по убыванию баллов за собеседование и наконец по возрастанию id (нас интересуют наименьшие id):
Заметим, что 256 — проходной балл, а 255 — полупроходной. Тогда с полупроходным будет отобран 21 человек, а 8252 — id последнего отобранного, так как мы уже применили всю сортировку.

Ответ: 8252 21.

Заключение

Задание № 26 удобно решать в редакторе таблиц через сортировку. Общая схема такая: загружаем данные и разбиваем их по столбцам, при необходимости считаем сумму нужных полей, а затем сортируем — иногда по нескольким уровням сразу, в точности повторяя приоритеты из условия. После сортировки нужные значения (число элементов, проходной и полупроходной баллы, последний подходящий объём или id) оказываются на предсказуемых местах, и остаётся только их считать.