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


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

Дан набор из N целых положительных чисел. Из этих чисел формируются все возможные пары (парой считаются два элемента, которые находятся на разных местах в наборе, порядок чисел в паре не учитывается), в каждой паре вычисляются сумма и произведение элементов. Необходимо определить количество пар, у которых сумма нечётна, а произведение делится на 5.

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает одного килобайта и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.

Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.

Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Описание входных и выходных данных.

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

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

4

1

2

4

5

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

2

Из четырёх чисел можно составить 6 пар. В данном случае условиям удовлетворяют две пары: (2, 5) и (4, 5). Суммы чисел в этих парах (7 и 9) нечётны, а произведения (10 и 20) делятся на 5. У всех остальных пар как минимум одно из этих условий не выполняется.

Решение.

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

Разобьём все числа исходного набора на 4 группы, в зависимости от их чётности и делимости на 5. Сами числа можно не хранить, достаточно при вводе определить остаток от деления очередного числа на 2 и на 5 и увеличить соответствующий счётчик. Таким образом, независимо от количества чисел в исходном наборе, после чтения исходных данных для хранения необходимой информации хватит четырёх счётчиков, и программа получится эффективной по памяти.

Пусть в результате подсчёта получилось, что в наборе данных

m1 нечётных чисел, не кратных 5;

m2 чётных чисел, не кратных 5;

m5 нечётных чисел, кратных 5;

m10 чётных чисел, кратных 5.

Тогда количество удовлетворяющих условию пар можно определить по формуле m1m10 + m2m5 + m5m10.

Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).

 

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

var

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

    a: integer; {очередное число}

    m1: integer; {нечётные, не кратные 5}

    m2: integer; {чётные, не кратные 5}

    m5: integer; {нечётные, кратные 5}

    m10: integer; {чётные, кратные 5}

    s: integer; {количество пар}

    i: integer;

begin

    m1 := 0; m2 := 0; m5 := 0; m10 := 0;

    readln(N);

    for i:=1 to N do begin

        readln(a);

        if a mod 2 = 0 then begin

            if a mod 5 = 0 then m10 := m10 + 1;

            else m2 := m2 + 1;

            end

        else begin

            if a mod 5 = 0 then m5 := m5 + 1;

            else m1 := m1 + 1;

            end

    end;

    s := m1 * m10 + m2 * m5 + m5 * m10;

    writeln(s);

end.

 

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

Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)

 

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

 

var

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

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

    s: integer; {количество пар}

    i, j: integer;

begin

    readln(N);

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

    s := 0;

    for i := 1 to N − 1 do begin

        for j := i + 1 to N do begin

            if ((a[i] + a[j]) mod 2 = 1) and ((a[i]*a[j]) mod 5 = 0) then s := s + 1;

        end

    end;

    writeln(s);

end.