Редактировать

Внимание!

Обновлено 03.10.2024

Мы рекомендуем всем, кто готовит и готовится к сдаче ЕГЭ, пользоваться возможностями PascalABC.NET версии 3.10.0. Эта версия вышла 27.08.2024 года. Использование более ранних версий лишит школьника некоторых имеющихся в языке возможностей и потребует самостоятельно искать для них эквивалентные замены.

Мы призываем также тех работников образования, от которых зависит состояние программных средств на станциях ЕГЭ, заблаговременно установить любую доступную сборку версии 3.10.0 или выше. Версия PascalABC.NET 3.9.0 и тем более 3.8.3 считаются устаревшими.

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

Рекомендуется скачивать текущую версию на сайте.

Об этом документе

Здесь представлены решения некоторых задач демонстрационных вариантов ЕГЭ по информатике прошлых лет. Решения даются с кратким описанием алгоритма и концентрируются в основном на демонстрации возможностей языка.

Решения сбалансированы по простоте записи и восприятия в балансе с новыми возможностями.

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

Великолепный разбор задач типа 8, 13 и 22 ЕГЭ по информатике 2023-24 на чистом PascalABC.NET дан К.Ю.Поляковым в данной презентации. Здесь представлены наиболее эффективные и неочевидные решения.

О PascalABC.NET

PascalABC.NET – современный диалект языка программирования Паскаль, позволяющий записывать код компактно и понятно, используя современные языковые возможности. Это делает программу яснее и как следствие сокращает число возможных ошибок на ЕГЭ по информатике, связанных с волнением и другими субъективными причинами.

Данный текст составлен разработчиками языка и рассматривает ряд вопросов, связанных с использованием PascalABC.NET при сдаче ЕГЭ по информатике. Он ориентирован:

  • на школьников, использующих при сдаче ЕГЭ PascalABC.NET как язык реализации программ
  • на преподавателей, которые при подготовке школьников к сдаче ЕГЭ по информатике используют PascalABC.NET

Важно! Данный текст не рассматривает вопросы, связанные с методикой решения задач. Он лишь описывает то, как на PascalABC.NET сделать запись алгоритмов лучше, сохранив при этом эффективность.

