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


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

Последовательность натуральных чисел характеризуется числом Y – наибольшим числом, кратным 26 и являющимся произведением двух элементов последовательности с различными номерами.

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

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

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

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

5

40

100

130

28

51

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

Решение.

Произведение двух чисел делится на 26, если:

— один из сомножителей делится на 26 (второй может быть любым) либо

— ни один из сомножителей не делится на 26, но один из сомножителей делится на 13, а другой – на 2.

Поэтому программа, вычисляющая число Y, может работать так.

Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:

М13 — самое большое число, кратное 13, но не кратное 2;

M2 — самое большое число, кратное 2, но не кратное 13;

M26 — самое большое число, кратное 26;

МAX — самое большое число среди всех элементов последовательности, отличное от М26 (если число М26 встретилось более одного раза и оно же является максимальным, то MAX = M26).

После того как все данные прочитаны, искомое число Y вычисляется как максимум из произведений М26*MAX и М13*М2.

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

Допускаются решения, записанные на других языках программирования.

 

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

var M13,M2,M26,MAX,dat,res,i,N: longint;

begin

  M13 := 0;

  M2 := 0;

  M26 := 0;

  MAX := 0;

  readln(N);

  for i := 1 to N do

  begin

    readln(dat);

    if ((dat mod 13) = 0) and ((dat mod 2) > 0) and (dat > M13) then

      M13 := dat;

    if ((dat mod 2) = 0) and ((dat mod 13) > 0) and (dat > M2) then

      M2 := dat;

    if (dat mod 26 = 0) and (dat > M26) then

    begin

      if M26 > MAX then MAX := M26;

      M26 := dat

    end

    else

    if dat > MAX then

      MAX := dat;

  end;

  if (M13*M2 < M26*MAX) then

    res := M26*MAX

  else

    res := M13*M2;

  writeln(res);

  end.

 

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

M26 = 0

M13 = 0

M2 = 0

MAX = 0

INPUT N

FOR I = 1 TO N

  INPUT DAT

  IF DAT MOD 13 = 0 AND DAT > M13 THEN

    M13 = DAT

    ELSE

      IF DAT MOD 2 = 0 AND DAT > M2 THEN

      M2 = DAT

      END IF

    END IF

  IF DAT MOD 26 = 0 AND DAT > M26 THEN

    IF M26 > MAX THEN

      MAX = M26

    END IF

  M26 = DAT

  ELSE

    IF DAT > MAX THEN

      MAX = DAT

    END IF

  END IF

NEXT I

IF M2 * M13 < M26 * MAX THEN

  RES = M26 * MAX

ELSE

  RES = M2 * M13

END IF

PRINT RES

END

 

Приводим эффективное решение Игоря Кудашева на Python 3.

n = int(input())

x1 = 0

x2 = 0

x13 = 0

x26 = 0

for i in range(n):

    x = int(input())

    if x % 26 == 0 and x > x26: x26 = x

    else:

        if x > x1: x1 = x

        if x % 2 == 0 and x > x2: x2 = x

        if x % 13 == 0 and x > x13: x13 = x

print(max(x26 * x1, x2 * x13))


Аналоги к заданию № 9708: 9662 Все