По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям:
1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 22.
Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: …
Контроль пройден (или – Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
6
55
997
22
7
9
400
22000
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 22000
Контроль пройден
Объяснение
Нам необходимо найти максимальное произведение двух различных элементов последовательности такое, чтобы оно было кратно 22. Произведение будет кратно 22, если как минимум один из сомножителей делится на 22 или один из сомножителей делится на 2, а другой на 11. Нам надо найти максимальное произведение, значит сомножители также должны быть максимальны. В программе будем хранить 4 переменные: для максимального числа кратного 22 (a22), для максимального числа в последовательности, отличного от a22 (m), для максимального числа кратного 11 (a11) и для максимального числа кратного 2 (a2). Когда все данные прочитаны просто сравниваем произведения a22 и m, a11 и a2 и присваиваем наибольшее из этих значений переменной otv. Далее эту переменную сравниваем с контрольным значением и выводим результаты.
Решение на языке Паскаль
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
var N: biginteger; //Количество элементов a: word; //Очередное значение a22: word; //Наибольшее число кратное 22 a2: word; //Наибольшее число кратное 2 a11: word; //Наибольшее число кратное 11 m: word; //Максимальное число в последовательности R: longword; //Переменная для проверки otv: longword; //Ответ i: biginteger; //Счетчик begin a22 := 0; a2 := 0; a11 := 0; m := 0; readln(N); i := 0; while i < N do begin readln(a); if a mod 22 = 0 then begin if a > a22 then begin if a22 > m then m := a22; a22 := a; end; end else begin if a > m then m := a; if (a > a11) and (a mod 11 = 0) then a11 := a; if (a > a2) and (a mod 2 = 0) then a2 := a; end; i := i + 1; end; if (a11 * a2) > (a22 * m) then otv := a11 * a2 else otv := a22 * m; readln(R); writeln('Вычисленное контрольное значение: ', otv); if R = otv then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. |
Решение на языке Python
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
a22 = 0 #Переменная для хранения максимального числа кратного 22 a2 = 0 #Переменная для хранения максимального числа кратного 2 a11 = 0 #Переменная для хранения максимального числа кратного 11 m = 0 #Самое большое число из всей последоваельности otv = 0 #Ответ N = int(input()) for i in range(N): a = int(input()) #Считываем очередное значение if a % 22 == 0: if a > a22: if a22 > m: m = a22 a22 = a else: if a > m: m = a if a % 11 == 0 and a > a11: a11 = a if a % 2 == 0 and a > a2: a2 = a if a22 * m > a11 * a2: otv = a22 * m else: otv = a11 * a2 print('Вычисленное контрольное значение: ' + str(otv)) if int(input()) == otv: print('Контроль пройден') else: print('Контроль не пройден') |