PascalABC.NET имеет множество языковых возможностей и множество стилей программирования, поскольку обобщает современные языковые и библиотечные возможности сразу нескольких современных языков программирования (C#, Python, Kotlin).

При решении задач ЕГЭ по информатике мы рекомендуем использовать лишь ограниченный набор возможностей PascalABC.NET, которые делают текст программы яснее и короче, позволяя концентрироваться на сути алгоритма, а не на технических деталях.

К базовым возможностям языка, рекомендуемым нами при решении задач ЕГЭ, относятся:

  1. Описания переменных внутри блока в том месте, где они впервые потребовались. Это ликвидирует длинные перечни описания переменных до beginа основной программы, ухудшающие читаемость и лёгкость написания программы.
  2. Автовывод типа переменной при описании с инициализацией (var a := 1).
  3. Использование описания счётчика цикла for в заголовке цикла (for var i).
  4. Функции ввода вида ReadInteger, ReadReal, ReadInteger2 и т.д., позволяющие одной строкой описывать и вводить переменную в любом месте операторного блока программы (var a := ReadInteger).
  5. Процедуры вывода Print, Println, автоматически разделяющие элементы вывода пробелами.
  6. Цикл loop – аналог цикла for, использующийся когда счётчик цикла не нужен.
  7. Кортежи и распаковка кортежей в переменные, называемая также множественным присваиванием: (a,b) := (1,1).

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

Все представленные здесь решения сбалансированно сочетают простоту и понятность записи и использование новых возможностей.

Задача 17

Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.

Решение 1. Минимум новых возможностей; длинная запись условия, уводящая от сути

begin
  var count := 0;
  var max := -MaxInt;
  for var x := 1016 to 7937 do
    if (x mod 3 = 0) and (x mod 7 <> 0) and (x mod 17 <> 0) and 
       (x mod 19 <> 0) and (x mod 27 <> 0) then
    begin
      count += 1;
      if x > max then
        max := x;
    end;
  Print(count,max);
end.

Ответ. 1568 7935

Решение 2. Использование методов Divs и DivsAny

begin
  var count := 0;
  var max := -MaxInt;
  for var x := 1016 to 7937 do
    if x.Divs(3) and not x.DivsAny(7, 17, 19, 27) then
    begin
      count += 1;
      if x > max then
        max := x;
    end;
  Print(count,max);
end.

Решение 2а. Заметим, что максимальный элемент является последним удовлетворяющим условию

begin
  var count := 0;
  var last := 0;
  for var x := 1016 to 7937 do
    if x.Divs(3) and not x.DivsAny(7, 17, 19, 27) then
    begin
      count += 1;
      last := x;
    end;
  Print(count,last);
end.

Решение 3. Использование последовательностей

begin
  // Рассмотрим последовательность целых от 1016 до 7937, делящихся на 3 и не делящихся ни на одно из 7, 17, 19, 27
  var seq := (1016..7937).Where(x -> x.Divs(3) and not x.DivsAny(7, 17, 19, 27));
  // Выведем количество элементов этой последовательности и ее максимальный элемент
  Print(seq.Count,seq.Max);
end.

Замечание. Аналогично предыдущему вместо seq.Max можно использовать seq.Last

Задача 25

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.

Решение 1

Для получения всех делителей составим функцию, которая будет помещать все получаемые делители в список. Это неэффективно (нужны только числа с ровно двумя делителями), но для приводимых на ЕГЭ значений программа выполняется мгновенно, поэтому писать более оптимальный алгоритм не следует.

function Divisors(N: integer): List<integer>;
begin
  Result := new List<integer>;
  for var i:=2 to N-1 do
    if N.Divs(i) then
      Result.Add(i);
end;

begin
  for var N := 174457 to 174505 do
  begin
    var d := Divisors(N);
    if d.Count = 2 then
      Println(d[0],'|',d[1]);
  end;
end.

Ответ.

3 | 58153
7 | 24923
59 | 2957 
13 | 13421
149 | 1171 
5 | 34897
211 | 827
2 | 87251

Решение 2

Без использования функции

begin
  for var N := 174457 to 174505 do
  begin
    var d := new List<integer>;
    for var i:=2 to N-1 do
      if N mod i = 0 then
        d.Add(i);
    if d.Count = 2 then
      Println(d[0],'|',d[1]);
  end;
end.

Решение 3

Более эффективное, в котором список делителей не пополняется если уже содержит более двух делителей. Это решение - на случай достаточно больших значений N, что трудно представить на ЕГЭ

begin
  for var N := 174457 to 174505 do
  begin
    var d := new List<integer>;
    for var i:=2 to N-1 do
    begin  
      if N mod i = 0 then
        d.Add(i);
      if d.Count > 2 then // Это условие даёт более эффективное решение
        break;
    end;  
    if d.Count = 2 then
      Println(d[0],'|',d[1]);
  end;
end.

Данное решение тем не менее будет медленно работать при очень больших N, однако подобное усложнение невозможно на ЕГЭ - оно делает задачу олимпиадной. Однако, решение есть и в этом случае. Оптимизации решения задачи 25 рассмотрены в презентации К.Ю. Полякова.

Задача 26

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

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

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

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

100 4
80
30
50
40

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

2 50

Решение 1

begin 
  Assign(input, '26.txt'); 
  var (S,N) := ReadInteger2;
  var data := ReadArrInteger(N);
  Sort(data);  
  var (total,count) := (0,0);
  while (count < N) and (total + data[count] <= S) do
  begin
    total += data[count];
    count += 1;
  end;
  var delta := S - total;
  Println(count, data.Last(x -> x - data[count-1] <= delta));
end.

Решение скорее всего позаимствовано с сайта К. Полякова с косметическими правками в стиле PascalABC.NET.

Решения аналогичных задач на чистом PascalABC.NET содержатся в презентации К.Ю. Полякова.

Ответ.

568 50

Задача 27

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

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

6
1 3
5 12
6 9
5 4
3 3
1 1

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

Решение 1

begin
  Assign(input,'27-b.txt');
  var (s, d) := (0, MaxInt);
  var n := ReadInteger;
  loop n do
  begin
    var (a,b) := ReadInteger2;
    s += Max(a,b);
    var diff := Abs(a-b);
    if diff mod 3 <> 0 then
      d := Min(d, diff)
  end;  
  if s mod 3 <> 0 then
    Print(s)
  else Print(s-d)
end.

Решение скорее всего позаимствовано с сайта К. Полякова с косметическими правками в стиле PascalABC.NET.

Ответ.

127127 399762080

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

Задача 5

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

  1. Строится двоичная запись числа N.
  2. К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.

Пояснение

Для решения используется функция Bin модуля School, содержащего ряд базовых математических алгоритмов:

uses School;

begin
  for var NN := 1 to 100 do
  begin
    var N := NN;
    var rem := Bin(N).Count(d->d='1') mod 2;
    N := 2*N + rem;
    rem := Bin(N).Count(d->d='1') mod 2;
    N := 2*N + rem;
    Println(NN,N);
  end;
end.

Задача 12

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

ПОКА условие
  последовательность команд
КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ условие
  ТО команда1
  ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.

НАЧАЛО
  ПОКА нашлось (2222) ИЛИ нашлось (8888)
    ЕСЛИ нашлось (2222)
      ТО заменить (2222, 88)
      ИНАЧЕ заменить (8888, 22)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

Решение. Условие - слишком длинное ))

