Question

По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наименьшее число R, удовлетворяющее следующим условиям:1) R является произведением двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);2) R кратно 6.

Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения.Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение: …Контроль пройден (или — Контроль не пройден)

Перед текстом программы кратко опишите используемый Вами алгоритм решения.На вход программе в первой строке подаётся количество чисел N;в программе можно считать, что 2 ≤ N ≤ 10 000. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение — натуральное число, не превышающее 1 000 000.

*Пример входных данных*:630653430012*Пример выходных данных для приведённого выше примера входных данных*:Вычисленное контрольное значение: 12Контроль пройден

Accepted Answer

Answer

### СТАТЕМЕНТ По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наименьшее число R, удовлетворяющее следующим условиям: 1) R является произведением двух различных переданных элементов последовательности (под «различными» понимаются разные позиции в последовательности; произведения элементов с одинаковыми значениями допускаются); 2) R кратно 6. Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную программу, которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: ``` Вычисленное контрольное значение: … Контроль пройден (или — Контроль не пройден) ``` **Входные данные:** - Первая строка: количество чисел N (2 ≤ N ≤ 10 000). - Следующие N строк: по одному натуральному числу, не превышающему 1000. - Последняя строка: контрольное значение (натуральное число, не превышающее 1 000 000). **Пример входных данных:** ``` 6 30 6 5 3 4 30 0 12 ``` **Пример выходных данных:** ``` Вычисленное контрольное значение: 12 Контроль пройден ``` --- ### РЕШЕНИЕ Идея решения: произведение двух чисел делится на 6 тогда и только тогда, когда либо одно из них кратно 6, либо одно кратно 2 (но не 3), а другое кратно 3 (но не 2). Поэтому достаточно отслеживать четыре минимальных значения: наименьшее чётное число, не кратное 3; наименьшее число, кратное 3, но не чётное; наименьшее число, кратное 6; и наименьшее число в целом (отличное от минимума, кратного 6, если тот встречается один раз). Алгоритм: 1. Читаем последовательность один раз, не сохраняя все элементы в памяти. 2. Для каждого числа обновляем четыре переменные: - M2 — минимум среди чисел, делящихся на 2, но не на 3; - M3 — минимум среди чисел, делящихся на 3, но не на 2; - M6 — минимум среди чисел, делящихся на 6; - MIN — минимум всех чисел, кроме M6 (если M6 встречается один раз). 3. Вычисляем контрольное значение как минимум из произведений M6 × MIN и M2 × M3. 4. Если ни одна из пар не существует, результат равен 0. 5. Сравниваем вычисленное значение с переданным. ```pascal Program C4; var M2, M3, M6, MIN, dat: integer; R, res, i, N: longint; begin M2 := 1001; M3 := 1001; M6 := 1001; MIN := 1001; readln(N); for i := 1 to N do begin readln(dat); if (dat mod 2 = 0) and (dat mod 3 > 0) and (dat < M2) then M2 := dat; if (dat mod 3 = 0) and (dat mod 2 > 0) and (dat < M3) then M3 := dat; if (dat mod 6 = 0) and (dat < M6) then begin if M6 < MIN then MIN := M6; M6 := dat; end else if dat < MIN then MIN := dat; end; if (M2 * M3 > M6 * MIN) then res := M6 * MIN else res := M2 * M3; if (M6 >= 1001) and ((M2 >= 1001) or (M3 >= 1001)) then res := 0; writeln('Вычисленное контрольное значение: ', res); readln(R); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. ``` **Сложность:** $O(N)$ по времени, $O(1)$ по памяти (используются только четыре переменные для отслеживания минимумов). --- ### ОТВЕТ

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