Главная Посты Курсы Связь О сайте

Демоверсия ЕГЭ по информатике 2023 (Задания 22-27)



Продолжаем решать демоверсию ЕГЭ по информатике 2023.


Условия задач были взяты с сайта: https://fipi.ru/ege/demoversii-specifikacii-kodifikatory#!/tab/151883967-5


В этой статье разберём задания 22-27.



Демоверсия ЕГЭ по информатике 2023 (Задания 1-5)
Демоверсия ЕГЭ по информатике 2023 (Задания 6-10)
Демоверсия ЕГЭ по информатике 2023 (Задания 11-15)
Демоверсия ЕГЭ по информатике 2023 (Задания 16-21)



Задание 22

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

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


ЕГЭ по информатике демоверсия 2023 - задание 22

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

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



Решение:

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


Если процесс зависит от двух процессов, то время ожидания будет равно самому медленному из этих процессов.


В столбце D пишем для каждой строчки: время процесса + время ожидания самого медленного процесса, от которого зависит этот процесс (если такие есть).


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


ЕГЭ по информатике демоверсия 2023 - задание 22 решение

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


Ответ: 17


Задание 23

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

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


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

Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.


Решение:

Будем решать с помощью шаблона на языке Python, который был представлен в видеокурсе по подготовке к ЕГЭ по информатике.


def F(x, y):
    if x == y: return 1

    if x > y or x==17: return 0

    if x < y: return F(x+1, y) + F(x*2, y)

print(F(1, 10)*F(10, 35))

Ответ: 98


Задание 24

Текстовый файл состоит из символов A, B, C, D и O.

Определите максимальное количество идущих подряд пар символов вида


согласная + гласная

в прилагаемом файле.

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



Решение:

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

f=open('24_10.txt')
s=f.read()
s=s.replace('BA', '1')
s=s.replace('CA', '1')
s=s.replace('DA', '1')
s=s.replace('BO', '1')
s=s.replace('CO', '1')
s=s.replace('DO', '1')
k=0
kmax=0

for i in range(0, len(s)):
    if s[i]=='1':
        k=k+1
        kmax=max(k, kmax)
    else:
        k=0

print(kmax)

Ответ получается 24, но в официальном ответе 95. Дело в том, что в файле присутствует буква F, хотя в условии сказано, что файл состоит только из букв A, B, C, D и O. Следовательно, файл к задаче не верный.


Ответ: 24



Задание 25

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

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

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


Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 1?2139*4, делящиеся на 2023 без остатка.

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

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



Решение:

Подобная задача так же обсуждалась в видеокурсе и на обзоре реального экзамена ЕГЭ по информатике от 20.06.22


Если не учитывать звёздочку, число 1?21394 имеет семь разрядов. Максимальная верхняя граница 1010. Значит, для звёздочки есть три разряда.

