Всемирный день риса

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



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


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


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





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


Задание 22

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

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



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

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


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


Скачать файл




Решение:

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


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


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


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


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


ЕГЭ по информатике ДЕМО 2024 - задание 22 (решение)

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


=СУММ(E2:E13)

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


ЕГЭ по информатике ДЕМО 2024 - задание 22 (решение 2)




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


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


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


ЕГЭ по информатике ДЕМО 2024 - задание 22 (решение 3)

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


Ответ: 7



Задание 23

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

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


A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат

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

Сколько существует программ, для которых при исходном числе 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))

Ответ: 37



Задание 24

Текстовый файл состоит из символов 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)

Ответ: 133



Задание 25

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


– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

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

Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 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)

Ответ:

14215766470236
1021575544504731
1121571264554136
1221577104603546
1321572824652951
1421578664702361
1521574384751766
1621570104801171
1721575944850581
1821571664899986
1921577504949396




Задание 26

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


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


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

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


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


5
10 150
100 120
131 170
150 180
120 130

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 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)


Ответ:
3215




Задание 27

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

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


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

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

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


Типовой пример организации данных во входном файле
2
6
150
–150
20
–200
–300
0

При таких исходных данных искомая величина равна 170 – это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

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


Предупреждение: для обработки файла 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)

Ответ:
18953617210


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


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




30-08-2023 в 08:41:40





Поддержать сайт:


Похожая статья:

Разбор демоверсии ОГЭ по информатике 2023. Часть 2

Разбор второй части ОГЭ по информатике демоверсии 2023....

Категория: Информатика  Подкатегория: ОГЭ
Дата: 24-08-2022 в 13:09:01 3



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:




Нажимая кнопку Отправить, Вы соглашаетесь с политикой конфиденциальности сайта.