15 задание ЕГЭ информатика

Задание 15 – логическое выражение с параметром A (отрезок на числовой прямой, ДЕЛ(x, A), поразрядная конъюнкция x & A), которое должно быть истинно при всех x. Найти наименьшую/наибольшую длину отрезка или значение A. 1 балл.

Способ 1 – перебор на Python (универсальный). Для отрезков: перебирай концы A с шагом и проверяй x с дробным шагом.

def ok(a1, a2):
    for t in range(0, 2400):
        x = t / 40                     # шаг 0,025, чтобы поймать нецелые точки
        P = 10 <= x <= 30
        Q = 20 <= x <= 50
        A = a1 <= x <= a2
        if not ((not P) or ((not Q) or A)):   # (x∈P) → ((x∈Q) → (x∈A))
            return False
    return True

print(min(a2 - a1 for a1 in range(60) for a2 in range(a1, 60) if ok(a1, a2)))

Для ДЕЛ: ДЕЛ(x, A) пиши x % A == 0, перебирай A от 1 и x от 1 до 1000. Для поразрядной конъюнкции: (x & A) != 0.

Способ 2 – логически. Упрости выражение: $P\to (Q\to A)=\mathrm{\neg }P\vee \mathrm{\neg }Q\vee A$. Оно должно быть истинно везде, значит, где P и Q оба истинны, должно быть истинно A: A ⊇ P ∩ Q.

Разобранный пример. P = [10; 30], Q = [20; 50]. Нужно A ⊇ P ∩ Q = [20; 30]. Наименьшая длина A = 30 − 20 = 10. Программа выше выводит 10.

Ловушки: отрезки замкнутые – концы входят, сравнения <= а не <; при поиске максимальной длины A может быть «не больше» какого-то отрезка – тогда A ⊆ …; шаг проверки x должен быть дробным, иначе можно пропустить дырку между целыми.