Проверка контрольного значения
На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента прибор каждую минуту передаёт в обсерваторию положительное целое число, не превышающее 1000, — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах.
После окончания эксперимента передаётся контрольное значение — наибольшее число $R$, удовлетворяющее следующим условиям: $R$ — произведение двух чисел, переданных в разные минуты; $R$ делится на 26.
Предполагается, что удовлетворяющее условиям контрольное значение существовало в момент передачи. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную по времени и используемой памяти программу, которая будет проверять правильность контрольного значения. Программа эффективна по времени, если время её работы пропорционально количеству полученных показаний прибора $N$. Программа эффективна по памяти, если размер памяти, использованной для хранения данных, не зависит от $N$ и не превышает 1 килобайта.
Если вычисленное контрольное значение существует, программа должна вывести его и сообщить, пройден ли контроль. Если определить удовлетворяющее условию контрольное значение невозможно, выводится только фраза «Контроль не пройден».
На вход программе в первой строке подаётся количество чисел $N \le 100\,000$. В каждой из последующих $N$ строк записано одно положительное целое число, не превышающее 1000. В последней строке записано переданное контрольное значение.
Условие как в банке ФИПИ — открыть и сверить
| На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента (это время известно заранее) прибор каждую минуту передаёт в обсерваторию по каналу связи положительное целое число, не превышающее 1000, количество энергии солнечного излучения, полученной за последнюю минуту, измеренное После окончания эксперимента передаётся контрольное значение наибольшее число R, удовлетворяющее следующим условиям: 1) R произведение двух чисел, переданных в разные минуты; 2) R делится на 26. Предполагается, что удовлетворяющее условиям контрольное значение существовало в момент передачи. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную по времени и используемой памяти программу (укажите используемую версию языка программирования, например Free Pascal 2.6.4), которая будет проверять правильность контрольного значения. Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Программа должна напечатать отчёт по следующей форме.
Вычисленное контрольное значение: … Контроль пройден (или Контроль не пройден)
Если удовлетворяющее условию контрольное значение определить невозможно, то выводится только фраза «Контроль не пройден». Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N ≤ 100 000. В каждой из последующих N строк записано одно положительное целое число, не превышающее 1000. В последней строке записано контрольное значение. Пример входных данных: 5 52 12 39 55 23 2860
Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: 2860 Контроль пройден
| ||
| |
Это задание с развёрнутым решением: ответом считается запись хода решения, а не строка. Напишите решение на бумаге и сравните с разбором — там каждый шаг с обоснованием.
Открыть разбор1Мягкая — с чего смотретьуровень 1 из 3
Какие свойства чисел нужно хранить, чтобы после обработки очередного значения быстро находить максимальное произведение с ним?
2Наводящая — какие числа считатьуровень 2 из 3
Так как $26 = 2 \cdot 13$, произведение делится на 26, если в паре есть множитель, содержащий множитель 2, и множитель, содержащий множитель 13. Достаточно хранить максимальные уже встреченные числа с нужными свойствами.
3Прямая — фактически решениеуровень 3 из 3
Разделите числа на четыре группы по признакам делимости на 2 и на 13. При чтении очередного числа вычисляйте произведения с максимальными представителями подходящих групп, затем обновляйте максимумы. Это даёт время $O(N)$ и память $O(1)$.