ЕГЭ Инфа PRO

🎯 ЕГЭ, задание 23: ищем минимальную длину пути из 1 в 100, но только если она в диапазоне [18 000; 22 000].

Найдите минимальную длину пути из вершины с номером 1 в вершину с номером 100 среди всех путей с длинами от 18000 до 22000 (включительно). Гарантируется, что хотя бы один такой маршрут существует. Запишите в ответе целую часть найденной длины.

Поэтому берём надёжную архитектуру: чёткие условия, настоящая бесконечность, никакой двойной арифметики.

✅ Готовый код — можно копировать на практику:

from collections import defaultdict
from functools import lru_cache

graf = defaultdict(list)
with open("23.txt") as f:
for line in f:
st, end, dl = line.split()
graf[int(end)].append((int(st), float(dl)))

@lru_cache(maxsize=None)
def dlina(x, sm):
if x == 1:
return 0.0 if 18000 <= sm <= 22000 else float('inf')
mn = float('inf')
for prev, w in graf[x]:
res = dlina(prev, sm + w)
if res != float('inf'):
mn = min(mn, res + w)
return mn

print(int(dlina(100, 0.0)))

#егэинформатика #задание23 #графы_егэ #алгоритмы_егэ #python_для_егэ #разбор_задания23 #айти #хрупкие_решения #подготовка_к_егэ

🧠 Разбор задачи: кратчайший путь ≤ 6 рёбер, отсекаем тупики/23 задания ЕГЭ
🎯 Задача

Найти целую часть длины кратчайшего пути из вершины 1 в вершину 100 в ориентированном ациклическом графе. Путь должен содержать не более 6 рёбер.

🔄 Хитрость решения: идём от конца к началу
Вместо того чтобы стартовать из 1 и натыкаться на тупики, запускаем поиск из 100 к 1 по обратному графу.
Почему это удобно: ветка, которая не ведёт к 1, просто не даст валидного пути — такие «лишние» вершины автоматически отсекаются.

💻 Код (обратный обход + кэш)

from collections import defaultdict
from functools import lru_cache

graf = defaultdict(list)
# Строим ОБРАТНЫЙ граф: end -> st
with open("23-1.txt") as f:
for line in f:
st, end, dl = line.split()
graf[int(end)].append((int(st), float(dl)))

@lru_cache(maxsize=None)
def dlina(x, steps):
# База: дошли до вершины 1 — путь найден
if x == 1:
return 0

# Лимит рёбер: нельзя больше 6 шагов
if steps >= 6:
return float('inf')

mn = float('inf')
for prev, w in graf[x]:
res = dlina(prev, steps + 1)
if res != float('inf'):
mn = min(mn, res + w)

return mn

result = dlina(100, 0)
print(int(result))

#егэ2024 #егэинформатика #задание23 #графы_егэ #работа_с_графами #алгоритмы_егэ #python_для_егэ #разбор_задания23 #подготовка_к_егэ_информатика #задачи_на_графы

Задача 27 ЕГЭ по информатике — кластеризация частиц
Рассматриваются частицы на плоскости, обладающие следующими характеристиками: декартовы координаты, вектор скорости, масса, а также признак, характеризующий внутреннее строение частицы, обозначаемый числами отI доVII (в римской системе счисления).

Учёный решил провести кластеризацию частиц по значениям их кинетической энергии, то есть разбить их множество на K непересекающихся непустых подмножеств (кластеров), таких, что модуль разности кинетических энергий любых двух частиц каждого подмножества не превосходит значения R. Гарантируется, что такое разбиение существует и единственно для заданного R.

Будем называть центром кластера такую его частицу, для которой сумма модулей разности кинетических энергий со всеми остальными частицами этого кластера минимальна. Для каждого кластера гарантируется единственность его центра.

В каждой строке текстового файла хранится информация об одной частице: координаты x и y, проекции вектора скорости Vx и Vy, масса m и признак.

Сортировка и кластеризация
Логика
Сортируем все частицы по энергии (по первому элементу списка).
Идём по отсортированному списку и добавляем частицы в текущий кластер, пока разница между энергией текущей частицы и первой частицей кластера ≤ 2.0.
Если разница больше 2.0 — закрываем текущий кластер и начинаем новый.
В конце добавляем последний кластер.
При отсортированном списке условие «разность энергий любых двух частиц в кластере ≤ 2.0» эквивалентно «разность между первой и последней частицей кластера ≤ 2.0».
#ЕГЭИнформатика #Задача27 #PythonДляЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #КластеризацияВЕГЭ

Рекурсия с умом: зачем кэшировать и как не утонуть в вызовах

from functools import lru_cache

