Ах, ЕГЭ по информатике — тот самый экзамен, который заставляет даже самых стойких айтишников задуматься: «А не пойти ли мне лучше на йогу?» Вот и задача №15 из сборника Крылова, где всё не так просто, как кажется. Сергей Крылов — человек с таким именем, что уже вызывает уважение.
Если он руководит комиссией по разработке КИМ (контрольно-измерительных материалов), значит, задача будет не просто о том, как включить компьютер, а о том, как заставить его думать.
На первый взгляд — обычная задачка про отрезки. Но тут же подкрадываются делители числа 177 (кстати, загадочное число: оно то делится на 3 и 59 — словно тайный код для тех, кто любит математику). Множества лезут в кадр один за другим, будто гости на вечеринке у программиста.
И конечно же логическое выражение — ведь без него никуда. Это вам не шутки!
Я решил не мучить себя аналитикой и погрузился в мир перебора значений компьютером. Потому что иногда проще довериться машине — она хоть ошибок не делает (ну почти).
Объявляем функцию f(x,c,a,b), которая проверяет: если x входит в множество c, то он должен быть в отрезке a и при этом не попадать во множество b. Сложно?
Представьте себе бармена в ночном клубе: если гость (x) есть в списке приглашённых (c), то он должен быть одет по дресс-коду (a) и при этом не числиться в черном списке (b). Если все условия выполнены — добро пожаловать!
Если нет — проходите мимо.
Далее создаём два множества: отрезок a от 3 до 60 и множество b из делителей числа 177. Тут самое интересное: делителей всего два — 3 и 59. Как будто эти числа решили устроить клуб для избранных.
Начинается эпичный перебор y от 5555 до 2 с шагом -1.
Почему именно так? Чтобы найти первое подходящее число сверху вниз — ведь мы все любим быстрые результаты! Для каждого y строится множество c из его делителей (кроме самого y и единицы) — словно собирается команда супергероев.
Если множество c непусто и для всех x от 1 до 5554 функция f возвращает истину, значит мы нашли нашего героя!
Выводим y и прекращаем поиск.
Чтобы вы почувствовали всю магию кода:
«`python
def f(x, c, a, b):
return (x in c) <= ((x in a) and (not(x in b)))
a = [x for x in range(3, 61)]
b = [x for x in range(2, 177) if 177 % x == 0]
for y in range(5555, 1, -1):
c = [x for x in range(2, y) if y % x == 0]
if c and all(f(x, c, a, b) == True for x in range(1, 5555)):
print(y)
break
«`
Смешно представить программиста на экзамене с таким кодом на экране: «Ну что ж ты там делаешь?», спрашивает преподаватель. А он такой невозмутимый: «Проверяю всех гостей на вечеринке».
К слову сказать: ответ этой загадочной задачи равен… барабанная дробь… 2809! Да-да! Именно это число прошло строгий фильтр условий и оказалось победителем.
А теперь анекдот по теме: приходит студент к преподавателю информатики и говорит:
— Профессор, я решил задачу №15 из сборника Крылова!
— Молодец! А какой у тебя ответ?
— Не знаю… я просто заставил компьютер перебирать все варианты.
— Отлично!
Значит ты понял главное правило программирования – если сложно подумать самому — пусть думает машина!
Вот так и живём: иногда лучше довериться железу. Ну а если статья помогла вам чуть-чуть разобраться с этой задачкой или хотя бы улыбнуться над моими метафорами про вечеринки множества и строгих барменов – ставьте лайк!
Ведь позитивный настрой важнее любых сложных формул.