Задание №26 ЕГЭ Информатика с ответом и решением
Ответ: 459 45
Условие
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 2000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов — 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50
Подсказки — как подойти к решению
- Ответ содержит два числа: сначала количество сохранённых файлов, затем максимальный размер одного из сохранённых. Порядок именно такой, иначе ответ не засчитают.
- После набора минимальных объёмов выясни, насколько можно увеличить самый большой из выбранных файлов: освободив его объём и добавив остаток места, примеряй более крупные файлы из оставшихся.
Решение
Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с размером свободного места на диске, получим максимальное количество пользователей, чьи файлы могут поместиться на диске. Далее, вычитая из найденной суммы наибольший файл в текущей последовательности, будем пробовать прибавлять файлы с большим весом. Если такой файл будет найден, то заменяем значение наибольшего файла, который возможно поместить на диск.
Приведём решение на языке Pascal.
var
i, j, t: integer;
a: array [1..2000] of integer;
s: integer;
n: integer;
sum: integer;
maxi: integer;
f: text;
begin
assign(f,'C:\27887.txt');
reset(f);
readln(f, s, n);
for i := 1 to n do readln(f, a[i]);
for i := 1 to n do
for j := i + 1 to n do
if a[i] > a[j] then begin
t := a[i];
a[i] := a[j];
a[j] := t;
end;
sum := 0;
maxi := 1;
for i := 1 to n do
if sum + a[i] <= s then begin
sum := sum + a[i];
maxi := i;
end;
t := a[maxi];
for i := maxi to n do
if ((sum - t) + a[i]) <= s then begin
sum := sum - t + a[i];
t := a[i];
end;
writeln(maxi, ' ', t);
end.
Ответ: 459 45.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open('27887.txt')
data = f.readlines()
s = data[0].split()
s = int(s[0])
del (data[0]) # первая строка больше не нужна, удаляем ее
for i in range(0, len(data)):
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]
print(count)
zapas = s - summa
for i in range(0, len(data)):
if data[i] - data[count - 1] <= zapas:
itog = data[i]
print(itog)
Приведём решение Евгений Петченко на языке Python.
files = sorted([int(i) for i in open('27887.txt').readlines()[1:]])# считывание всех строк кроме первой и преобразование к числам
memory = int(open('27887.txt').readline().split()[0])# считывание количества памяти
files_size = []# список для хранения выбранных файлов
for file in files:
if memory - file > 0:# если достаточно памяти для файла
files_size.append(file)# добавляем файл в архив
memory -= file# вычитаем размер файла из памяти
else:
break
print(len(files_size), memory+max(files_size))# выводим количество файлов, а также размер самого большого файла, прибавленного к остатку памяти
Типичные ошибки
- Второе число уменьшено: при замене нужно учитывать весь объём выбранного файла плюс остаток свободного места. Считай по схеме «сумма минус старый файл плюс новый».
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №26 по информатике