begin
  var s := 70 * '8';
  
  while ('2222' in s) or ('8888' in s) do
    if '2222' in s
      then s := s.Replace('2222', '88', 1)
    else s := s.Replace('8888', '22', 1);
  Print(s);
end.

Ответ

22

Задача 14

Значение арифметического выражения: 497 + 721 – 7 – записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?

Решение.

begin
  var bb := 49bi ** 7 + 7bi ** 21 - 7;
  
  var count := 0;
  repeat
    if bb mod 7 = 6 then
      count += 1;  
    bb := bb div 7;
  until bb = 0;
  
  Count.Print; 
end.

Пояснение 49bi, 7bi - это константы типа BigInteger

Ответ

13

Решение 2. Используем стандартный метод ToBase модуля School и стандартный метод последовательностей CountOf:

uses School;

begin
  (49bi ** 7 + 7bi ** 21 - 7).ToBase(7).CountOf('6').Print
end.

Задача 15

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Решение.

begin
  // Возьмём большой диапазон a: от 1 до 10000
  for var a := 10000 downto 1 do
    // Если для всех натуральных x (возьмём некоторый большой диапазон) 
    // выполняется условие задачи, то мы нашли a
    if (1..100000).All(x -> not x.Divs(a) <= (x.Divs(6) <= not x.Divs(9))) then
    begin  
      Print(a);
      break;
    end;
end.

Пояснение Импликация → в PascalABC.NET описывается операцией <=. Это легко показать таблицей истинности.

Пояснение

Тип BigInteger указан “на всякий случай” - если будут возникать очень большие целые. В задачах ЕГЭ - вряд ли

Задача 16

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.

Чему равно значение функции F(26)?

Решение.

function F(n: integer): BigInteger;
begin
  if n = 1 then Result := 1
  else if n.IsEven then Result := n + F(n - 1)
  else Result := 2 * F(n - 2);
end;

begin
  F(26).Print 
end.

Ответ

4122