ЕГЭ · задание с файлом

Задание 26 ЕГЭ по информатике — обработка данных: сортировка и жадные алгоритмы

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

39заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 26 ЕГЭ

В файле — список объектов (размеры файлов, массы грузов, заявки, места в зале). Нужно выбрать максимальное число объектов при ограничении, а затем — наибольший возможный элемент при этом максимальном количестве. Главный приём — сортировка и жадный выбор: сначала берём самые маленькие, затем пробуем заменить последний на как можно больший.

КЕГЭ, задание 26к заданию прилагается файл39 заданий в банке ИнфДоски

Типичные ошибки

  • Не сортируют данные и берут объекты в порядке файла.
  • Находят максимальное количество, но не улучшают второй ответ (наибольший элемент).
  • Заменяют последний элемент на больший, не проверив, что сумма не превысит объём.
  • Путают первую строку файла (параметры) с данными.

Пример с решением

Условие

На диске свободно 100 Мбайт, есть файлы размером 30, 15, 50, 8, 22, 40, 12 Мбайт. Нужно сохранить максимальное число файлов, а среди всех таких наборов — с наибольшим возможным размером самого большого файла. Запишите количество файлов и размер наибольшего файла.

Решение

Сортируем: 8, 12, 15, 22, 30, 40, 50. Берём по возрастанию: 8 + 12 + 15 + 22 = 57, + 30 = 87, + 40 уже больше 100 — максимум 5 файлов. Теперь убираем самый большой из набора (30): свободно 100 − 57 = 43 Мбайт, наибольший подходящий файл — 40. Ответ: 5 40.

files = sorted([30, 15, 50, 8, 22, 40, 12])
cap = 100
k = s = 0
while k < len(files) and s + files[k] <= cap:
    s += files[k]
    k += 1
rest = s - files[k - 1]
biggest = max(f for f in files[k - 1:] if rest + f <= cap)
print(k, biggest)
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 5 40

Задания из банка

В банке ИнфДоски 39 заданий этого номера с файлами. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Обработка данных (сортировка) Открыть на доске →

В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы.

По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно 13 идущих подряд свободных мест для посадки новых сосен, таких, что непосредственно слева и справа от них в том же ряду растут сосны. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: наибольший номер ряда и наименьший номер места для посадки из числа найденных в этом ряду подходящих последовательностей из 13 свободных мест.

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

В первой строке входного файла находится число N — количество прижившихся саженцев сосны (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места в этом ряду, на котором растёт деревце.

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

Два целых неотрицательных числа: наибольший номер ряда и наименьший номер места в выбранной последовательности из 13 мест, подходящих для посадки новых сосен.

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

7
40 3
40 7
60 33
50 125
50 129
50 68
50 72

Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.

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

Ответ
59966,50449
Задание 2 Обработка данных (сортировка) Открыть на доске →

В кондитерской есть N круглых форм для коржей. Специализация кондитерской – многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 4 единицы меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.

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

В первой строке входного файла находится число N – количество форм для коржей в кондитерской (натуральное число, не превышающее 10 000). В следующих N строк находятся значения диаметров форм для коржей (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.

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

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

5
43
40
32
40
30

Пример входного файла приведён для пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящих для изготовления многоярусного торта, составляет 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32.

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

Ответ
2172,50
Задание 3 Обработка данных (сортировка) Открыть на доске →

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 11 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.

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

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

5
43
40
32
40
30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

Ответ
854,54
Задание 4 Обработка данных (сортировка) Открыть на доске →

Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительно от 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) — натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке выше стоит участник с б´oльшими баллами за собеседование, а при равенстве и этих баллов — с меньшим 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.

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

Ответ
45539,127
Задание 5 Обработка данных (сортировка) Открыть на доске →

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 6 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

В первой строке входного файла находится число N — количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.

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

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

5
43
40
32
40
30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

Ответ
1511,54
Задание 6 Обработка данных (сортировка) Открыть на доске →

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

В первой строке входного файла находится число N — количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.

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

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

5
43
40
32
40
30

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

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

Ответ
1040,57
Задание 7 Обработка данных (сортировка) Открыть на доске →

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить билет на такое место в ряду, чтобы перед ним как можно больше идущих подряд кресел с таким же номером было свободно. Если места, удовлетворяющие этому условию, есть в нескольких рядах, то нужно выбрать ряд, расположенный как можно ближе к сцене. В ответе запишите два целых числа: искомый номер ряда и количество свободных кресел перед выбранным местом. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одно такое место в зале есть.

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

В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10 000), M — количество рядов (целое положительное число, не превышающее 100 000) и K — количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе — K).

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

Два целых положительных числа: искомый номер ряда и количество свободных кресел перед выбранным местом.

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

9 6 7
1 1
2 4
3 6
6 1
4 3
5 5
5 2
6 6
4 7

При таких исходных данных условию задачи удовлетворяют места (ряд, место): 5, 1; 4, 2; 6, 4; 4, 5. Перед этими местами три подряд кресла свободны. Ответом является пара чисел 4 и 3.

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

Ответ
33520,33406
Задание 8 Обработка данных (сортировка) Открыть на доске →

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 10 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

В первой строке входного файла находится число N — количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.

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

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

5
43
40
32
40
30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

Ответ
935,51
Задание 9 Обработка данных (сортировка) Открыть на доске →

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить билет на такое место в ряду, чтобы перед ним как можно больше идущих подряд кресел с таким же номером было свободно. Если места, удовлетворяющие этому условию, есть в нескольких рядах, то нужно выбрать ряд, расположенный как можно ближе к сцене. В ответе запишите два целых числа: искомый номер ряда и количество свободных кресел перед выбранным местом. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одно такое место в зале есть.

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

В первой строке входного файла находятся три числа: N — количество занятых мест в зале (целое положительное число, не превышающее 10 000), M — количество рядов (целое положительное число, не превышающее 100 000) и K — количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе — K).

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

Два целых положительных числа: искомый номер ряда и количество свободных кресел перед выбранным местом.

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

9 6 7
1 1
2 4
3 6
6 1
4 3
5 5
5 2
6 6
4 7

При таких исходных данных условию задачи удовлетворяют места (ряд, место): 5, 1; 4, 2; 6, 4; 4, 5. Перед этими местами три подряд кресла свободны. Ответом является пара чисел 4 и 3.

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

Ответ
68217,33508
Задание 10 Обработка данных (сортировка) Открыть на доске →

На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы. Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?

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

В первой строке входного файла находятся два числа: S — грузоподъёмность судна (натуральное число, не превышающее 100 000) и N — количество контейнеров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения масс контейнеров, требующих транспортировки (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

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

Пример входного файла

100 4
80
30
50
40

При таких исходных данных можно транспортировать за один раз максимум 2 контейнера. Возможные массы этих двух контейнеров 30 и 40, 30 и 50 или 40 и 50. Поэтому ответ для приведённого примера: 2 50.

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

Ответ
1612,90
ИнфДоска

Разбирайте задание 26 ЕГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ЕГЭ