ЕГЭ по информатике ДЕМО 2024 - Задания 11-21

Продолжаем разбирать Демоверсии 2024. В этой статье будут разобраны задания с 11-ого по 21-е.

Напоминаю про великолепный цикл статьей для подготовке к ЕГЭ по информатике.

Продолжаем праздник информатики!

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

Определите объём памяти (в Кбайт), необходимый для хранения 65 536 идентификаторов.

В ответе запишите только целое число – количество Кбайт.

Воспользуемся формулой для 11-ого задания из ЕГЭ по информатике.

Вместо N подставляем 260 (250 + 10) символов, которые претендуют в одну ячейку. Тогда

Т.е. 9 бита точно хватит, чтобы закодировать 260 символов.

В идентификаторе всего 60 ячеек. Найдём сколько будет "весить" один идентификатор: 9 * 60 = 540 бит. Узнаем, сколько байт потребуется для одного идентификатора 540 / 8 = 68 байт (округляем в большую сторону, чтобы точно хватило).

У нас всего 65536 идентификаторов. Тогда нам потребуется 65536 * 68 = 4456448 байт. Переведём в Кб: 716800 / 1024 = 4352 Кб.

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

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды

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

не меняет эту строку.

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

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

Цикл

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

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

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

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

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

Дана программа для Редактора:

НАЧАЛО
  ПОКА нашлось (52) ИЛИ нашлось (2222) ИЛИ нашлось (1122)
    ЕСЛИ нашлось (52)
      ТО заменить (52, 11)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (2222)
      ТО заменить (2222, 5)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (1122)
      ТО заменить (1122, 25)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «5», а затем содержащая n цифр «2» (3 < n < 10 000).

Определите наибольшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 64.

Перепишем программу с русского языка на язык Python.

for n in range(4, 10000):
    s = '5' + n * '2'
    while '52' in s or '2222' in s or '1122' in s:
        if '52' in s:
            s = s.replace('52', '11', 1)
        if '2222' in s:
            s = s.replace('2222', '5', 1)
        if '1122' in s:
            s = s.replace('1122', '25', 1)

    sm = s.count('1')*1 + s.count('2')*2 + s.count('5')*5
    if sm == 64:
        print(n)

Если есть какая-то переменная в задании, скорее всего, её нужно прокрутить в цикле. Здесь у нас была переменная n, мы её перебираем в цикле.

Как искать сумму строки в 12 задании, написано в статье на моём сайте Code-Enjoy.

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети. Сеть задана IP-адресом 192.168.32.160 и маской сети 255.255.255.240. Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса чётна?

В ответе укажите только число.

Более подробно, как работать с задачами на эту тему, можете посмотреть в статье.

В задаче сказано, что к IP-адресу узла применяется поразрядная конъюнкция байтов маски и получается адрес сети.

Разберёмся с последним байтом.

Получается, что возможность для манёвров у нас есть только на последних 4 битах IP-адреса узла.

Посчитаем, сколько у нас уже единиц точно известно в IP-адресе в двоичным виде.

Плюс две единицы в последнем байте. Тогда получается:

Восемь единиц уже точно есть в любом IP-адресе узла.

Теперь задача сводится к тому, чтобы посчитать количество вариантов, когда в 4 битах будет чётное количество единиц.

Можно решать на Python, как в 8 задании.

k=0
for x1 in '01':
    for x2 in '01':
        for x3 in '01':
            for x4 in '01':
                s = x1 + x2 + x3 + x4
                if s.count('1')%2==0:
                    k=k+1
print(k)

Ответ получается 8.

Операнды арифметического выражения записаны в системе счисления с основанием 19.

В записи чисел переменной x обозначена неизвестная цифра из алфавита 19-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 18. Для найденного x вычислите частное от деления значения арифметического выражения на 18 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.

Такие задачи, как орехи, щёлкаются в статье по 14 заданию из ЕГЭ по информатике.

Пишем шаблоне на Python.

