Задание 27 ЕГЭ по информатике · 391438

1. Для произведения двух чисел быть кратным 26 необходимо и достаточно, чтобы оно было кратно 2 и 13. Для каждого уже обработанного числа достаточно знать, делится ли оно на 2 и на 13.

2. Храним четыре максимальных значения: число, делящееся и на 2, и на 13; число, делящееся на 2, но не на 13; число, делящееся на 13, но не на 2; число, не делящееся ни на 2, ни на 13.

3. Для текущего числа проверяем произведение с максимальными числами из групп, которые вместе обеспечивают делимость произведения на 2 и на 13. Если произведение больше текущего максимума, заменяем максимум.

4. После обработки всех показаний считываем переданное контрольное значение. Если подходящая пара найдена, выводим вычисленное максимальное произведение и сравниваем его с переданным значением. Иначе выводим только «Контроль не пройден».

5. Каждое число обрабатывается за постоянное число операций, поэтому время работы равно O(N). Хранятся только четыре максимума и несколько переменных, поэтому используемая память равна O(1) и не зависит от N.

6. Пример реализации на Python 3:

7. ```python n = int(input())
# Максимумы по группам:
# 0: делится на 2 и на 13
# 1: делится на 2, но не на 13
# 2: не делится на 2, но делится на 13
# 3: не делится ни на 2, ни на 13 best = [0, 0, 0, 0] maximum_product = 0 for _ in range(n):
x = int(input()) divisible_by_2 = (x % 2 == 0) divisible_by_13 = (x % 13 == 0)
# Проверяем произведения с уже встречавшимися числами.
for y in best:
if y != 0 and (x * y) % 26 == 0:
maximum_product = max(maximum_product, x * y) if divisible_by_2 and divisible_by_13:
group = 0 elif divisible_by_2:
group = 1 elif divisible_by_13:
group = 2 else:
group = 3 if x > best[group]:
best[group] = x control = int(input()) if maximum_product == 0:
print("Контроль не пройден") else:
print("Вычисленное контрольное значение:", maximum_product) if maximum_product == control:
print("Контроль пройден") else:
print("Контроль не пройден")
```