ЕГЭ по информатике 2021 - Задание 26 (Сортировка)

Сегодняшний урок посвящён 26 заданию из ЕГЭ по информатике 2021. На нём мы будем тренировать умение обрабатывать целочисленную информацию с использованием сортировки.

Сортировка - это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.

Приступим к практике 26 задания из ЕГЭ по информатике.

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

Известно, какой объём занимает файл каждого пользователя.

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

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

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

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

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

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

Напишем решение на Pascal ABC.

const n = 970; //Заводим константу, это будет длина массива
var
  f: text;
  i, j, k, s, sum, count, count2 : integer;
  m: array[1..n] of integer; //Заводим массив
    
begin
  assign(f, 'c:\26.txt');
  reset(f);
  
  readln(f, s);  
  
  // Записываем данные в массив. 
  for i:=1 to n do begin 
        readln(f, m[i]);
  end; 
    
  //Сортируем массив по возрастанию методом Пузырька  
  for i:=1 to n-1 do begin
    for j:=1 to n-i do begin
      if m[j]>m[j+1] then begin
        k:=m[j];
        m[j]:=m[j+1];
        m[j+1]:=k;
      end;
    end;
  end;
  
  sum:=0;
  count:=0;
  
  //Ищем максимальное количество файлов
  for i:=1 to n do begin
    if sum+m[i] <= s then begin
    count := count+1;
    sum := sum + m[i];
    end
    else break;
  end; 
  
  
  // Ищем максимальный размер файла
  // при максимальном количестве файлов.
  for i:=n downto 1 do begin
    
      sum:=m[i];
      count2:=0;  
     
     for j:=1 to n do begin
      if sum+m[j] <= s then begin
      count2 := count2+1;
      sum := sum + m[j];
      end
      else break;
    end;
    
    if count = count2+1 then break;
    
  end;
  
  Writeln(count);
  Writeln(m[i]);
 
  close (f);
end.

Каждое значение, которое показывает размер файла, сохраним в массиве.

Количество файлов можно посмотреть в самом файле к задаче. Это второе число в первой строчке. В нашей случае это число 970.

Затем отсортируем массив по возрастанию с помощью метода Пузырька. По данному методу есть статья на моём сайте.

Суммарный размер файлов не должен превышать значения 8200 (первое число в первой строчке). Нам нужно понять, а сколько максимум файлов можно сохранить. Т.к. после сортировки у нас в начале массива числа самые маленькие, то мы начинаем их суммировать в переменную sum, проверяя, чтобы значение этой переменной не превышало 8200. Так мы в переменной count получим максимальное количество файлов, которое можно уместить на диске.

Нам нужно написать так же написать в ответе максимальный размер файла при максимальном количестве файлов, который можно сохранить. Это не значит, что мы должны искать максимальный размер только среди тех чисел, которые участвовали, когда мы подсчитывали максимальное количество файлов. Возможно, найдётся один файл такой, при котором, количество будет такое же, но сам размер файла будет больше, чем те, которые мы рассматривали.

Чтобы найти максимальный размер файла проходим массив уже с наибольших чисел. Если количество файлов будет таким же, как и с исследуемым файлом, то мы нашли то что нужно.

(№ 2639) (А.М. Кабанов) Спутник «Фотон» проводит измерения солнечной активности, результат каждого измерения представляет собой натуральное число. Перед обработкой серии измерений из неё исключают K наибольших и K наименьших значений (как недостоверные). По заданной информации о значении каждого из измерений, а также количестве исключаемых значений, определите наибольшее достоверное измерение, а также целую часть среднего значения всех достоверных измерений.

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

Источник: https://kpolyakov.spb.ru/

Напишем решение на Pascal ABC.

const n = 1000; //Заводим константу, это будет длина массива
var
  f: text;
  i, j, l, k, sr, max, sum : integer;
  m: array[1..n] of integer; //Заводим массив
    
