По каналу связи передаётся последовательность положительных целых чисел. Все числа не превышают 1000, их количество известно, но может быть очень велико. Затем передаётся контрольное значение — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
2) R не делится на 15.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Получено чисел: …
Принятое контрольное значение: …
Вычисленное контрольное значение: …
Контроль пройден (или Контроль не пройден)
Если удовлетворяющее условию контрольное значение определить невозможно, вычисленное контрольное значение не выводится, но выводится фраза «Контроль не пройден».
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке указывается количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
5
60
100
8
9
90
800
Выходные данные
Программа должна напечатать отчёт по образцу, приведённому в условии.
Пример выходных данных для приведённого выше примера входных данных:
Получено чисел: 5
Принятое контрольное значение: 800
Вычисленное контрольное значение: 800
Контроль пройден
Решение.Произведение двух чисел делится на 15, если один из сомножителей делится на 15 (второй может быть любым), либо если ни один из сомножителей не делится на 15, но один из сомножителей делится на 3, а другой — на 5.
Чтобы получить произведение, не делящееся на 15, нужно взять два сомножителя так, чтобы эти условия не выполнялись. Чтобы добиться этого, можно разбить все элементы входной последовательности на 4 непересекающихся класса чисел:
- кратные 15 (класс 15);
- кратные 3, но не кратные 5 (класс 3);
- кратные 5, но не кратные 3 (класс 5);
- не кратные ни 3, ни 5 (класс 0).
Числа, кратные 15, можно сразу отбросить: они не могут участвовать в итоговом произведении. Произведение двух чисел не будет делиться на 15, если оба числа принадлежат одному классу, либо если числа принадлежат
разным классам, но не классам 3 и 5. При этом для получения максимального значения следует брать максимально возможное число из каждого класса. Пусть a3 — максимальное число в классе 3, b3 — второе по величине число в классе 3, аналогичным образом обозначим два наибольших числа в классах 5 и 0. Тогда контрольным значением будет наибольшее из следующих произведений: a3*b3, a5*b5, a0*b0, a0*a3, a0*a5.
Программа читает все входные данные один раз, не запоминая все данные в массиве, для каждого входного числа определяет его класс, отбрасывает числа класса 15 и хранит два наибольших числа для каждого из остальных классов. После ввода всей последовательности программа вычисляет 5 перечисленных выше произведений, выбирает из них наибольшее и сравнивает его с введённым контрольным значением.
Пример правильной и эффективной программы на языке Паскаль
program c4;
var
N: integer; {количество чисел на входе}
x: integer; {исходные данные}
a3, b3: integer; {макс. числа, кратные 3, но не кратные 5}
a5, b5: integer; {макс. числа, кратные 5, но не кратные 3}
a0, b0: integer; {максимальные числа, не кратные 5 и 3}
R: integer; {введенное контрольное значение}
m: integer; {вычисленное контрольное значение}
i: integer;
begin
readln(N);
a3:=0; b3:=0;
a5:=0; b5:=0;
a0:=0; b0:=0;
for i:=1 to N do begin
readln(x);
if x mod 15 = 0 then {ничего не делать}
else if x mod 3 = 0 then begin
if x>a3 then begin b3:=a3; a3:=x end
else if x>b3 then b3:=x
end
else if x mod 5 = 0 then begin
if x>a5 then begin b5:=a5; a5:=x end
else if x>b5 then b5:=x
end
else begin
if x>a0 then begin b0:=a0; a0:=x end
else if x>b0 then b0:=x
end
end;
readln(R);
m := a0*a3;
if a0*a5>m then m:=a0*a5;
if a0*b0>m then m:=a0*b0;
if a3*b3>m then m:=a3*b3;
if a5*b5>m then m:=a5*b5;
writeln('Получено чисел: ', N);
writeln('Принятое контрольное значение: ', R);
if m>0 then writeln('Вычисленное контрольное значение: ', m);
if (R>0) and (R=m)
then writeln('Контроль пройден')
else writeln('Контроль не пройден')
end.
Пример правильной и эффективной программы на языке Си
#include <stdio.h>
void main ()
{
int N; /*количество чисел на входе*/
int x; /*исходные данные*/
int a3=0, b3=0; /*макс. числа, кратные 3, но не кратные 5*/
int a5=0, b5=0; /*макс. числа, кратные 5, но не кратные 3*/
int a0=0, b0=0; /*максимальные числа, не кратные 5 и 3*/
int R; /*введенное контрольное значение*/
int m; /*вычисленное контрольное значение*/
int i;
cin >> N;
for (i=1; i<=N; ++i) {
cin >> x;
if (x % 15 == 0) continue; /*ничего не делать*/
if (x % 3 == 0) {
if (x>a3) {b3=a3; a3=x;}
else if (x>b3) b3=x;
}
else if (x % 5 == 0) {
if (x>a5) {b5=a5; a5=x;}
else if (x>b5) b5=x;
}
else {
if (x>a0) {b0=a0; a0=x;}
else if (x>b0) b0=x;
}
}
cin >> R;
m = a0*a3;
if (a0*a5>m) m=a0*a5;
if (a0*b0>m) m=a0*b0;
if (a3*b3>m) m=a3*b3;
if (a5*b5>m) m=a5*b5;
printf("Получено чисел: %d\n", N);
printf("Принятое контрольное значение: %d\n", R);
if (m>0) printf("Вычисленное контрольное значение: %d\n", m);
if (R>0 && R==m) cout << "Контроль пройден\n";
else cout << "Контроль не пройден\n";
}
Пример правильной и эффективной программы на языке Бейсик
DIM N AS INTEGER 'количество чисел на входе
DIM x AS INTEGER 'исходные данные
DIM a3, b3 AS INTEGER 'макс. числа, кратные 3, но не кратные 5
DIM a5, b5 AS INTEGER 'макс. числа, кратные 5, но не кратные 3
DIM a0, b0 AS INTEGER 'максимальные числа, не кратные 5 и 3
DIM R AS INTEGER 'введенное контрольное значение
DIM m AS INTEGER 'вычисленное контрольное значение
DIM i AS INTEGER
INPUT N
FOR i = 1 TO N
INPUT x
IF x MOD 15 = 0 THEN 'ничего не делать
ELSEIF x MOD 3 = 0 THEN
IF x > a3 THEN
b3 = a3: a3 = x
ELSEIF x > b3 THEN b3 = x
END IF
ELSEIF x MOD 5 = 0 THEN
IF x > a5 THEN
b5 = a5: a5 = x
ELSEIF x > b5 THEN b5 = x
END IF
ELSE
IF x > a0 THEN
b0 = a0: a0 = x
ELSEIF x > b0 THEN b0 = x
END IF
END IF
NEXT i
INPUT R
m = a0 * a3
IF a0 * a5 > m THEN m = a0 * a5
IF a0 * b0 > m THEN m = a0 * b0
IF a3 * b3 > m THEN m = a3 * b3
IF a5 * b5 > m THEN m = a5 * b5
PRINT "Получено чисел: "; N
PRINT "Принятое контрольное значение: "; R
IF m > 0 THEN PRINT "Вычисленное контрольное значение: "; m
IF (R > 0) AND (R = m) THEN
PRINT "Контроль пройден"
ELSE
PRINT "Контроль не пройден"
END IF
Пример правильной и эффективной программы на Алгоритмическом языке
алг
нач
цел N | количество чисел на входе
цел x | исходные данные
цел a3=0, b3=0 | макс. числа, кратные 3, но не кратные 5
цел a5=0, b5=0 | макс. числа, кратные 5, но не кратные 3
цел a0=0, b0=0 | максимальные числа, не кратные 5 и 3
цел R | введенное контрольное значение
цел m | вычисленное контрольное значение
ввод N
нц N раз
ввод x
выбор
при mod(x, 15) = 0: | ничего не делать
при mod(x, 3) = 0:
выбор
при x>a3: b3:=a3; a3:=x
при x>b3: b3:=x
все
при mod(x, 5) = 0:
выбор
при x>a5: b5:=a5; a5:=x
при x>b5: b5:=x
все
иначе
выбор
при x>a0: b0:=a0; a0:=x
при x>b0: b0:=x
все
все
кц
ввод R
m := a0*a3
если a0*a5>m то m:=a0*a5 все
если a0*b0>m то m:=a0*b0 все
если a3*b3>m то m:=a3*b3 все
если a5*b5>m то m:=a5*b5 все
вывод "Получено чисел: ", N
вывод нс, "Принятое контрольное значение: ", R
если m>0
то вывод нс, "Вычисленное контрольное значение: ", m
все
если R>0 и R=m
то вывод нс, "Контроль пройден"
иначе вывод нс, "Контроль не пройден"
все
кон
Приведём решение Ильи Муратова, Python.
n = int(input())
max31 = max32 = max51 = max52 = max01 = max02 = 0
for i in range(n):
k = int(input())
if k % 15 != 0:
if k % 3 == 0:
if max31 < k:
max32 = max31
max31 = k
elif max32 < k:
max32 = k
elif k % 5 == 0:
if max51 < k:
max52 = max51
max51 = k
elif max52 < k:
max52 = k
else:
if max01 < k:
max02 = max01
max01 = k
elif max02 < k:
max02 = k
R = int(input())
t = max([max31 * max32, max51 * max52, max01 * max02, max31 * max01, max51 * max01])
print "Получено чисел: ", n
print "Принятое контрольное значение: ", R
print "Вычисленное контрольное значение: ", t
if R == t:
print "Контроль пройден"
else:
print "Контроль не пройден"
