СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 13373

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента (это время известно заранее) прибор каждую минуту передаёт в обсерваторию по каналу связи положительное целое число, не превышающее 1000, — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах.

После окончания эксперимента передаётся контрольное значение — наибольшее число R, удовлетворяющее следующим условиям:

1) R — произведение двух чисел, переданных в разные минуты;

2) R делится на 26.

Предполагается, что удовлетворяющее условиям контрольное значение существовало в момент передачи.

В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

Напишите эффективную по времени и используемой памяти программу (укажите используемую версию языка программирования, например Free Pascal 2.6.4), которая будет проверять правильность контрольного значения. Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Программа должна напечатать отчёт по следующей форме.

 

Вычисленное контрольное значение: …

Контроль пройден (или Контроль не пройден)

 

Если удовлетворяющее условию контрольное значение определить невозможно, то выводится только фраза «Контроль не пройден». Перед текстом программы кратко опишите используемый Вами алгоритм решения.

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

 

Пример входных данных:

5

52

12

39

55

23

2860

 

Пример выходных данных для приведённого выше примера входных данных:

Вычисленное контрольное значение: 2860

Контроль пройден

Решение.

Можно заметить, что 26 = 13*2. Поэтому ответом является наибольшее из двух произведений:

a) максимальное нечетное число, кратное 13, умноженное на максимальное четное число из оставшихся;

b) максимальное число, кратное 26, умноженное на максимальное число из оставшихся.

Чтобы не взять в произведении одно и тоже число, можно хранить номер их поступления.

Если вдруг найдем повторяющиеся значения по этому номеру (например, на тесте из 3 элементов 52, 5 и 7 значение максимума и максимального числа кратного 26 совпадает), то найдем предмаксимумы для обоих случаев и возьмем более выгодный из них.

 

Далее пример оптимальной программы на языке PascalABC.

 

 

var

n, i, a, r, max2, max13, max26, max, predmax: integer;

index2, index13, index26, indexmax, ans, ans1, ans2: integer;

 

begin

readln(n);

max:=0;

max26:=0;

max13:=0;

max2:=0;

ans:=0;

ans1:=0;

ans2:=0;

r:=0;

for i := 1 to n do

begin

readln(a);

if (a mod 13 = 0) and (a > max13) then begin

max13 := a;

index13 := i;

end;

if (a mod 2 = 0) and (a > max2) then begin

max2 := a;

index2 := i;

end;

if (a mod 26 = 0) and (a > max26) then begin

max26 := a;

index26 := i;

end;

if (a >= max) then begin

predmax:=max;

max := a;

indexmax := i;

end;

if(a < max) and (a >= predmax) then

predmax := a;

end;

readln(r);

if(index2 <> index13) then

ans1 := max2 * max13;

if(index26 <> indexmax) then

ans2 := max * max26

else

ans2 := predmax * max26;

if(ans1 > ans2) then

ans := ans1

else

ans := ans2;

writeln('Вычисленное контрольное значение:', ans);

if (ans=r) then

writeln('Контроль пройден')

else

writeln('Контроль не пройден');

end.

Пример правильной, но неэффективной программы на языке Паскаль.

 

var

N: integer; {количество чисел}

a: array [1..1000] of integer; {исходные данные}

max: integer; {вычисленное контролькое значение}

R: integer; {передаваемое контрольное значение}

i, j: integer;

begin

readln(N);

for i := 1 to N do read(a[i]);

max := 0;

for i := 1 to N-1 do

for j := i + 1 to N do

if (a[i]*a[j] mod 26 = 0) and (a[i]*a[j]>max) then

max := a[i]*a[j];

readln(R);

if max = R then begin

writeln('Вычисленное контрольное значение: ', R);

writeln('Контроль пройден')

end

else writeln('Контроль не пройден');

end.

Источник: ЕГЭ — 2017. До­сроч­ная волна по информатике