По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 33.
Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: ...
Контроль пройден (или — Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
550
33
7
997
9
60
33000
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 33000
Контроль пройден
Произведение двух чисел делится на 33, если:
· один из сомножителей делится на 33 (второй может быть любым) либо
· ни один из сомножителей не делится на 33, причём один из сомножителей делится на 11, а другой — на 3.
Поэтому программа, вычисляющая кодовое число, может работать так. Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин: M11 — самое большое число, кратное 11, но не кратное 3; М3 — самое большое число, кратное 3, но не кратное 11; М33 — самое большое число, кратное 33; МАХ — самое большое число среди всех элементов последовательности, отличное от М33 (если число М33 встретилось более одного раза и оно же является максимальным, то МАХ = М33).
После того как все данные прочитаны, искомое контрольное значение вычисляется как максимум из произведений М33*МАХ и M11*М3. Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм. Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы. Допускаются решения, записанные на других языках программирования.
| Пример правильной и эффективной программы на языке Бейсик: | Пример правильной и эффективной программы на языке Паскаль: |
МЗЗ = 0 М11 = 0 МЗ = 0 МАХ = 0 INPUT N FOR I = 1 ТО N INPUT DAT IF DAT MOD 11 = 0 AND DAT > M11 THEN M11 = DAT ELSE IF DAT MOD 3=0 AND DAT > M3 THEN M3 = DAT END IF END IF IF DAT MOD 33 = 0 AND DAT > M33 THEN IF M3 3 > MAX THEN MAX = M33 END IF M33 = DAT ELSE IF DAT > MAX THEN MAX = DAT END IF END IF NEXT I INPUT R IF M3 * M11 < M33 * MAX THEN RES = M33 * MAX ELSE RES = M3 * M11 END IF PRINT "Вычисленное контрольное значение: "; RES IF RES = R THEN PRINT "Контроль пройден" ELSE PRINT "Контроль не пройден" END IF END | var M11,МЗ,МЗ3,R,MAX,dat,res,i,N: longint; begin M11 := 0; М3 := 0; М33 := 0; MAX := 0; readln(N) for i := 1 to N do begin readln(dat); if ((dat mod 11) = 0) and ((dat mod 3) > 0) and (dat > M11) then M11 : = dat; if ((dat mod 3) = 0) and ((dat mod 11) > 0) and (dat > М3) then M3 : = dat; if (dat mod 33 = 0) and (dat > M33) then begin if M33 > MAX then MAX := M33; M33 : = dat end else if dat > MAX then MAX : = dat; end; readln(R); if (M11*M3 < M33*MAX) then res := M33*MAX else res := M11*M3; writeln('Вычисленное контрольное значение: 1,res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. |
Приводим эффективное решение Игоря Кудашева на Python 3.
n = int(input())
x1 = 0
x3 = 0
x11 = 0
x33 = 0
for i in range(n):
x = int(input())
if x % 33 == 0 and x > x33: x33, x1 = x, x33
else:
if x > x1: x1 = x
if x % 3 == 0 and x > x3: x3 = x
if x % 11 == 0 and x > x11: x11 = x
r = int(input())
print('Вычисленное контрольное значение:', max(x1 * x33, x3 * x11))
if r == max(x1 * x33, x3 * x11): print('Контроль пройден')
else: print('Контроль не пройден')