Примерное время на чтение статьи: 15 минут

Рассмотрим решение некоторых задач из варианта ИН2010401 (Статград 2021 № 4).

Задача 2

---

Логическая функция F задаётся выражением ¬((?∨?)→(?∧?))∧(?→?). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции  F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных  x, y, z, w.

Переменная 1	Переменная 2	Переменная 3	Переменная 4	Функция
???	???	???	???	F
	1	1	1	1
1		1		1
		1	1	1

В ответе напишите буквы  x, y, z, w; в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Переменная 1	Переменная 1	Функция
???	???	F
0	1	0

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Решение. Поскольку пока не известно, в каком столбце заголовка стоит какая переменная, дадим им произвольные имена по порядку, например a, b, c, d. После чего подставим их в функцию F и отобразим только строки, соответствующие значению F=1. Рассмотрим два варианта решения:

##
uses school;                       
  var tt := TrueTable((a, b, c, d) → ( not((a or b) <= (c and d)) and (a <= d)));
  TrueTablePrint(tt, 1);

Результат работы программы:

 a b c d F
 ---------
 0 1 0 0 1
 0 1 0 1 1
 0 1 1 0 1
 1 0 0 1 1
 1 1 0 1 1

Ответ: zxy

Задача 5

---

Алгоритм получает на вход натуральное число ?>1 и строит по нему новое число ? следующим образом:

1. Строится двоичная запись числа ?.
2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.
3. Шаг 2 повторяется ещё два раза.
4. Результат переводится в десятичную систему счисления.

Пример. Дано число ?=19. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 10011.
2. В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.
3. В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.
4. Результат работы алгоритма ?=153.

При каком наименьшем исходном числе ?>99 в результате работы алгоритма получится число, кратное 4?

##
uses school;

function Modify(st: string): string;
begin
  var (k0, k1)  := (st.CountOf('0'), st.CountOf('1'));
  if k0 = k1 
  then result := st + st[^1]
  else if k0 > k1
       then result := st + '1'
       else result := st + '0' 
end;

  var N := 100;
  while True do
    begin
      var strN := bin(N);
      for var i:=1 to 3 do strN:=Modify(strN);
      var R := dec(strN, 2);
      if (N > 99) and (R mod 4 = 0)
      then begin
             print(N);
             break
            end;
      N += 1
    end;

Ответ: 103

Задание 6

---

Определите, при каком наименьшем введённом значении переменной ? программа выведет число 11. Для Вашего удобства программа представлена на двух языках программирования.

##
function alg(s: integer): boolean;
begin
    s := 10 * s + 5;
    var n := 1;
    while s < 2021 do begin
        s := s + 2 * n;
        n := n + 1
      end;
    alg := (n=11)
end;

  var s := 1;
  while True do
  begin
    if alg(s)
    then begin
           println(s);
           break;
         end;
    s += 1;
  end;

Ответ: 191

Задание 7

---

В информационной системе хранятся изображения размером 1024×768 пикселей. Методы сжатия изображений не используются. Каждое изображение дополняется служебной информацией, которая занимает 1280 Кбайт. Для хранения 2048 изображений потребовалось 4 Гбайт. Сколько цветов использовано в палитре каждого изображения?

##
  for var B:=1 to 24 do
    begin
      var v := 2048 * (1024 * 768  * B + 1280 * 2**13) / (2 ** 33);
      if v = 4 then println(2**B)
    end;

Более простое решение этой задачи (без перебора) было предложено Александром (спасибо за комментарий).

Идея: одно изображение занимает объем, равный v = 4 Гб / 2048. Вычитаем объем дополнительной информации 1280 Кбайт и остается объем, отводимый на само изображение. Делим его на (1024 х 768), получаем количество бит в палитре. Все операции, естественно, делаем в битах.

## 
Print(2 ** (8 * ((4 * 2bi ** 30) / 2048 - 1280 * 1024) / (1024 * 768)));

Ответ: 256

Задача 8

---

Вероника составляет 3-буквенные коды из букв В,Е,Р,О,Н,И,К,А, причём буква В должна входить в код ровно один раз. Все полученные коды Вероника записала в алфавитном порядке и пронумеровала. Начало списка выглядит так:

1. ААВ
2. АВА
3. АВЕ
4. …

На каком месте будет записан первый код, не содержащий ни одной буквы А?

// Способ 1 (с Cartesian)
##
  var lst:='ВЕРОНИКА'
  .Cartesian(3)
  .Where(item → item.CountOf('В') = 1)
  .Select(item → item.JoinToString(''))
  .Sorted.ToArray;
  for var i:=0 to lst.Count-1 do
    if lst[i].CountOf('А')=0
    then begin
           println(i + 1);
           break
         end;

// Способ 2 (без Cartesian)
##
  var nabor:='ВЕРОНИКА';
  var lst := new List <string>;
  foreach var a in nabor do
    foreach var b in nabor do
      foreach var c in nabor do
        begin
          var word := a + b + c;
          if word.CountOf('В')=1 then lst.Add(word); 
        end;
  lst.Sort;
  for var i:=0 to lst.Count-1 do
    if lst[i].CountOf('А')=0
    then begin
            println(i+1);
            break
         end;

Ответ: 23

Задание 11

---

Каждый объект, зарегистрированный в информационной системе, получает уникальный код из 14 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 79 байт для хранения содержательной информации. Сколько байтов потребуется для хранения данных (код и содержательная информация) о 30 объектах? В ответе запишите только целое число – количество байтов.

##
  var part_1 := 14 * 6;   // 26 заглавных латинских букв и 10 цифр потребуют 6 бит
  var kod: integer;
  if part_1 / 8 = part_1 div 8
  then  kod := part_1 div 8 
  else  kod := part_1 div 8 + 1;
  var v := (kod + 79) * 30;
  print(v)

Ответ: 2700

Задание 14

---

Значение выражения 729⁷+3¹⁶–18 записали в системе счисления с основанием 9. Сколько раз в этой записи встречается цифра 0?

// Способ 1 (без school)
##
  var N:=729bi**7 + 3bi**16 - 18;
  var k := 0;
  while N > 0 do
    begin
      if N mod 9 = 0 then k += 1;
      N := N div 9;
    end;
  println(k)

// Способ 2 (с использованием school)
##
uses school;
  var N:=729bi**7 + 3bi**16 - 18;
  var sN := N.ToString;
  var n9:=ToBase(sN, 9);
  print(n9.CountOf('0'))

Ответ: 14

Задание 15

---

Для какого наименьшего натурального числа ? формула ДЕЛ(?,45)∧(ДЕЛ(750,?)→(¬ДЕЛ(?,?)→¬ДЕЛ(120,?))) тождественно истинна, то есть принимает значение 1 при любом натуральном ??

##
function ДЕЛ(n, m: integer): boolean := n.Divs(m);

function condition(x, A: integer): boolean := 
         ДЕЛ(A, 45) and (ДЕЛ(750, x) <= (not(ДЕЛ(A, x)) <= (not(ДЕЛ(120, x)))));

  for var A:=1 to 10000 do
  begin
    var Ok := True;  // Это А хорошее для всех x
    for var x:=1 to 1000000 do
      if not(condition(x, A))
      then begin
             Ok:=false;
             break
           end;
    if Ok 
    then begin
           Println(A);
           break
         end;
  end;

Ответ: 90

Задача 16

---

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

• ?(0)=0;
• ?(?)=?(?/3), если ?>0 и при этом ???(?,3)=0;
• ?(?)=???(?,3)+?(?–???(?,3)), если ???(?,3)>0.

Назовите минимальное значение ?, для которого ?(?)=11.

##
function F(n: integer): integer :=
  n=0 ? 0 : n.Divs(3) ? F(n div 3) : n mod 3 + F(n - (n mod 3));

  var n:=0;
  while True do
  begin
    if F(n)=11
    then begin
           Println(n);
           break
         end;
    n += 1;
  end;

Ответ: 485

Задача 17

