Калужский Александр: Исправил!
05-09-2024
Читать статью
.: "Если число в двоичной форме имеет меньш..
Калужский Александр: Можно и так
02-09-2024
В этой части решим задачи из 22-27 задания новой демоверсии ЕГЭ по информатике 2025.
При решении задач будем опираться на НОВЫЙ курс для подготовки к ЕГЭ по информатике 2025.
Не будем терять ни секунды, приступим к задачам!
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов при условии, что все независимые друг от друга процессы могут выполняться параллельно и время окончания работы всех процессов минимально.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Т.к. время окончания работы всех процессов минимально, это означает, что процессы нельзя двигать. Они должны как можно раньше начаться и как можно раньше закончится, с учётом зависимостей.
Изобразим все процессы в виде диаграммы и решим задачу.
Время процессов изобразим жёлтыми клетками, где расставим 1.
Внизу в ячейке D16 напишем формулу:
Распространим эту формулу вправо на всю строчку.
Максимальное количество параллельных процессов равно 4. Максимальный отрезок, когда выполняются 4 параллельных процессов, равен 5.
Более подробно, как решать такие задачки, смотрите в видео, которое находится в статье по 22 Заданию из нового круса ЕГЭ по информатике 2025.
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 2
B. Найди целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2 и при этом траектория вычислений содержит число 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Воспользуемся чудо-шаблоном из статьи по 23 Заданию НОВОГО бесплатного курса ЕГЭ по информатике 2025.
def F(x, y): if x == y: return 1 if x < y: return 0 if x > y: return F(x-2, y) + F(x//2, y) print(F(38, 16)*F(16, 2))
Текстовый файл состоит из цифр 0, 6, 7, 8, 9 и знаков арифметических операций «–» и «*» (вычитание и умножение). Определите максимальное количество символов в непрерывной последовательности, которая является корректным арифметическим выражением с целыми неотрицательными числами. В этом выражении никакие два знака арифметических операций не стоят рядом, в записи чисел отсутствуют незначащие (ведущие) нули и число 0 не имеет знака.
В ответе укажите количество символов.
Похожую задачу мы разбирали в статье. Название задачи "ЕГЭ по информатике 8.06.24, мат. последовательность". Там есть разбор и в текстовой форме, и в видеоформате.
Эта задача отличается тем, что теперь число ноль тоже подходит. В той задаче рассматривали только натуральные числа (т.е. > 0).
Так же, как и в прошлой задаче будем считать, что хотя бы один знак "-" или "*" должен быть в арифметическом выражении.
f=open('demo_2025_24.txt') s=f.read().strip() s=s.replace('-', '*') a=s.split('*') st='' kmax=0 for i in range(len(a)): if (a[i]!='') and ((a[i][0]!='0') or (a[i]=='0')): # Формируем цепочку-кандидата if st!='': st = st + '*' + a[i] else: st = st + a[i] if st.find('*')!=-1: kmax=max(kmax, len(st)) else: if a[i]!='' and a[i][0]=='0': if a[i].count('0')!=len(a[i]): a[i]=a[i].lstrip('0') else: a[i]='0' st=a[i] else: st = '' print(kmax)
Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.
Например, для числа 20 М = 2 + 10 = 12.
Количество строк в таблице для ответа избыточно.
Будем работать с делителям так, как мы обсуждали в статье из курса ЕГЭ по информатике 2025.
count=0 for i in range(800001, 900000): m=0 a=[] for j in range(2, int(i**0.5)+1): if i%j==0: a.append(j) b=i//j if j!=b: a.append(b) if len(a)>=1: a.sort() m=a[0]+a[-1] if m%10==4: print(i, m) count = count + 1 if count == 5: break
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы.
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917.
Применим функцию fnmatch.
from fnmatch import * for i in range(1917, 10**10+1, 1917): if fnmatch(str(i), '3?12?14*5'): print(i, i//1917)
Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.
Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 25 % мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 25 % студентов. Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».
В ответе запишите два целых положительных числа: сначала ID студента, который занимает последнее место среди студентов с повышенной стипендией, затем ID первого в рейтинговом списке студента, который имеет более двух «двоек».
Входные данные
В первой строке входного файла находится число N, обозначающее количество студентов (целое положительное число, не превышающее 10 000). Каждая из следующих N строк содержит 5 чисел через пробел: ID студента (целое положительное число, не превышающее 100 000) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов N кратно 4 и хотя бы один студент имеет более двух «двоек».
Во входном файле все ID различны.
Выходные данные
Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.
Типовой пример организации данных во входном файле
При таких исходных данных рейтинговый список ID имеет вид: 4 6 10 1 3 7 13 2. Ответ: 6 13.
Посмотрим в файл. Количество студентов равно n = 9964. Двадцать пять процентов от общего числа - это целое число:
Найдём, какой средний балл будет у последнего студента, который получит повышенную стипендию.
f=open('demo_2025_26.txt') n=int(f.readline()) # Количество мест s = int( 0.25 * n ) a = [] for i in range(n): st = f.readline().split() x, y, z, w, m = int(st[0]), int(st[1]), int(st[2]), int(st[3]), int(st[4]) if y!=2 and z!=2 and w!=2 and m!=2: a.append(((y+z+w+m)/4, x)) a.sort(reverse=True) print(a[s-1][0])
Получается 4.25.
Найдём количество студентов, которые входят в эти 25% и имеют средний балл 4.25.
k=0 for i in range(s): if a[i][0]==4.25: k=k+1 print(k)
Получается k=1253.
Теперь добавим наименьшие ID в список b первых k участников, которые имеют средний балл 4.25
b=[] k=1253 for i in range(len(a)-1, -1, -1): if a[i][0]==4.25: if k>0: b.append(a[i][1]) k -= 1 print(b[-1])
Последний элемент списка b[-1] - и будет ответ на первый вопрос. Получается 52326.
Займёмся вторым вопросом. Найдём учеников, которые получили ровно 3 двойки.
f=open('demo_2025_26.txt') n=int(f.readline()) # Количество мест s = int( 0.25 * n ) a = [] for i in range(n): st = f.readline().split() x, y, z, w, m = int(st[0]), int(st[1]), int(st[2]), int(st[3]), int(st[4]) if st.count('2')==3: a.append(x) a.sort() print(a[0])
Получается 635. Это и есть ответ на второй вопрос.
Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения Px × 10 000 , затем целую часть произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию. Для выполнения задания используйте данные из прилагаемого файла.
Нам дали данные в виде текстового файла и в виде Excel файла.
В начале откроем Excel для файла A.
Выделим столбцы A и B. Выберем вставка -> диаграмма -> точечная. Получим такую картину:
Здесь мы чётко видим два кластера.
Найдём перебором координаты центра каждого кластера.
f=open('demo_2025_27_А.txt') f.readline() a1=[] a2=[] for s in f.readlines(): s = s.replace(',', '.').split() x, y = float(s[0]), float(s[1]) if x < 1: a1.append((x, y)) else: a2.append((x, y)) sm1 = sm2 = 10**10 x1=y1=x2=y2=0 for i in range(len(a1)): d_sm = 0 for j in range(len(a1)): d_sm += ((a1[j][0] - a1[i][0])**2 + (a1[j][1] - a1[i][1])**2) ** 0.5 if d_sm < sm1: x1 = a1[i][0] y1 = a1[i][1] sm1 = d_sm for i in range(len(a2)): d_sm = 0 for j in range(len(a2)): d_sm += ((a2[j][0] - a2[i][0])**2 + (a2[j][1] - a2[i][1])**2) ** 0.5 if d_sm < sm2: x2 = a2[i][0] y2 = a2[i][1] sm2 = d_sm Px = (x1+x2)/2 Py = (y1+y2)/2 print(int(Px*10000), int(Py*10000))
Здесь завели два списка a1 и a2. В первый список будем класть точки из первого кластера, во второй список из второго кластера.
Визуально видно в диаграмме Excel, что точки из первого кластера по оси X меньше единицы, а из второго больше.
Перебором пробуем для каждой точки из кластера найти сумму расстояний до всех точек этого кластера. Где получается минимальная длина, запоминаем координаты x и y этой точки.
Для файла B решается аналогично.
f=open('demo_2025_27_А.txt') f.readline() a1=[] a2=[] a3=[] for s in f.readlines(): s = s.replace(',', '.').split() x, y = float(s[0]), float(s[1]) if x < 3 and y < 4: a1.append((x, y)) else: if x<5 and y>6: a2.append((x, y)) else: a3.append((x, y)) sm1 = sm2 = sm3 = 10**10 x1=y1=x2=y2=x3=y3=0 for i in range(len(a1)): d_sm = 0 for j in range(len(a1)): d_sm += ((a1[j][0] - a1[i][0])**2 + (a1[j][1] - a1[i][1])**2) ** 0.5 if d_sm < sm1: x1 = a1[i][0] y1 = a1[i][1] sm1 = d_sm for i in range(len(a2)): d_sm = 0 for j in range(len(a2)): d_sm += ((a2[j][0] - a2[i][0])**2 + (a2[j][1] - a2[i][1])**2) ** 0.5 if d_sm < sm2: x2 = a2[i][0] y2 = a2[i][1] sm2 = d_sm for i in range(len(a3)): d_sm = 0 for j in range(len(a3)): d_sm += ((a3[j][0] - a3[i][0])**2 + (a3[j][1] - a3[i][1])**2) ** 0.5 if d_sm < sm3: x3 = a3[i][0] y3 = a3[i][1] sm3 = d_sm Px = (x1+x2+x3)/3 Py = (y1+y2+y3)/3 print(int(Px*10000), int(Py*10000))
Удачи на экзаменах!
