Решение: Проверка контрольного значения
На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента прибор каждую минуту передаёт в обсерваторию положительное целое число, не превышающее 1000, — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах.
После окончания эксперимента передаётся контрольное значение — наибольшее число $R$, удовлетворяющее следующим условиям: $R$ — произведение двух чисел, переданных в разные минуты; $R$ делится на 26.
Предполагается, что удовлетворяющее условиям контрольное значение существовало в момент передачи. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную по времени и используемой памяти программу, которая будет проверять правильность контрольного значения. Программа эффективна по времени, если время её работы пропорционально количеству полученных показаний прибора $N$. Программа эффективна по памяти, если размер памяти, использованной для хранения данных, не зависит от $N$ и не превышает 1 килобайта.
Если вычисленное контрольное значение существует, программа должна вывести его и сообщить, пройден ли контроль. Если определить удовлетворяющее условию контрольное значение невозможно, выводится только фраза «Контроль не пройден».
На вход программе в первой строке подаётся количество чисел $N \le 100\,000$. В каждой из последующих $N$ строк записано одно положительное целое число, не превышающее 1000. В последней строке записано переданное контрольное значение.
Решение по шагам
7 шаговДля произведения двух чисел быть кратным 26 необходимо и достаточно, чтобы оно было кратно 2 и 13. Для каждого уже обработанного числа достаточно знать, делится ли оно на 2 и на 13.
Храним четыре максимальных значения: число, делящееся и на 2, и на 13; число, делящееся на 2, но не на 13; число, делящееся на 13, но не на 2; число, не делящееся ни на 2, ни на 13.
Для текущего числа проверяем произведение с максимальными числами из групп, которые вместе обеспечивают делимость произведения на 2 и на 13. Если произведение больше текущего максимума, заменяем максимум.
После обработки всех показаний считываем переданное контрольное значение. Если подходящая пара найдена, выводим вычисленное максимальное произведение и сравниваем его с переданным значением. Иначе выводим только «Контроль не пройден».
Каждое число обрабатывается за постоянное число операций, поэтому время работы равно $O(N)$. Хранятся только четыре максимума и несколько переменных, поэтому используемая память равна $O(1)$ и не зависит от $N$.
Пример реализации на Python 3:
```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("Контроль не пройден")
```
Алгоритм использует четыре максимальных значения, классифицированных по делимости на 2 и 13; сложность — $O(N)$ по времени и $O(1)$ по памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Хранение всех входных чисел, нарушающее требование по памяти.
Проверка всех пар чисел, имеющая квадратичную сложность $O(N^2)$.
Использование только условия делимости на 26 для отдельных чисел вместо проверки делимости произведения.
Обновление максимума до проверки пары с текущим числом: это может привести к использованию одного и того же числа дважды.
Вывод вычисленного значения, когда подходящей пары не существует.