Question

По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наибольшее число *R*, удовлетворяющее следующимусловиям: 1) *R* — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине); 2) *R* делится на 21. Если такого числа *R* нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: *Вычисленное контрольное значение: … Контроль пройден

* (**или** — *Контроль не пройден*) Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение. *Пример входных данных: *6 70 21 997 7 9 300 21000 *Пример выходных данных для приведённого выше примера входных данных: *Вычисленное контрольное значение: 21000 Контроль пройден

Accepted Answer

Answer

### СТАТЕМЕНТ По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наибольшее число $R$, удовлетворяющее следующим условиям: 1. $R$ — произведение двух различных переданных элементов последовательности (различные означает, что не рассматриваются квадраты; допускаются произведения различных элементов, равных по величине); 2. $R$ делится на 21. Если такого числа $R$ нет, контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную программу, которая проверяет правильность контрольного значения. **Входные данные:** - Первая строка: количество чисел $N$. - Следующие $N$ строк: по одному натуральному числу, не превышающему 1000. - Последняя строка: контрольное значение. **Выходные данные:** ``` Вычисленное контрольное значение: <значение> Контроль пройден ``` или ``` Вычисленное контрольное значение: <значение> Контроль не пройден ``` **Пример входных данных:** ``` 6 70 21 997 7 9 300 21000 ``` **Пример выходных данных:** ``` Вычисленное контрольное значение: 21000 Контроль пройден ``` --- ### РЕШЕНИЕ Идея решения: произведение двух чисел делится на 21 тогда и только тогда, когда либо один из них делится на 21, либо один делится на 7 (но не на 3), а другой — на 3 (но не на 7). Поэтому достаточно отслеживать четыре величины при однократном проходе по входным данным: максимальное число, кратное 7, но не 3; максимальное число, кратное 3, но не 7; максимальное число, кратное 21; максимальное число среди всех остальных (или второе по величине число, кратное 21, если максимум — число, кратное 21). **Алгоритм:** 1. Инициализируем четыре переменные: `M7` (макс. кратное 7, не кратное 3), `M3` (макс. кратное 3, не кратное 7), `M21` (макс. кратное 21), `MAX` (макс. число, отличное от `M21`, или второе по величине число, кратное 21). 2. Проходим по всем $N$ числам: - Если число кратно 21 и больше `M21`, обновляем `MAX := M21` (если `M21 > 0`), затем `M21 := число`. - Иначе, если число кратно 7 (но не 3) и больше `M7`, обновляем `M7 := число`. - Иначе, если число кратно 3 (но не 7) и больше `M3`, обновляем `M3 := число`. - Иначе, если число больше `MAX`, обновляем `MAX := число`. 3. Вычисляем контрольное значение как максимум из `M21 * MAX` и `M7 * M3` (если оба произведения определены). 4. Сравниваем вычисленное значение с переданным и выводим результат. **Реализация на Python:** ```python n = int(input()) numbers = [] for _ in range(n): numbers.append(int(input())) r = int(input()) M7 = 0 M3 = 0 M21 = 0 MAX = 0 for dat in numbers: if dat % 21 == 0 and dat > M21: if M21 > MAX: MAX = M21 M21 = dat elif dat % 7 == 0 and dat % 3 != 0 and dat > M7: M7 = dat elif dat % 3 == 0 and dat % 7 != 0 and dat > M3: M3 = dat else: if dat > MAX: MAX = dat if M7 * M3 < M21 * MAX: res = M21 * MAX else: res = M7 * M3 print(f"Вычисленное контрольное значение: {res}") if r == res: print("Контроль пройден") else: print("Контроль не пройден") ``` **Реализация на Паскале:** ```pascal var M7, M3, M21, R, MAX, dat, res, i, N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do begin readln(dat); if (dat mod 7 = 0) and ((dat mod 3) > 0) and (dat > M7) then M7 := dat else if (dat mod 3 = 0) and ((dat mod 7) > 0) and (dat > M3) then M3 := dat else if (dat mod 21 = 0) and (dat > M21) then begin if M21 > MAX then MAX := M21; M21 := dat end else if dat > MAX then MAX := dat; end; readln(R); if (M7 * M3 < M21 * MAX) then res := M21 * MAX else res := M7 * M3; writeln('Вычисленное контрольное значение: ', res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. ``` **Сложность:** $O(n)$ — один проход по входным данным, константное количество операций на каждом элементе. Память: $O(1)$ — хранятся только четыре переменные, независимо от размера входа. --- ### ОТВЕТ ![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=10590) ![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=10591)

Задание №27ПрограммированиеЕГЭ по информатике