#Вместо звёздочки ноль разрядов
for x in '0123456789':
    s = '1' + x + '21394'
    i=int(s)
    if i%2023==0:
        print(i, i//2023)
    
    
#Вместо звёздочки один разряд
for x in '0123456789':
    for y in '0123456789':
        s = '1' + x + '2139' + y + '4'
        i=int(s)
        if i%2023==0:
            print(i, i//2023)

#Вместо звёздочки два разряда
for x in '0123456789':
    for y in '0123456789':
        for z in '0123456789':
            s = '1' + x + '2139' + y + z + '4'
            i=int(s)
            if i%2023==0:
                print(i, i//2023)

           
#Вместо звёздочки три разряда
for x in '0123456789':
    for y in '0123456789':
        for z in '0123456789':
            for w in '0123456789':
                s = '1' + x + '2139' + y + z + w + '4'
                i=int(s)
                if i%2023==0:
                    print(i, i//2023)

Ответ:
16213940480148
1321399324653188
1421396214702618
1521393104752048



Задание 26

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


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

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

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


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


5
43
40
32
40
30

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

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.


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




Решение:
f=open('26.txt')
n=int(f.readline())

a=[]

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


a.sort(reverse=True)

k=1
p=a[0]

for i in range(1, len(a)):
    if p-a[i]>=3:
        k=k+1
        p=a[i]

print(k, p)

В начале считываем все числа в массив (список) a. Сортируем их в порядке убывания.


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


Если следующая коробка подходит по условию, то мы её берём в наш подарок. Кто-то может подумать, что может выгоднее взять не самую большую коробку, а предпоследнего размера. Но все размеры которые будут подходить для предпоследнего элемента, точно будут подходить и для последнего, и количество упаковок точно не будет меньше, если мы берём самую большую коробку.


Дубликаты не влияют на ответы.


Если мы начинаем с самой большой коробки, то в самом конце в переменной p окажется максимальный размер самой маленькой коробки.


Ответ:
2767 51



Задание 27

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

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.


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

Дано два входных файла (файл А и файл B), каждый из которых в первой строке содержит число N ( 1 ≤ N ≤ 10 000 000) - количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.

В ответе укажите два числа: сначала значение искомой величины для файла A, затем - для файла B.


Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190

При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1*2 + 3*1 + 5*1 + 6*1 + 8*2.


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


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




Решение:
import math

f=open('27B.txt')

k=9999995

n=int(f.readline())

a=[0]*k

sm=0

for i in range(n):
    x, y = f.readline().split()
    x=int(x)
    y=int(y)
    z = math.ceil(y/36)
    a[x] = z
    sm = sm + (x-1)*z

# Вспомогательные суммы
s1=[]
s2=[]
s1.append(0)
s2.append(0)
s1.append(0)
s2.append(0)

for i in range(1, k):
    s1[1] = s1[1] + a[i]


for i in range(2, k):
    s1.append(s1[i-1] - a[i-1])
    s2.append(s2[i-1] + a[i-1])

# Ищем минимальное значение
mn=sm

for i in range(2,  k):
    sm = sm - s1[i] + s2[i]
    mn=min(mn, sm)

print(mn)


Переменная k - это количество приёмных пунктов (Т.е. длина массива a). Превая ячейка соответсвует приёмному пункту под номером 1, вторая ячейка под номером 2 и т.д. Само значение для k мы смотрим в конце файла. Например, для файла A значение напишем 999. Всего 998 приёмных пунктов, но т.к. индексы в массиве начинаются с 0, то мы должны завести 999 ячеек. Т.е. нулевая ячейка не будет никак задействована. Для файла B устанавливаем k в 9999995.


В сами ячейки массива мы поместим для каждого приёмного пункта количество контейнеров. Их легко вычислить. Если количество пробирок не нулевое, то мы должны это количество разделить на 36 и округлить в большую сторону. Количество контейниров в нашей программе для каждого приёмного пункта - это переменная z.


Пусть лаборатория расположена в первом пункте. Тогда вычислим для неё стоимость доставки:


sm1 = a[2]*1 + a[3]*2 + a[4]*3 + ... + a[m]*(m-1)

Здесь m - это последний индекс массива a (m = k-1). Пусть лаборатория будет во втором пункте, тогда:


sm2= a[3]*1 + a[4]*2 + ... + a[n]*(m-2) + a[1] = sm1 - (a[2] + a[3] + a[4] + ... + a[m]) + a[1]

Отсюда мы понимаем, что достаточно вычислить стоимость доставки sm1 по формуле, которую нам дали в задаче, только один раз для первого пункта. Для второго пункта вычисляем: sm2 = sm1 - (a[2] + a[3] + a[4] + ... + a[m]) + a[1]. Для третьего sm3 = sm2 - (a[3] + a[4] + ... + a[m]) + a[2] + a[1] и т.д.


Значит, для каждого приёмного пункта i мы должны иметь уже готовую вспомагательную сумму s1[i] = a[i] + a[i+1] + ...+ a[m], а так же сумму s2, т.е. сумма элементов, которые идут левее i (само a[i] уже не берётся): s2[i] = s[1] + s[2] + ... + s[i-1].


Сумму s1[i] мы должны отнимать, а s2[i] прибавлять. По мерее продвижения по нашим приёмным пунктам, s1[i] будет уменьшаться, а s2[i] увеличиваться.


Но вспомогательные суммы s1[i] и s2[i] нужно тоже вычислисть, как можно эффективней. Достаточно вычислить для s1[1] и s2[1] (для первого приёмного пункта), а дальше можно воспользоваться закономерностью: s1[2] = s1[1]-a[1], s1[3] = s1[2]-a[2]...и т.д. Так же s2[2] = s[1]+a[1], s[3] = s[2]+a[2] и т.д.


s1[0] и s2[0] не нужны, они соответсвуют a[0], а она не используется при решении задачи. Значение s1[1] вычисляем "честно" с помощью цикла. Значение s2[1] = 0 (левее нет ячеек).


В самом первом цикле вычисляется значение для переменной sm - это стоимость перевозки, если лаборатория стоит в первом пункте. В последнем цикле программы вычисляем стоимоть для всех остальных приёмных пунктов, используя вышеописанные алгоритмы. И находим минимальное значение среди всех значений для переменной sm.


Ответ:
51063 5634689219329


Демоверсия ЕГЭ по информатике 2023 (Задания 1-5)
Демоверсия ЕГЭ по информатике 2023 (Задания 6-10)
Демоверсия ЕГЭ по информатике 2023 (Задания 11-15)
Демоверсия ЕГЭ по информатике 2023 (Задания 16-21)






27-08-2022 в 18:31:42







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

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

ЕГЭ по информатике - Задание 11 (Рекурсия)

Одиннадцатое задание из ЕГЭ по информатике обычно даётся на рекурсию...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 0


Комментарии:

Задания 24, 26 - файлы не скачиваются, а открываются текстом в новой вкладке браузера.
Александр Литвиненко 15-09-2022 в 13:06:01

Нажмите правой кнопкой мыши на ссылку -> "Сохранить ссылку как"
Калужский Александр 15-09-2022 в 13:20:39



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



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


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