@lru_cache(maxsize=None)
def g(n):
if n<=20:
return n+2
else:
return g(n-3)+1
for n in range(37812):
g(n)
print(3*g(n-3)+7)

Что делает код:
from functools import lru_cache и @lru_cache(maxsize=None):
Эти строки подключают и применяют декоратор кэширования. Он сохраняет результаты вызова функции g(n) для каждого переданного n. Это критически важно, так как без кэша рекурсивные вызовы привели бы к экспоненциальному росту времени выполнения (множество повторных вычислений одних и тех же значений). С кэшем каждое значение вычисляется ровно один раз, и сложность становится линейной.

Функция g(n):
Это прямая программная реализация математического определения функции G(n).
Если n≤20, возвращается n+2.
Если n>20, функция вызывает сама себя для n−3 и прибавляет 1.

Цикл for n in range(37812): g(n)
Этот цикл последовательно вычисляет значения функции g для всех чисел от 0 до 37811.
Зачем это нужно? В данном конкретном коде это избыточный шаг, если мы вызываем g(37808) сразу после цикла. Функция с @lru_cache сама по себе вычислит все необходимые промежуточные значения при первом вызове g(37808) (она рекурсивно спустится до базового случая).
Однако такой цикл часто пишут в задачах ЕГЭ по информатике, чтобы «прогреть» кэш или гарантировать, что все значения до нужного предела уже посчитаны, избегая даже малейшей вероятности переполнения стека при глубокой рекурсии (хотя при шаге 3 глубина для 37811 вполне допустима).
Ответ: 37861
#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_3eB0F2 #ЕГЭ_Задание16 #Рекурсия #PythonДляЕГЭ #ИнформатикаСНуля #functools_import_lru_cache

Хочешь ещё больше лайфхаков по оптимизации кода, разборов алгоритмов или задач на рекурсию? Подписывайся на канал — впереди ещё куча интересного! 😉🔔

#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #PythonДляЕГЭ #ИнформатикаСНуля

s = 6*512**395 + 7*64**396 + 3*8**398 + 5*8**393 + 300
k = 0
while s != 0:
if s % 64 == 0:
k += 1
s = s // 64
print(k)
Что делает код:
Вычисляет значение выражения S.
В цикле последовательно делит S на 64, проверяя остаток от деления:
Если остаток 0, значит, текущая младшая цифра в 64‑ричной записи — ноль, счётчик k увеличивается.
Затем S заменяется на целую часть от деления на 64 (сдвиг вправо на одну цифру в 64‑ричной системе).
Цикл продолжается, пока S не станет 0.
Выводит количество нулевых цифр — то есть количество раз, когда остаток от деления на 64 был 0.

