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


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

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

Входные данные.

Файл A

Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Пример организации исходных данных во входном файле:

5

40

1000

7

28

55

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

28000

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

 

Ответ:

Решение.

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

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

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

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

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

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

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

M14 – самое большое число, кратное 14;

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

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

Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.

 

Приведём решение задачи на языке Pascal.

var M7,M2,M14,MAX,dat,res,i,N: longint; var s: string;

begin

M7 := 0;

M2 := 0;

M14 := 0;

MAX := 0;

assign(input, '27-B_2.txt');

readln(N);

for i := 1 to N do

begin

readln(dat);

if ((dat mod 7) = 0) and ((dat mod 2) > 0) and (dat > M7) then

M7 := dat;

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

M2 := dat;

if (dat mod 14 = 0) and (dat > M14) then

begin

if M14 > MAX then MAX := M14;

M14 := dat

end

else

if dat > MAX then

MAX := dat;

end;

if (M7*M2 < M14*MAX) then

res := M14*MAX

else

res := M7*M2;

writeln(res);

end.

В результате работы данного алгоритма при вводе данных из файла A ответ — 447552, из файла B — 994000.

 

Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.