Шаблон функции выражения

# выносим ВЫРАЖЕНИЕ в функцию
def f(A, x):
    # ... здесь логическое выражение, вернуть True/False
    return (not P) or Q

Функция выражения (демо-2026)

def seg(L, R, x):           # принадлежность точки отрезку [L; R]
    return L <= x <= R

def f(a, b, x):             # A — это отрезок [a; b]
    P = seg(25, 64, x)
    Q = seg(40, 115, x)
    A = seg(a, b, x)
    # (x∈P) → (((x∈Q) ∧ ¬(x∈A)) → ¬(x∈P))
    return (not P) or ((not (Q and not A)) or (not P))

Метод на числовой оси — два примера

Условные обозначения: тонкие скобки — отрезки P и Q (ножки касаются границ); жирная скобка — искомый A; полоса на самой прямой — результат выражения без A (зелёное = истина, красное = дыра, за которую отвечает A).

Пример 1 (часть с A = (x∈A) — A накрывает).
Выражение (x∈P) → ((x∈Q) ∨ (x∈A)) упрощаем: ¬P ∨ Q ∨ A. Часть без A это ¬P ∨ Q; она ложна только там, где x входит в P, но не в Q. Эту дыру обязан накрыть A.

A должен накрыть дыру [10; 30] → минимальная длина 20.

Пример 2 (часть с A = ¬(x∈A) — A обходит). Выражение (x∈A) → (x∈P) упрощаем: ¬A ∨ P. Часть без A это P; она ложна везде вне P. На этой дыре нужна ¬(x∈A), то есть A туда заходить нельзя — значит A целиком сидит внутри P.

A не должен задевать дыру (всё вне P) → A ⊆ [10; 50], максимальная длина 40.

Функция выражения + сбор A

P = set(range(2, 21, 2))     # пример: {2,4,...,20}
Q = set(range(5, 51, 5))     # пример: {5,10,...,50}

def f(A, x):                 # A — множество; истинность выражения для данного x
    # ((x∈A) → (x∈P)) ∧ ((x∈Q) → ¬(x∈A))
    return ((x in A) <= (x in P)) and ((x in Q) <= (not (x in A)))

A_max, A_min = set(), set()
for x in range(0, 1000):
    can_in  = f({x}, x)      # выражение истинно, если x ЛЕЖИТ в A
    can_out = f(set(), x)    # выражение истинно, если x НЕ лежит в A
    if can_in:               # для МАКСИМУМА берём всё допустимое
        A_max.add(x)
    if not can_out:          # для МИНИМУМА — только обязательное
        A_min.add(x)

print(len(A_max), sum(A_max))    # наибольшее множество: размер и сумма
print(len(A_min), sum(A_min))    # наименьшее множество: размер и сумма

Функция выражения

def D(n, m):
    return n % m == 0

def f(A, x):
    # ДЕЛ(120, A) ∧ ((ДЕЛ(x,70) ∧ ДЕЛ(x,30)) → ДЕЛ(x,A))
    return D(120, A) and ((D(x, 70) and D(x, 30)) <= D(x, A))

Функция выражения

def f(A, x):
    a = (x & 51) != 0       # СКОБКИ обязательны: & ниже по приоритету, чем !=
    b = (x & A)  == 0
    c = (x & 25) != 0
    # (x&51≠0) → ((x&A=0) → (x&25≠0))
    return (not a) or ((not b) or c)

Функция выражения и поиск минимума/максимума

def f(A, x, y):
    # (x·y > A) ∨ (x > y) ∨ (11 > x)
    return (x * y > A) or (x > y) or (11 > x)

ok = [A for A in range(0, 1000)
      if all(f(A, x, y)
             for x in range(0, 200)        # неотрицательные → с 0
             for y in range(0, 200))]
print(max(ok))    # наибольшее A
print(min(ok))    # наименьшее A

Метод областей на плоскости

Пример: (x ≥ A) ∨ (y ≥ A) ∨ (x + y ≤ 40), истинно при всех натуральных x, y. Найти наибольшее A.

(x≥A) и (y≥A) закрывают верхнюю и правую полуплоскости; (x+y≤40) — нижний треугольник. Остаётся «дыра» — квадрат x, y < A. Худшая точка — угол (A−1, A−1); она обязана попасть под прямую: 2(A−1) ≤ 40 → A ≤ 21. Ответ 21.

Оптимальный перебор для больших чисел

Не перебирай 0..огромное по обеим осям — это и долго, и не влезает. Опасны только точки, где «всё остальное» ложно, а это ограниченная зона (здесь x, y < A). Перебирай именно её:

def f(A, x, y):
    return (x >= A) or (y >= A) or (x + y <= 40)

ans = 0
for A in range(1, 200):
    if all(f(A, x, y)
           for x in range(1, A)        # опасны только x < A
           for y in range(1, A)):      #          и  y < A
        ans = A
print(ans)   # 21

Для совсем больших границ идут дальше: для каждого x вычисляют граничный y аналитически (из уравнения области) и проверяют только критические точки границы — двойной перебор сводится к одинарному.

Что уменьшаем, что увеличиваем

Одной фразой: дизъюнкция A<… → минимизируем большую координату (баланс), A на 1 меньше; конъюнкция A>… → максимизируем её (вершина), A на 1 больше.

Три примера с большими числами

Проверка кодом (умный перебор по границе)

Перебираем не всю плоскость, а только границу зоны — один цикл, O(n):

# пример 1: зона — прямая 2x + 3y = N; спасатель A < max(x, y)
N = 500000
mn = min(max(x, (N-2*x)//3)
         for x in range(0, N//2+1)
         if (N-2*x) % 3 == 0)        # только целые точки прямой
print(mn - 1)                        # 99999

Пример 2: пройти границу 4x+y=850000, взять min(max(x, 850000−4x)) → 169999. Пример 3: вершины всего две — цикл не нужен, max(300000, 900000)=900000 → 900001.

Функция выражения

def D(n, m):   return n % m == 0
def seg(L, R, x): return L <= x <= R

def f(A, x):
    # ДЕЛ(x, A) ∨ ((x ∈ [60;80]) → ¬ДЕЛ(x, 22))
    return D(x, A) or ((not seg(60, 80, x)) or (not D(x, 22)))

Универсальный каркас под любой редкий формат

# 1) выражение → в функцию f(A, x) или f(A, x, y)
# 2) выбрать квантор: all (для всех) или any (существует)
# 3) выбрать область x: range(1,N) натуральные / range(0,N) неотрицательные / i/2 действительные
# 4) выбрать направление A: range(BIG,0,-1) максимум / range(1,BIG) минимум
def f(A, x):
    return ...    # сюда логику из условия

for A in range(1, 10**6):              # минимум; для максимума — реверс
    if all(f(A, x) for x in range(1, 100000)):
        print(A); break