Задание №26 ЕГЭ Информатика с ответом и решением
Ответ: 611 27
Условие
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 4000). В следующих 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..4000] of integer;
s: integer;
n: integer;
sum: integer;
maxi: integer;
f: text;
begin
assign(f,'C:\27880.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.
Приведём решение Владислава Маталина на языке Python.
f = open('27880.txt')
s, n = map(int, f.readline().split())
v = sorted(map(int, f))
sum, cnt = 0, 0
for i in range(len(v)):
if sum + v[i] <= s:
sum += v[i]
cnt += 1
biggest_file = v[cnt - 1:][0] + s - sum
while biggest_file not in v:
biggest_file -= 1
print(cnt, biggest_file)
Ответ: 611 27.
Приведём решение Юрия Лысакова на языке Python.
f = open('27880.txt')
s = int(f.readline().split()[0])
a = [int(i) for i in f]
a.sort()
s1 = 0
for i in range(0,len(a)):
if s1 + a[i] > s: break
s1 += a[i]
i1 = i
s2 = s1 - a[i1]
for j in range(i1, len(a)):
if s2 + a[j] > s: break
p = a[j]
print(i1 + 1,p)
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильников а на языке Python.
f = open('27880.txt')
место, _ = map(int,f.readline().split())
файлы = sorted([int(s) for s in f], reverse=True)
пользователи = 0
while файлы and место >= файлы[-1]: # добавляем файлы, пока есть файлы и место
пользователи += 1
последний = файлы.pop()
место -= последний
# вернём последний файл назад и увеличим место на его размер
место += последний
файлы.append(последний)
# ищем самый большой файл, который поместится
наибольший = max([x for x in файлы if x <= место])
print(пользователи, наибольший)
Типичные ошибки
- Ответ записан в обратном порядке: сначала указывают наибольшее число пользователей, а затем максимальный размер файла, который может быть сохранён.
- Счётчик увеличен на файл, который в оставшееся место не влезает. Перед добавлением сравнивай со свободным местом сумму всех выбранных файлов вместе с очередным, а не только сам файл.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №26 по информатике