---

Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители – 2, 3 и 5), а число 12 – нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [10001;50000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

## //Способ 1 (с помощью school)
  uses school;
  var (cnt, mn) := (0, MaxInt);
  for var n:=50000 downto 10001 do
  begin
    var lst := n.Factorize.Distinct;
    if lst.count =3 then (cnt, mn) := (cnt + 1, n);
  end;
  println(cnt, mn);

// Способ 2 (с помощью school + LINQ)
## 
uses school;
  var s:=(10001..50000).Where(n → n.Factorize.Distinct.Count = 3);
  s.Count.Println;
  s.Min.Println;

Ответ: 15652 10002

Задача 22

---

Ниже записана программа, которая вводит натуральное число ?, выполняет преобразования, а затем выводит два числа. Укажите наименьшее возможное значение ?, при вводе которого программа выведет числа 3 и 10.

##
function alg(x: integer): boolean;
begin
  var k := x mod 9;
  var (a, b) := (0, 0);
  while x > 0 do begin
    var d := x mod 9;
    if d = k then a := a + 1;
    b := b + d;
    x := x div 9
  end;
  alg:=(a=3) and (b=10);
end;

   for var x:=1 to 10000 do
    if alg(x)
    then begin
           Println(x); 
           break;
         end;

Ответ: 874

Задача 23

---

Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 2
3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 2 в число 36, и при этом траектория вычислений содержит число 12 и не содержит числа 30?

##
function numProg(start, cur: integer): integer;
begin
  if (cur < start) or (cur=30) then result := 0
  else if cur = start then result := 1
       else begin
              result := numProg(start, cur-1);
              if cur mod 2 =0 then result += numProg(start, cur div 2);
              if cur mod 3 =0 then result += numProg(start, cur div 3);
            end;
end;

  // Умножаем количество маршрутов 2->12 на 12->36 (комбинаторика)
  print(numProg(2, 12) * numProg(12, 36));

Ответ: 60

Задача 24

---

Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (???…?).

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

Пример. Исходный файл:

GIGA
GABLAB
AGAAA

В этом примере в первой строке две буквы G, во второй и третьей – по одной. Берём вторую строку, т. к. она находится в файле раньше. В этой строке чаще других встречаются буквы A и B (по два раза), выбираем букву B, т. к. она позже стоит в алфавите. В ответе для этого примера надо записать B.

var
  cnt: array['A'..'Z'] of integer;
  f: Text;
  s, stroka: string;
  kcurrG: integer;
begin 
  assignFile(f, '24data/ИН2010401.txt');
  reset(f);
  var minG := maxInt;
  while not eof(f) do
    begin
      readln(f, stroka);
      kcurrG:=stroka.CountOf('G');
      if kcurrG < minG 
      then (minG, s) := (kcurrG, stroka);
    end;
  CloseFile(f);

  for var c:='A' to 'Z' do cnt[c] := 0;
  for var i:=1 to s.length do cnt[s[i]] += 1;

  var maxCount := 0;
  var maxC: char;

  for var c:='A' to 'Z' do
    if cnt[c] >= maxCount
    then begin
           maxCount := cnt[c];
           maxC := c;
         end;
  print(maxC)
end.

Ответ: T

Задача 25

---

Найдите все натуральные числа, принадлежащие отрезку [35000000;40000000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.

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

##
// Способ 1 (с использованием school)
uses school;
  var (a, b) := (35000000, 40000000);
  for var n:=a to b do
    begin
      var x := n;
      while x.isEven do
        x := x div 2;    // Убираем все четные делители
      if (x ** 0.25 = trunc(x ** 0.25)) and trunc(x**0.25).isPrime
      then print(n);
    end;

##
// Способ 2 (с использованием school)
uses school;
  var (a, b) := (35000000, 40000000);
  for var n:=a to b do
    begin
      var lst := n.Divisors;
      var cntOddDel := 0;
      foreach var d in lst do begin
        if d.isOdd then cntOddDel += 1;
        if cntOddDel > 5 then break
      end;
      if cntOddDel = 5 then println(n);
    end; 

// Способ 3 (с school + LINQ)
##
uses school;
  (35000000..40000000)
  .Where(n → n.Divisors.Count(x → x.isOdd) = 5)
  .println

Ответ: 35819648; 38950081; 39037448; 39337984

Задача 26

---

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

Входные данные Первая строка входного файла содержит целое число ? – общее количество чисел в наборе. Каждая из следующих ? строк содержит одно число.

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

6
3
8
14
11
2
17

В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11), 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 11. В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.

//Способ 1 (линейный поиск - работает долго)
var
  f: text;
  sr: integer;
begin
  assign(input, '26data/ИН2010402.txt');
  var n := ReadInteger;
  var a:= ReadArrInteger(n);
  var (k, mx):=(0, 0);
  for var i:=0 to n-2 do
  begin
    if a[i] mod 2=0 then
    begin
      for var j:=i+1 to n-1 do
        if a[j] mod 2=0 
        then begin
               sr:=(a[i]+a[j])div 2;
               if sr in a
               then (k, mx):=(k+1, max(mx, sr))
             end;
    end;
  end;
  print(k, mx);
end.

//Способ 2 (с реализацией двоичного поиска)
##
  assign(input, '26data/ИН2010402.txt');
  var n := ReadInteger;
  var a:= ReadArrInteger(n);
  var lsts := new List <integer>;
  var s, L, R, C: integer;
  a.Sort;
  for var i:=0 to n-2 do
    for var j:=i+1 to n-1 do 
      begin
        if (a[i] mod 2 = 0) and (a[j] mod 2 = 0) then 
        begin
          s:=(a[i]+a[j]) div 2;
          L:=i;
          R:=j+1;
          while L<R-1 do 
            begin 
              C:=(R+L) div 2;
              if s<a[c] then R:=C else L:=C;  
            end;
          if a[L]=s then  lsts.Add(s);
        end;
    end;
lsts.count.println;
lsts.max.println;

//Способ 3 (с использованием готового двоичного поиска)
##
assign(input, '26data/ИН2010402.txt');
var n := ReadInteger;
var a:= ReadArrInteger(n);
a.Sort;
var (k, m):=(0, 0);
for var i:=0 to a.High-1 do
  for var j:=i+1 to a.High do
    if (a[i] mod 2 = 0) and (a[j] mod 2 = 0) then begin
      var s:=(a[i]+a[j]) div 2;
      if a.BinarySearch(s)>=0 then begin
        k:=k+1;
        m:=max(m,s);
      end;
    end;
print(k,m);

Ответ: 15; 976339247

Задача 27

---

В текстовом файле записан набор натуральных чисел, не превышающих 10⁸. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 3. Какую наибольшую сумму можно при этом получить?

Входные данные Первая строка входного файла содержит целое число ? – общее количество чисел в наборе. Каждая из следующих ? строк содержит одно число.

4
5
8
14
11

В данном случае есть две подходящие тройки: 5,14,11 (сумма 30) и 8,14,11 (сумма 33). В ответе надо записать число 33.

Вам даны два входных файла (? и ?), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла ?, затем для файла ?.

Приведу довольно интересное решение, которое предложил Кирилл Козырев (учащийся 11 класса).

##
  assign(input, '27data/ИН2010401-B.txt');
  var (m01, m02, m03) := (0, 0, 0); // три максимума, дающие при делении на 3 остаток 0
  var (m11, m12, m13) := (0, 0, 0); // три максимума, дающие при делении на 3 остаток 1
  var (m21, m22, m23) := (0, 0, 0); // три максимума, дающие при делении на 3 остаток 2
  var n := ReadInteger;
  var a := ReadArrInteger(n).Sorted; // получение отсортированной последовательности
  foreach var x in a do begin
     if x mod 3 = 0 then (m03, m02, m01) := (m02, m01, x); 
     if x mod 3 = 1 then (m13, m12, m11) := (m12, m11, x); 
     if x mod 3 = 2 then (m23, m22, m21) := (m22, m21, x); 
   end;
  max(m01 + m02 + m03, m11 + m12 + m13, m21 + m22 + m23, m01 + m11 + m21).print;

Ответ: 2697; 299986167

P.S. Если Вы заметили ошибку, буду благодарна за комментарии.