Статья Автор: Лебедев Дмитрий Алексеевич

Задание 15 и Бинарный поиск !?

На ЕГКР в апреле 2026 было задание

Для какого наибольшего целого неотрицательного числа А выражение

(3x+4y≠84 882)∨(x<y)∨(A<x)

истинно (т.е. принимает значение 1) при любых целых неотрицательных х и у?

Решение задания с помощью аналитики не представляет проблем.
А как решать программно, с минимальным применение аналитики?
Стандартная модель состоит в следующим
def f(x,y, A) : которая возвращает True/False выражения при заданных x, y, A
def g(A) : которая проверяет истинность выражения для данного A при всех x, y
Основной (поисковый) блок (возможны другие реализации)
A = 0
while True :
if g(A) == False : break
A += 1
print(A)

Самая большая сложность в параметрах для g(A) и её реализации (ведь нельзя проверить все x, y - значит находим разумные ограничения)
Стандартная
def g(A) :
N = 84_882
for x in range(N//3 + 1):
for y in range(N//4 +1):
if f(x,y,A) == False : return False
return True0
не пройдет по времени (от слова совсем, можно проверить время для одного значения A)

def f(x,y,A, N) :
  return (3*x + 4*y != N) or (x < y) or (A < x)
def g(A, N) :
  for x in range(N//3 + 1):
    for y in range(N//4 +1):
      if f(x,y,A,N) == False : return False
  return True
print(g(1580, 24_882))

В чем проблема?
Ограничения для x, y взяли независимыми и такими, что первое условие ( 3x + 4y != N было истинным)
Более правильно, но несколько сложнее перебирать значения x, y такими, что:

условия были ложными (хотя бы одно), значит
- перебираем x до N//3+1
- задаем y = (N - 3x)//4 (делемость на 4 проверять не нужно)
- вычисляем функцию

Меняем код и проверяем.

def f(x,y,A, N) :
  return (3*x + 4*y != N) or (x < y) or (A < x)
def g(A, N) :
  for x in range(N//3 + 1):
    y = (N - 3*x)//4
    if f(x,y,A,N) == False : return False
  return True
print(g(1580, 84_882))

Уже лучше. Пробуем весь код (на среднем значениии 24_882) - получаем ответ за 10 секунд, а на реальном за сотню секунд)
Такой подхот (создание условий для ложности заданных условий более правильный), но может потребовать больших затрат.
Что можно ещё исподьзовать? УСЛОВИЕ!!!

def f(x,y,A, N) :
  return (3*x + 4*y != N) or (x < y) or (A < x)
def g(A, N) :
  for x in range(N//3 + 1):
    y = (N - 3*x)//4
    if f(x,y,A,N) == False : return False
  return True
A, N = 0, 24_882
while True :
  if g(A, N)  == False : break
  A += 1
print(A)

По условию задания надо найти НАИБОЛЬШЕЕ значение A.
Значит есть Я такое, что

при А > Я функции g будет возвращать False
в остальных случаях True

Применим "ручной БП (бинарный поиск)"

запустим с шагом 10000
от найденного True с шагом 1000
затем с шагом 100
затем с шагом 1 (можно 10 и 1)

Ниже шаблон для пробы для более большого значения

def f(x,y,A, N) :
  return (3*x + 4*y != N) or (x < y) or (A < x)
def g(A, N) :
  for x in range(N//3 + 1):
    y = (N - 3*x)//4
    if f(x,y,A,N) == False : return False
  return True
N = 984_882
A,shag = 140_600, 1
while True :
  if g(A, N)  == False : break
  A += shag
print(A, g(A,N))

Тракектория решения для N = 984_882

A, shag = 0, 100_000 - ответ 200_000б False
A, shag = 100_000, 10_000 - ответ 150_000, False
A, shag = 140_000, 1_000 - ответ 141_000, False
A, shag = 140_000, 100 - ответ 140_700, False
A, shag = 140_600, 1 - ответ 140_700, False

Печать