Анализ логически выражений. Метод опасной зоны

Задание 15 на координатной плоскости: один приём вместо десятка формул — найди зону, где всё держится на A, и её крайнюю точку

Выражение в задании 15 должно быть истинно во всех точках (x, y). Чтобы не перебирать всё, поймём, где оно вообще может стать ложным.

Разделим условия на две группы:

• Прикрытие — все условия без A. Там, где хотя бы одно из них истинно, всё выражение уже истинно, и значение A не важно.
• Спасатель — условие с A. Оно «включается» только там, где прикрытие отказало.

Опасная зона — это точки, где всё прикрытие разом ложно. Только здесь выражение держится на спасателе. Значит задача сводится к одному: подобрать A так, чтобы спасатель был истинным во всей опасной зоне.

Спасатель сравнивает A с некоторой величиной V. В разных задачах V своя: x·y, или x, или y. Чтобы спасатель был истинным во всей зоне, надо смотреть на его форму.

Что мы ищем? — крайнее значение величины V по точкам опасной зоны: минимум, если A стоит снизу, и максимум, если A стоит сверху.

Как находить крайнюю точку (шаг 4)

Крайнее значение V почти всегда достигается на границе опасной зоны — в её углу или на граничном отрезке. Алгоритм такой:

1. выпиши величину V;
2. нужен максимум → возьми точку зоны, где V наибольшее;
   нужен минимум → точку, где V наименьшее;
3. подставь координаты этой точки в V — получишь границу для A.

Если в условии есть ≠, зона — не область, а прямая, и крайнюю точку ищем вдоль этой прямой (по её целым точкам).

Опасная зона — пересечение «перевёрнутых» условий прикрытия. Вот как каждое из них становится ложным:

Задачи интерактива взяты из ЕГЭ 2025 года разных волн. Переключай задачу и двигай ползунок A. Зелёные точки — где спасатель уже выполнен, красные — где нарушен (в них выражение ложно). Золотое кольцо — крайняя точка зоны. Двигай A, пока все точки не позеленеют (а для линейной задачи — пока прямоугольник не накроет всю зону): это и есть граничное A.

10.06 — произведение · ответ 120

Условие: (x·y > A) ∨ (x > y) ∨ (11 > x), наибольшее A, при целых неотрицательных x, y.

Спасатель — x·y > A (форма «V > A» → ищем минимум, V = x·y).
Прикрытие: x>y ложно при x≤y, 11>x ложно при x≥11.
Зона: x ≥ 11 и x ≤ y. Минимум произведения — в углу (11; 11), равен 121.
Нужно 121 > A → наибольшее A = 120.

11.06 — дырка (≠) · ответ 36

Условие: (2x + y ≠ 110) ∨ (x < y) ∨ (A < x), наибольшее A, при целых неотрицательных x, y.

Спасатель — A < x (форма «A < V» → ищем минимум, V = x).
Прикрытие: 2x+y≠110 ложно на прямой 2x+y=110, x<y ложно при x≥y.
Зона: целые точки прямой 2x+y=110 с x ≥ y. Наименьший x там — из x ≥ 110−2x следует x ≥ 37 (точка (37; 36)).
Нужно A < 37 → наибольшее A = 36.
 

19.06 — линейное · ответ 64

Условие: (x < A) ∧ (y < 3A) ∨ (2x + y > 128), наименьшее A, при целых положительных x, y.

Спасатель — сразу два условия x < A и y < 3A (форма «V < A» → ищем максимумы).
Прикрытие: 2x+y>128 ложно при 2x+y≤128.
Зона: треугольник 2x+y ≤ 128. Из x<A: max x = 63 → A ≥ 64. Из y<3A: max y = 126 → 3A > 126 → A ≥ 43.
Берём жёстче → наименьшее A = 64.

Если аналитика буксует — проверь перебором. Но наивный двойной цикл по всей плоскости при больших порогах не успеет:

наивно · медленно# O(n²): двойной цикл по всей плоскости
for A in range(30000):
    if all(F(x, y, A) for x in range(20002)
                    for y in range(20002)):   # ~4·10⁸ на каждое A → не успеет
        ...

Идея ускорения. Крайнее значение V достигается на границе зоны — внутри «хуже» не бывает. Значит достаточно пройти только границу, а это один цикл, O(n):

• линейная зона 3x + y ≤ N: граница — отрезок 3x + y = N; для каждого x берём крайний y = N − 3x (один y на один x);
• дырка (≠): зона и так прямая L = N — перебираем её целые точки;
• произведение: минимум в углу — можно вообще без цикла, подставив угол.

умно · быстро# O(n): только граница зоны
N = 20001                       # пример: (x<A) ∧ (y<2A) ∨ (3x+y>N)
for A in range(1, 30000):
    if all(x < A and N-3*x < 2*A          # крайний y = N − 3x
           for x in range(1, N//3+1) if N-3*x >= 1):
        print(A); break                  # 10000, мгновенно