Перейти к содержанию

На вход программе подаются пары неотрицательных чисел

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

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

В первой строке задаётся число N — количество пар чисел. В каждой из следующих N строк задаются два неотрицательных числа, каждое из которых не больше 10 000. Программа должна вывести одно число — описанную в условии сумму либо 0.

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

4

8 3

1 9

4 4

3 1

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

22

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

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

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

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

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

Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.


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

Программа на языке PascalABC. Программа эффективна повремени и по памяти.

var S, N, i, t, d, x, y, mx, my: integer;

begin

S := 0;

d := 10001;

mx := 10001;

my := 10001;

readln(N);

for i := 1 to N do begin

readln(x, y);

if y > x then begin

t := x; x := y;

y := t

end;

S := S + x;

if (x<>y) and ((x-y) mod 4 <>0) and (x-y

then begin

d := x — y;

mx := x; my := y

end

end;

if (S mod 4) = 0 then

begin

if d <> 10001 then

S := S — mx + my

else

S := 0

end;

writeln(S)

end.