На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел была нечётна и при этом была максимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 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.