for x in range(19):
    a = 1*19**0 + 2*19**1 + x*19**2 + 7*19**3 + 9*19**4 + 8*19**5 + 8*19**6 + 9*19**7
    b = 3*19**0 + 2*19**1 + 9*19**2 + x*19**3 + 2*19**4
    if (a+b)%18 == 0:
        print(x, (a+b)//18)

Для наибольшего икс получается 469034148.

Значение арифметического выражения

записали в системе счисления с основанием 25. Сколько значащих нулей содержится в этой записи?

f = 3 * 3125**8 + 2*625**7 - 4*625**6 + 3*125**5 - 2*25**4 - 2024
k=0
while f>0:
    if f%25==0:
        k=k+1
    f = f // 25
print(k)

Для какого наименьшего целого неотрицательного числа A выражение

тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y?

for A in range(0, 300):
    k=0
    for x in range(0, 300):
        for y in range(0, 300):
            if (x + 2*y < A) or (y > x) or (x > 60):
                k=k+1

    if k == 300*300:
        print(A)

Как решать такие задачи подробно объяснялось в этой статье.

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

Чему равно значение выражения F(2022) / F(2024)?

Тоже в статье подробно разбирались такие задачи.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n > 2024:
        return n
    if n <= 2024:
        return n*F(n+1)

for n in range(2024, 0, -1):
    F(n)

print(F(2022)/F(2024))

В файле содержится последовательность натуральных чисел, каждое из которых не превышает 100 000. Определите количество троек элементов последовательности, в которых ровно два из трёх элементов являются трёхзначными числами, а сумма элементов тройки не больше максимального элемента последовательности, оканчивающегося на 13. Гарантируется, что в последовательности есть хотя бы одно число, оканчивающееся на 13. В ответе запишите количество найденных троек чисел, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Похожую задачу я разбирал недавно в статье по 17 заданию из ЕГЭ по информатике.

Задача решается в два шага. В начале найдём максимальный элемент последовательности, оканчивающий на 13.

f=open('17_2024.txt')

mx = 0

for s in f.readlines():
    x=int(s)
    if x%100==13:
        mx = max(mx, x)

print(mx)

Получается число 98413.

Числа в файле натуральные, следовательно, положительные. Значит, переменную mx в начале можно инициализировать нулём. Так же, когда ищём на что оканчивается число, не нужно использовать модуль.

Выполним второй шаг, напишем основную программу.

f=open('17_2024.txt')

mx = 0
k=0

n1=int(f.readline())
n2=int(f.readline())

for s in f.readlines():
    n3=int(s)
    c = 0
    if 100 <= n1 < 1000:
        c = c + 1
    if 100 <= n2 < 1000:
        c = c + 1
    if 100 <= n3 < 1000:
        c = c + 1
    if c==2 and n1+n2+n3 <= 98413:
        k=k+1
        mx = max(mx, n1+n2+n3)
    n1=n2
    n2=n3

print(k, mx)

Здесь удобно использовать приём "мини-счётчики". Кто любит смотреть видео формат, посмотрите видео по данной теме.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

При решении 18 задания нужно проявлять теперь бдительность и внимательно читать вопрос.

Решается данное задание стандартно, только теперь вводится понятие итоговых клеток. Итоговая клетка - это клетка, когда и снизу, и справа, стена т.е. роботу больше некуда ходить.

В начале выделим все буквы от A до T, вызовем контекстное меню и выберем ширина столбца. Поставим ширу столбца 5. Это нам позволит ужать всё пространство.

Выделим все ячейки с числами, нажмём "вырезать", используя контекстное меню. Вставим данные на 1 столбец вправо. Это делаем потому, что будем использовать для решения формулу, которая будет обращаться к ячейке слева.

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

Можно скопировать прямоугольник с числами и вставить его снизу, пропустив одну строчку. Потому нажмём кнопку DELETE, тогда числа удаляться, а стенки останутся, нам это и нужно!

Отметим особым цветом те ячейки, которые "спрятаны" от движения Робота стенками.

Для этих ячеек будем составлять другие формулы, в отличии от обычных ячеек.

Цвет ячейки можно поменять, нажав на кнопку "Цвет заливки" на главной вкладке программы.

Т.к. Робот направляется из левой верхней ячейки, то мы сначала и напишем формулу для этой ячейки. Пишем для ячейки B22:

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

Распространим формулу на всё пространство, не трогая закрашенные клетки.

Получается такая картина:

Для вертикальных подкрашенных полосок, Робот может попасть только сверху! Поэтому пишем формулу для ячейки, к примеру, для I24:

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

Аналогично делаем для всех вертикальны подкрашенных полосок.

В ячейки для горизонтально подкрашенных полосок, Робот может попасть только слева! Поэтому пишем формулу, к примеру, для ячейки C26:

Распространяем формулу по всей закрашенной строчке. Аналогично делаем со всеми горизонтальными полосками.

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

Из этих трёх клеток нужно выбрать максимальное значение.

Получается 2167.

Чтобы получить минимальную возможную сумму, в главной формуле функцию МАКС нужно заменить на МИН!

Удобно воспользоваться автоматической заменой через Ctrl+F.

Минимальная сумма равна 718.

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

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 128.

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

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

Воспользуемся убойным шаблоном для решения задач 19-21 из ЕГЭ по информатике.

def F(x, p):
    if x >= 129 and p==3:
        return True
    if x <= 129 and p==3:
        return False
    if x >= 129:
        return False

    if p%2!=0:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
        return F(x+1, p+1) or F(x*2, p+1)

for s in range(1, 129):
    if F(s, 1):
        print(s)

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

Найденные значения запишите в ответе в порядке возрастания.

Изменим пару символов в предыдущем шаблоне-трансформере и получаем 20 задание!

def F(x, p):
    if x >= 129 and p==4:
        return True
    if x <= 129 and p==4:
        return False
    if x >= 129:
        return False

    if p%2==0:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
        return F(x+1, p+1) or F(x*2, p+1)

for s in range(1, 129):
    if F(s, 1):
        print(s)

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

Если найдено несколько значений S, в ответе запишите минимальное из них.

Тот же шаблон-трансформер превращается в 21 задание без особого труда!

def F(x, p):
    if x >= 129 and (p==3 or p==5):
        return True
    if x <= 129 and p==5:
        return False
    if x >= 129:
        return False

    if p%2!=0:
        return F(x+1, p+1) and F(x*2, p+1)
    else:
        return F(x+1, p+1) or F(x*2, p+1)

def F1(x, p):
    if x >= 129 and p==3:
        return True
    if x <= 129 and p==3:
        return False
    if x >= 129:
        return False

    if p%2!=0:
        return F1(x+1, p+1) and F1(x*2, p+1)
    else:
        return F1(x+1, p+1) or F1(x*2, p+1)

for s in range(1, 129):
    if F(s, 1):
        print(s)

print()

for s in range(1, 129):
    if F(s, 1):
        print(s)

То, что распечатает функция F1, мы должны исключить из ответов.