На уроке рассмотрен материал для подготовки к ЕГЭ по информатике, разбор 26 задания. Объясняется тема о программной обработке целочисленной информации с использованием алгоритмов сортировки.
ЕГЭ по информатике 26 задание объяснение
26-е задание: «Обработка целочисленной информации с использованием сортировки»
Уровень сложности — высокий,
Требуется использование специализированного программного обеспечения — да,
Максимальный балл — 2,
Примерное время выполнения — 35 минут.
Проверяемые элементы содержания: Умение обрабатывать целочисленную информацию с использованием сортировки
Выполнение 26 задания ЕГЭ
Плейлист видеоразборов задания на YouTube: 
Задание демонстрационного варианта 2022 года ФИПИ
26_1.
26_1. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Задание выполняется с использованием прилагаемых файлов
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
2 | 50
Ответ: 568 | 50
✍ Решение:
Проанализируем возможное решение:
- Чтобы вычислить максимальное число пользователей, чьи файлы можно сохранить в архиве, необходимо брать файлы с наименьшим объемом , пока суммарный объем этих файлов меньше свободного объема диска. Т.е. для нижеуказанного примера, будем брать
30 + 40. Файл объемом 50 мы взять уже не сможем, так как 70 + 50 = 120, а это уже больше указанного объема диска (100):
100 4
80
30
50
40
Таким образом, мы получили первый ответ — максимальное число пользователей, чьи файлы можно сохранить в архиве — ответ 2.
Далее необходимо вычислить максимальный размер имеющегося файла, который может быть сохранён в архиве. Для начала вспомним, что у нас оставался «запас» пространства диска при предыдущем расчете. Давайте вычислим этот запас:
100 - 70 = 30
Т.е. мы можем добавить 30 наибольшему возможному числу, из выбранных чисел, чтобы полученная сумма не превысила этот запас. Самое большое число из выбранных — это 40 (30, 40):
30 - 40 <= запаса (30)
40 - 40 <= запаса (30)
50 - 40 <= запаса (30)
80 - 40 > запаса (30), не подходит
Таким образом, наибольшее подходящее число — максимальный размер файла — это 50.
Теперь построим алгоритм на языках программирования:
PascalABC.net:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| begin
var f: text;
assign(f, 'proba.txt');
reset(f);
var s, n: integer;
read(f, s); // 100
read(f, n); //4 var (s, n) := ReadInteger2;
var i := 0;
var data: array of integer;
data := new integer[n];
while not EOF(f) do //
begin
readln(f, data[i]); // var data:= ReadArrInteger(n);
i += 1;
end;
data.Sort;
var summa := 0;
var count := 0;
for count := 0 to data.Length do
begin
if summa + data[count] > s then break;
summa += data[count];
end;
print(count);
var itog := 0;
var zapas := s - summa;
for i := 0 to data.Length do
if data[i] - data[count - 1] <= zapas then
itog := data[i] else break;
print(itog)
end. |
begin
var f: text;
assign(f, 'proba.txt');
reset(f);
var s, n: integer;
read(f, s); // 100
read(f, n); //4 var (s, n) := ReadInteger2;
var i := 0;
var data: array of integer;
data := new integer[n];
while not EOF(f) do //
begin
readln(f, data[i]); // var data:= ReadArrInteger(n);
i += 1;
end;
data.Sort;
var summa := 0;
var count := 0;
for count := 0 to data.Length do
begin
if summa + data[count] > s then break;
summa += data[count];
end;
print(count);
var itog := 0;
var zapas := s - summa;
for i := 0 to data.Length do
if data[i] - data[count - 1] <= zapas then
itog := data[i] else break;
print(itog)
end. |
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| f = open('26.txt')
data = f.readlines() # массив строк , readlines
s = data[0].split() # ['8200', '970']
s = int(s[0]) # 8200 - объем св места на диске
del(data[0]) # первая строка больше не нужна, удаляем ее
for i in range(0, len(data)): # цикл для преобразования в int
data[i]=int(data[i])
data=sorted(data) # сортируем полученный массив для удобства работы
summa = 0
for count in range (0,len(data)):
if summa + data[count] > s: break # если сумма больше - прерываем цикл
summa += data[count] # формируем сумму, добавляя отсортированные элементы
# как только сумма превысила s, произойдёт выход из цикла по оператору break,
# а в переменной count останется количество добавленных значений
print (count) # макс число файлов в архиве
# вычисляем запас, который мы можем уменьшить с помощью замены одного выбранного значения на другое:
zapas = s - summa
# теперь выбираем из массива данных те значения, которые могут быть выбраны:
# разность между таким значением и наибольшим выбранным элементом data[count-1] должна быть не больше, чем zapas:
for i in range (0,len(data)):
if data[i] - data[count-1] <= zapas:
itog = data[i]
print(itog) # максимальный размер файла |
f = open('26.txt')
data = f.readlines() # массив строк , readlines
s = data[0].split() # ['8200', '970']
s = int(s[0]) # 8200 - объем св места на диске
del(data[0]) # первая строка больше не нужна, удаляем ее
for i in range(0, len(data)): # цикл для преобразования в int
data[i]=int(data[i])
data=sorted(data) # сортируем полученный массив для удобства работы
summa = 0
for count in range (0,len(data)):
if summa + data[count] > s: break # если сумма больше - прерываем цикл
summa += data[count] # формируем сумму, добавляя отсортированные элементы
# как только сумма превысила s, произойдёт выход из цикла по оператору break,
# а в переменной count останется количество добавленных значений
print (count) # макс число файлов в архиве
# вычисляем запас, который мы можем уменьшить с помощью замены одного выбранного значения на другое:
zapas = s - summa
# теперь выбираем из массива данных те значения, которые могут быть выбраны:
# разность между таким значением и наибольшим выбранным элементом data[count-1] должна быть не больше, чем zapas:
for i in range (0,len(data)):
if data[i] - data[count-1] <= zapas:
itog = data[i]
print(itog) # максимальный размер файла |
|
С++:
|
Ответ: 568 | 50
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
26_2.
26_2:
Задание выполняется с использованием прилагаемых файлов
В магазине электроники раз в месяц проводится распродажа. Из всех товаров выбирают K товаров с самой большой ценой и делают на них скидку в 20%. По заданной информации о цене каждого из товаров и количестве товаров, на которые будет скидка, определите цену самого дорогого товара, не участвующего в распродаже, а также целую часть от суммы всех скидок.
Входные и выходные данные.
В первой строке входного файла 26-k1.txt находятся два числа, записанные через пробел: N – общее количество цен (натуральное число, не превышающее 10 000) и K – количество товаров со скидкой. В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке.
Запишите в ответе два числа: сначала цену самого дорогого товара, не участвующего в распродаже, а затем целую часть от суммы всех скидок.
Пример входного файла:
10 3
1800
3600
3700
800
2600
2500
1800
1500
1900
1200
При таких исходных данных ответ должен содержать два числа – 2500 и 1980.
Пояснение: скидка будет на товары стоимостью 3700, 3600, 2600. Тогда самый дорогой товар без скидки стоит 2500, а сумма скидок 740+720+520 = 1980.
Ответ: 9000 | 190680
✍ Решение:
Теперь построим алгоритм на языках программирования:
PascalABC.net:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| begin
var f: text;
assign(f, '26-k1.txt');
reset(f);
var n, k: integer;
read(f, n); // 10
read(f, k); //3
var i := 0;
var data: array of integer;
data := new integer[n];
while not EOF(f) do //
begin
readln(f, data[i]); // var data:= ReadArrInteger(n);
i += 1;
end;
SortDescending(data);
var summa := 0.0;
for var j := 0 to k-1 do
begin
summa += data[j]*0.2; // сумма всех скидок
end;
print(data[k],summa)
end. |
begin
var f: text;
assign(f, '26-k1.txt');
reset(f);
var n, k: integer;
read(f, n); // 10
read(f, k); //3
var i := 0;
var data: array of integer;
data := new integer[n];
while not EOF(f) do //
begin
readln(f, data[i]); // var data:= ReadArrInteger(n);
i += 1;
end;
SortDescending(data);
var summa := 0.0;
for var j := 0 to k-1 do
begin
summa += data[j]*0.2; // сумма всех скидок
end;
print(data[k],summa)
end. |
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| f = open('26-k1.txt')
data = f.readlines()
s = data[0].split()
nPrice=int(s[0]) # количество цен
k = int(s[1]) # количество товаров с самой большой ценой
del(data[0])
for i in range (0, len(data)): # переводим в целые числа
data[i] = int(data[i])
print(data)
data = sorted(data,reverse=True) # или data.sort(reverse = True)
summa = 0
for i in range(0,k):
summa+=data[i]*0.2 # 10000 10000 10000
print(data[k],int(summa)) # data[k] - самый дорогой товар, так как k уже не входит в счетчик цикла |
f = open('26-k1.txt')
data = f.readlines()
s = data[0].split()
nPrice=int(s[0]) # количество цен
k = int(s[1]) # количество товаров с самой большой ценой
del(data[0])
for i in range (0, len(data)): # переводим в целые числа
data[i] = int(data[i])
print(data)
data = sorted(data,reverse=True) # или data.sort(reverse = True)
summa = 0
for i in range(0,k):
summa+=data[i]*0.2 # 10000 10000 10000
print(data[k],int(summa)) # data[k] - самый дорогой товар, так как k уже не входит в счетчик цикла |
|
С++:
|
📹 YouTube здесь
📹 Видеорешение на RuTube здесь
Вместо цикла для преобразования в int можно просто data = list(map(int, data))
Ещё можно написать data = [int(i) for I in data]