#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_F946FA #ЕГЭ_Задание14 #информатика #системы_счисления #длинная_арифметика #PythonДляЕГЭ #ИнформатикаСНуля

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
if n<10: return 1
else:
return (n+3)*f(n-3)
for n in range(247564):
f(n)
print((f(247563)//519-477*f(247560))//f(247557))
Ответ: 1431
#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_67F7F0 #ЕГЭ_Задание16 #Рекурсия #PythonДляЕГЭ #ИнформатикаСНуля #functools_import_lru_cache

🔥 Оптимизируем рекурсию: считаем F(15) с мемоизацией! 🔥

Сегодня разберём крутой приём, который делает рекурсивные функции в разы быстрее — мемоизацию. Смотри, как это выглядит в коде: 👇

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
if n < 3:
return 1
if n % 2 == 0:
return f(n - 2) - f(n - 1)
return 2 * f(n - 1) - f(n - 2)

print(f(15))

🤔 Что тут происходит?

from functools import lru_cache — импортируем декоратор для кэширования результатов. Это как «записная книжка» для функции: она запоминает, что уже посчитала, и не тратит время на повторные вычисления.
@lru_cache(maxsize=None) — вешаем декоратор на функцию. Параметр maxsize=None означает, что ограничений по количеству сохранённых результатов нет — функция может запомнить сколько угодно значений.
if n < 3: return 1 — базовый случай рекурсии. Это «стоп-сигнал», без которого функция уходила бы в бесконечный цикл.
if n % 2 == 0: return f(n - 2) - f(n - 1) — для чётных n используем формулу из условия задачи.
return 2 * f(n - 1) - f(n - 2) — для нечётных n применяем вторую формулу.
print(f(15)) — запускаем функцию и выводим результат.

🚀 Почему это круто?

Без мемоизации при больших n функция многократно пересчитывает одни и те же значения — это сильно замедляет работу. С @lru_cache каждое значение считается только один раз, а потом просто берётся из кэша. Это как выучить таблицу умножения вместо того, чтобы каждый раз складывать числа! 😄

💡 Полезный факт: lru_cache использует стратегию LRU (Least Recently Used) — если бы мы задали конкретный maxsize, то при его превышении из кэша удалялись бы самые старые или наименее используемые значения. Но в нашем случае мы не ограничиваем размер кэша, чтобы сохранить все результаты.

Хочешь ещё больше лайфхаков по оптимизации кода, разборов алгоритмов или задач на рекурсию? Подписывайся на канал — впереди ещё куча интересного! 😉🔔

#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_859446 #ЕГЭ_Задание16 #Рекурсия #PythonДляЕГЭ #ИнформатикаСНуля #functools_import_lru_cache

🧠 Разбор задачи № D6DFe2 (ЕГЭ по информатике, задание 24)

Сегодня разберём типичную задачу на обработку строк: нужно найти максимальную длину подстроки, где:

подстрока 2025 встречается ≥ 90 раз;
буква Y встречается ровно 80 раз.

💻 Код на Python:

f=open("D6DFe2")
s=f.readline()
s=s.replace("Y","Y ").split()
mx=0
for i in range(len(s)-81):
st="".join(s[i:i+81])[:-1]
if st.count("2025")>=90:
mx=max(mx,len(st))
print(mx)

Построчный разбор
f=open("D6DFe2") и s=f.readline(): Открывается файл и считывается первая строка в переменную s. На этом этапе всё верно — у нас есть исходная строка с данными.
s=s.replace("Y","Y ").split(): Это самая критическая часть. Вы заменяете каждую букву Y на "Y " (буква плюс пробел), а затем разбиваете строку по пробелам.
st="".join(s[i:i+81])[:-1]: Вы склеиваете 81 фрагмент в одну строку и удаляете последний символ ([:-1]).
if st.count("2025")>=90: Проверка количества вхождений подстроки 2025. Это условие верное.
mx=max(mx,len(st)): Обновление максимума. Логика верная, но так как st было испорчено на шаге 4, результат будет неверным.

Жми кнопку «Подписаться» — и не пропускай новые разборы! 👇
#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_D6DFe2 #ЕГЭ_Задание25 #Алгоритмы #PythonДляЕГЭ #ИнформатикаСНуля

Разбираем код как конструктор: ищем числа с “правильными” простыми множителями

Что делает программа? 🤔
Ищет первые 5 чисел > 1 760 906, которые — произведение двух простых множителей (могут совпадать), причём в записи каждого множителя ровно одна цифра «1». Выводит число и больший множитель.

Ключевые блоки кода 🧩
1. Подготовка списка подходящих простых чисел

prost=[]
k=0
def pr(n):
for i in range(2,int(n**0.5)+1):
if n%i==0: return False
return True
for x in range(2,1_760_906+1):
if pr(x) and str(x).count("1")==1: prost.append(x)

pr(n) — функция проверки числа на простоту. Она перебирает делители от 2 до квадратного корня из n. Если хоть один делит n без остатка — число не простое. Иначе — простое ✅.
Далее идёт цикл от 2 до 1 760 906. Для каждого числа проверяется:
💡является ли оно простым (pr(x));
💡содержит ли в своей десятичной записи ровно одну цифру «1» (str(x).count("1") == 1).
Если оба условия выполняются — число добавляется в список prost.
⚠️ Важный нюанс: мы заранее собираем все подходящие простые числа до стартовой границы поиска. Это нужно, чтобы потом быстро проверять, являются ли множители искомых чисел «правильными».

2. Поиск нужных составных чисел

for n in range(1_760_907,10**9):
a=set()
for x in range(2,int(n**0.5)+1):
if n%x==0:
if x in prost: a.add(x)
if n//x in prost: a.add(n//x)

Перебираем числа n, начиная с 1 760 907 (первое число больше 1 760 906) и до миллиарда (это просто «запасной» верхний предел).
💡 Почему set()? Чтобы избежать дубликатов (например, если оба множителя одинаковые — как в случае
p × p).
3. Проверка условия «произведение ровно двух простых множителей»

if len(a)>0:
mx=0
for x in a:
for y in a:
if x*y==n:
mx=max(mx,x,y)
if mx!=0:
print(n,mx)
k+=1
if k==5: break

Хочешь прокачивать навыки в решении задач по информатике и разбирать код без «воды»? 😎

Подписывайся на канал — там регулярно выкладываю:
* разбор типовых и олимпиадных задач;
* лайфхаки по оптимизации кода;
* готовые шаблоны решений на Python.

Жми кнопку «Подписаться» — и не пропускай новые разборы! 👇

#ЕГЭ #РазборЗадач #ПодготовкаКЕГЭ #ФИПИ_3659c9 #ЕГЭ_Задание25 #Алгоритмы #PythonДляЕГЭ #ИнформатикаСНуля