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


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

На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел была нечётна и при этом была максимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Каждый элемент в паре целый, неотрицательный.

 

Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.

Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

 

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве. Перед программой укажите версию языка программирования.

Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.

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

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

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

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

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

 

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 100 000.

 

Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 100 000. На вход подается сначала количество пар, затем сами пары. Числа не превышают 10 000.

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

6

5 4

3 2

1 1

18 3

11 12

2 5

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

43

Решение.

Задание А.

Перебираем все 64 возможных варианта и находим подходящее значение или выводим 0.

 

Приведём пример решения на языке PascalABC.NET 1.8

var a, b, s: integer;

    x: Array [1...12] of integer;

begin

    for var i:= 1 to 12 do

        read (x[i]);

    for var i:= 1 to 2 do

    begin

        for var d:= 3 to 4 do

            begin

                for var c:= 5 to 6 do

                begin

                    for var e: = 7 to 8 do

                    begin

                        for var p:= 9 to 10 do

                        begin

                            for var q:= 11 to 12 do

                            begin

                                s:= x[q] + x[p] + x[c] + x[e] + x[d] + x[i];

                                if (s > b) and (s mod 2 = 1) then

                                    b:= s;

                                s:= 0;

                            end;

                        end;

                    end;

                end;

            end;

        end;

    writeln(b);

end.

 

Задание В.

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

Задание Б.

Приведём пример решения на языке Паскаль:

var

i, n, x, y, sum, min_r: longint;

begin

 readln(n);

 min_r:=10001;

 sum:=0;

 for i:=1 to n do

 begin

  readln(x,y);

  if x > y then sum:=sum + x else sum:= sum + y;

  if (abs(x - y) mod 2 = 1) and (abs(x - y) < min_r) then min_r:= abs(x - y);

 end;

 

 if (sum mod 2 = 1) then writeln(sum) else

  if (sum mod 2 = 0) and (min_r <> 10001) then writeln (sum - min_r) else writeln(0);

 

end.

Источник: ЕГЭ 16.06.2016 по информатике. Основная волна. Вариант 77 (Часть С)