begin
  k:=50;
  assign(f, 'c:\26-k2.txt');
  reset(f);
  
  // Считываем первую строчку, чтобы
  // массив считывать со второй строки.
  readln(f); 
  
  // Записываем данные в массив.
  for i:=1 to n do begin 
    readln(f, m[i]);
  end; 
  
   //Сортируем массив по возрастанию методом Пузырька 
  for i:=1 to n-1 do begin
    for j:=1 to n-i do begin
      if m[j]>m[j+1] then begin
        l:=m[j];
        m[j]:=m[j+1];
        m[j+1]:=l;
      end;
    end;
  end;
  
  sum:=0;
  
  //Ищем среднее значение
  for i:=k+1 to n-k do begin
    sum := sum + m[i];  
  end;
  
  sr := sum div (n - 2*k);
  max := m[n-k];
  
  Writeln(max);
  Writeln(sr);

  close (f);
end.

В начале откроем файл и посмотрим количество измерений и количество исключённых значений.

Затем, считаем измерения в массив.

Отсортируем массив методом пузырька.

Исключим максимальные и минимальные значения и найдём среднее арифметическое и максимальное значение достоверных значений.

(№ 2709) (Е. Джобс) В магазине Пятэльдодео на черную пятницу решено провести одну из двух акций. Первая акция – 30% скидки на 70% самых дешевых товаров, 40% процентов скидки на оставшиеся товары. Вторая акция – 40% скидки на 50% самых дешевых товаров, 35% процентов скидки на оставшиеся товары. Определите, какая акция принесет больше прибыли, если предположить, что все товары будут проданы. Известно, что прибыль двух акций разная.

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

Входные данные. Первая строка входного файла 26-j8.txt содержит натуральное число N – количество товаров кратное 20 (натуральное число, 20 ≤ N ≤ 10000). В следующих N строках находятся значения стоимости товаров, по одному в каждой строке (целые числа, не превышающие 1000).

Пример входного файла (все значения записываются с новой строки):

Напишем решение на Pascal ABC.

const n = 10000; //Заводим константу, это будет длина массива
var
  f: text;
  i, j, k, raznica, max_sum: integer;
  profit1, profit2 : double;
m: array[1..n] of integer; //Заводим массив

begin
  
  assign(f, 'c:\26-j8.txt');
  reset(f);
  
  // Считываем первую строчку, чтобы
  // массив считывать со второй строки.
  readln(f); 
  
  // Записываем данные в массив.
  for i:=1 to n do begin 
    readln(f, m[i]);
  end;
  
  //Сортируем массив по возрастанию методом Пузырька
  for i:=1 to n-1 do begin
    for j:=1 to n-i do begin
      if m[j]>m[j+1] then begin
        k:=m[j];
        m[j]:=m[j+1];
        m[j+1]:=k;
      end;
    end;
  end;
  
  // Первая акция
  profit1 := 0;
  
  for i:=1 to (n * 70) div 100 do
  begin
    profit1 := profit1 + m[i]*0.7;
  end;
      
  for j:=i+1 to n do
  begin
    profit1 := profit1 + m[j]*0.6;
  end;
  
    
  // Вторая акция
  profit2 := 0;

  for i:=1 to (n * 50) div 100 do
  begin
    profit2 := profit2 + m[i]*0.6;
  end;
  
  for j:=i+1 to n do
  begin
    profit2 := profit2 + m[j]*0.65;
  end;
  
  if profit1 > profit2 then begin
    raznica := Trunc(profit1 - profit2);
    max_sum := (m[n] * 60) div 100;
  end
  else begin
    raznica := Trunc(profit2 - profit1);
    max_sum := (m[n] * 65) div 100;
  end;
    
  Writeln(raznica);
  Writeln(max_sum);

  close (f);
  
end.

Заведём две переменные: profit1 и profit2. В этих переменных будет находится прибыль от продажи всех товаров для первой акции и для второй соответственно. Т.к. при вычислении цены со скидкой будет получатся дробное число, тип данных для переменных profit1 и profit2 выберем double.

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

Посчитаем прибыль для первой акции и для второй акции.

Количество товаров, которое соответствует 70%а можно почитать по формуле (n * 70) div 100. Здесь мы не боимся использовать операцию div, т.к. знаем, что всего товаров 10000 и не получится дробное значение для 70% и для 50%.

После того, как почитали прибыль, можно легко ответить на вопросы задачи.

Функция Trunc позволяет округлить дробное число в меньшую сторону.

На сегодня урок по 26 заданию завершён. Успехов на экзамене по информатике 2021!