Повышенный (1 балл) Время: 4-7 мин Python all() Побитовое & Перебор A Все задачи №15 в каталоге

Задание №15. Подбираем параметр A, чтобы формула была всегда истинной

Тема: Тождественная истинность, побитовая конъюнкция, делимость и отрезки

Дана формула с параметром A и переменной x. Надо найти наименьшее (или наибольшее) A, при котором формула истинна при любом x. Два основных вида: побитовое И и отрезки с делимостью.

Что от тебя хотят

Есть формула с неизвестным параметром A, например (x & 73156 = 0) → ((x & 63567 ≠ 0) → (x & A ≠ 0)). Формула должна быть истинна при любом x. Надо найти наименьшее подходящее A.

Идея: найди «опасные» x

Импликация A → B ложна только когда A истинно, а B ложно. Значит, формула ложна для тех x, у которых все условия до последнего выполнены, а последнее (про A) нарушено. Пусть компьютер найдёт все x, для которых «подготовительная» часть истинна. Это и есть опасные x. Тогда A подходит, если каждый опасный x «закрыт» условием про A.

Как это превращается в код

Собери список опасных x: тех, у которых все условия до последнего выполнены.
Переберай A по возрастанию. Для каждого проверь через all(...), что условие про A верно для всех опасных x.
Первое подходящее A и есть наименьшее.

В Python знак & стоит выше по приоритету, чем == и !=. Поэтому x & A != 0 читается как (x & A) != 0, то есть именно так, как в условии. Скобки писать не обязательно (в отличие от языка C).

Разбор 1: побитовая конъюнкция

Для какого наименьшего натурального A формула (x & 73156 = 0) → ((x & 63567 ≠ 0) → (x & A ≠ 0)) тождественно истинна?

Опасные x: те, у которых x & 73156 == 0 и x & 63567 != 0. Их в диапазоне до 140 000 всего 624. Верхнюю границу берём чуть выше 2¹⁷ = 131 072, потому что у числа 73156 нужные биты не дальше семнадцатого. Дальше первый же A, который «зацепляет» каждый опасный x, это 57355. Перебор по опасным работает за доли секунды, а прямой перебор по всем x для каждого A занял бы около 20 секунд.

Разбор 2: делимость и отрезок

ДЕЛ(n, m) означает «n делится на m». Отрезок B = [10; 40]. Найдите наименьшую возможную длину отрезка A, при которой формула (x ∈ A) ∨ ((x ∈ B) → ¬ДЕЛ(x, 6)) тождественно истинна.

Формула ложна только если x не в A, при этом x в B и x делится на 6. Такие x «опасные», и они обязаны оказаться в A.
Опасные x: числа от 10 до 40, кратные 6, это 12, 18, 24, 30, 36.
A должен целиком накрыть их. Отрезок от 12 до 36 имеет длину 24, и это наименьший возможный.

Ответ: 24. Второе окно находит наименьший и наибольший опасный x и вычитает.

Для отрезков с полуцелыми границами (например, 12,5 и 37,5) перебирай x с шагом 0,5: [i / 2 for i in range(20, 90)].

Разновидности и прототипы задания на экзамене

Тип 1: Побитовая конъюнкция (x & A)

Находим «опасные» x, для которых остальная часть формулы ложна, и требуем, чтобы A их «закрыл».

Тип 2: Делимость и отрезок

Выясняем, какие x обязаны попасть в A, и берём их наименьший и наибольший.

Тип 3: Два отрезка

Формула про принадлежность отрезкам P и Q. Идём по целым точкам, а при полуцелых границах шаг 0,5.

Код решения на Python

Запустить код в онлайн-песочнице

x & A != 0all(... for x in bad)bad.append(x)max(need) - min(need)break

Побитовое И: ищем наименьшее A

bad = []
for x in range(1, 140000):
    if x & 73156 == 0 and x & 63567 != 0:
        bad.append(x)

for A in range(1, 100000):
    if all(x & A != 0 for x in bad):
        print(A)
        break

Задача из базы, которую решает этот код Открыть в песочнице

Делимость и отрезок: длина A

need = []
for x in range(10, 41):
    if x % 6 == 0:
        need.append(x)

print(max(need) - min(need))

Задача из базы, которую решает этот код Открыть в песочнице

Типичные ошибки

✕ Не так

Начать перебор x с нуля при делимости

x % 0 даёт ZeroDivisionError, а натуральные числа начинаются с 1.

✓ Так

Диапазон натуральных x: range(1, ...).

✕ Не так

Перебирать A и x вложенными циклами «в лоб»

Для A порядка 60 000 и x порядка 140 000 программа считает десятки секунд.

✓ Так

Сначала собрать список опасных x, потом перебирать A только по нему.

✕ Не так

Считать длину отрезка по количеству точек

Отрезок от 12 до 36 содержит 25 целых точек, а длина его 24.

✓ Так

Длина это разность концов: max - min.

ГРОБ

ГРОБ №15: Границы отрезков и «между» целыми

Отрезки P = [10; 40] и Q = [25; 60]. Если перебирать только целые x, можно пропустить значение между ними, на котором формула ломается.

Как обойти

Перебирай x с шагом 0,5: [i / 2 for i in range(20, 130)]. Целые числа в этот список входят, и «щель» между ними тоже.

Лайфхаки на экзамене

all(...) останавливается на первом же x, где условие нарушено. Поэтому плохие A отсеиваются мгновенно.
Верхнюю границу для x выбирай чуть выше наибольшей степени двойки, влезающей в числа условия.
Для условий вроде «x делится на 3 или на 5» проверяй свойство прямо в if, без отдельных функций: x % 3 == 0 or x % 5 == 0.

Банк реальных задач №15 Открыть в тренажере СмартКИМ