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

Третья часть раздора ЕГЭ по информатике ДЕМО 2024.

Для подготовки к ЕГЭ по информатике помогут материалы сайта Code-Enjoy.

В этой части разберём самый сложные задачи. Поехали!

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

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Рекомендуется ужать ширину столбцов, чтобы было удобно работать. Сделать это можно так: выделяем нужные буквы столбцов, вызываем контекстное меню, потом ширина столбца и выбираем, к примеру, 5.

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

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

Если процесс зависит от нескольких процессов, то он должен дождаться самый долгих процесс, а потом выполниться сам.

Вот какой рисунок получается. Отметка ноль выбрана на границе D и E столбцов.

Теперь расставим единицы в жёлтые клеточки, а внизу подсчитаем сумму единиц для каждого столбца. Для ячейки E15 пропишем формулу:

Распространим эту формулу на всю строчку.

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

Но в данной задаче не сказано, что все процессы должны завершиться за минимально возможное время. Поэтому мы можем смещать процессы по времени, если это возможно.

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

Длина максимального отрезка равна 7.

Исполнитель преобразует число на экране.

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

Программа для исполнителя – это последовательность команд.

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.

Решим задачу с помощью с сногсшибательного шаблона.

def F(x, y):
    if x == y: return 1
    if x > y or x==11: return 0
    if x < y: return F(x+1, y) + F(x*2, y) + F(x*x, y)
print(F(2, 20))

Текстовый файл состоит из символов T, U, V, W, X, Y и Z.

Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди которых символ T встречается ровно 100 раз.

Для выполнения этого задания следует написать программу.

Подобные задачи отлично разобраны в статье по 24 заданию из ЕГЭ по информатике.

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

f=open('24_2024.txt')

s=f.read()

t=100

a=s.split('T')

k=0
kmax=0

for j in range(0, t+1):
    k=k+len(a[j])
    if j!=t:
        k=k+1

for i in range(t+1, len(a)):

    kmax = max(kmax, k)

    k=k-len(a[i-t-1])
    k=k-1
    k=k+1
    k=k+len(a[i])
           
kmax = max(kmax, k)   

print(kmax)

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

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 1?2157*4, делящиеся на 2024 без остатка.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 2024.

Количество строк в таблице для ответа избыточно.

Решим с помощью инструмента fnmatch. Об этом говорилось в этой статье.

from fnmatch import *

for i in range(2024, 10**10+1, 2024):
    if fnmatch(str(i), '1?2157*4'):
        print(i, i//2024)

Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.

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

Входные данные В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.

Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

Типовой пример организации данных во входном файле

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Очень похожая задача была решена в статье по 26 заданию из ЕГЭ по информатике.

Так же можете посмотреть видео-разбор с решением очень похожей задачи.

f=open('26_2024.txt')
n=int(f.readline())
a=[]
for i in range(n):
    st = f.readline().split()
    a.append((int(st[0]), int(st[1])))

# Сортируем по второму элементу
a.sort(key=lambda x: x[1])

gr=0
gr2=0
k=0

mx_end = 0

# Ищем максимальное количество
for i in range(n):
    if a[i][0] >= gr:
        gr2=gr # Окончание предпоследнего выбранного элемента
        gr=a[i][1]
        k=k+1
        
# Ищем максимальное время начала последнего элемента при максимальном количестве
for i in range(n):
    if a[i][0] >= gr2:
        mx_end=max(mx_end, a[i][0])

print(k, mx_end - gr2)

По каналу связи передаётся последовательность целых чисел – показания прибора. В течение N мин. (N – натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.

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

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

Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Похожая задача была разобрана в досрочном варианте 2023.

f=open('27_B_2024.txt')

k=int(f.readline())
n=int(f.readline())

a=[]

m1=-10**20
m2=-10**20
mx=-10**20

for i in range(n):
    x=int(f.readline())
    a.append(x)

for i in range(2*k, n):
    m1=max(m1, a[i-2*k])
    m2=max(m2, m1+a[i-k])
    mx=max(mx, m2+a[i])

print(mx)

Успехов в новом учебном 2024 году!