Дана последовательность чисел (там положительные и отрицательные), которая заканчивается нулём. Найти наибольшую сумму чисел из данной последовательности при условии, что сумма должна делиться на 3. Паскаль.
Пример последовательности: 2 5 -2 0
сумма в примере = 3
Пример последовательности: 2 5 -2 0
сумма в примере = 3
More Questions From This User See All
Answers & Comments
Verified answer
Будем суммировать все положительные числа, пока не встретится 0. Если полученная сумма сразу делится на 3, то нам повезло. Если нет, надо что-то делать - либо прибавлять отрицательные числа, либо вычитать положительные. Я не буду делать различия между ними - в любом случае надо вычитать модули чисел.- Если сумма дает остаток 1, то надо вычесть или одно число с остатком 1, или два числа с остатком 2 (вычитать три или более числа нерационально: числа, делящиеся на 3, картину не портят; вычитание трёх чисел с одинаковым остатком не влияет на остаток суммы, а среди трёх чисел с остатком 1 или 2 всегда найдутся два одинаковых).
- Аналогично (с точностью до перестановки 1 и 2) поступаем, если сумма даёт остаток 2.
Если после этих всех ухищрений сумма стала отрицательной, просто выводим 0, как будто мы взяли только последний 0.
Код (PascalABC.NET 3.2)
begin
var sum := 0;
var mins := MatrFill(2, 2, MaxInt div 2);
var temp: integer;
repeat
temp := readinteger;
if temp > 0 then
sum := sum + temp;
temp := abs(temp);
var i := temp mod 3 - 1;
if i > -1 then
if temp < mins[i, 0] then
(mins[i, 0], mins[i, 1]) := (temp, mins[i, 0])
else if temp < mins[i, 1] then
mins[i, 1] := temp;
until temp = 0;
var i := sum mod 3 - 1;
if i > -1 then
sum := max(sum - mins[i, 0], sum - mins.Row((i + 1) mod 2).Sum);
writeln(max(sum, 0))
end.