Дана последовательность натуральных чисел. Необходимо найти максимально
Условие
Дана последовательность натуральных чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество нечётных элементов кратно k = 10. Входные данные.Файл AФайл BПервая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел не превышает 2 · 10⁹.Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B. Ответ:
Ответ
4777208979268310
Решение по шагам
Как рассуждать
Решение. Будем последовательно считывать числа из файла. В массив lefts будем записывать первые встречающиеся суммы с количеством нечётных элементов, делящимся на 10 с остатком от нуля до девяти. В массив rights также будем записывать суммы с количеством нечётных элементов, делящимся на 10 с остатком от нуля до девяти. Если будет встречено несколько сумм с одним и тем же остатком, в массив rights будет записана сумма, встретившаяся позже. Если после считывания всех чисел из файла значение в переменной count не кратно 10, тогда будем проверять разности элементов массивов rights и lefts с соответствующими индексами и выводить на экран наибольшую из таких разностей — это и будет искомой максимальной суммой. Приведём решение задачи на языке Pascal.var i, n, num, count, d: integer; sum, maxsum: int64; lefts: array[0..9] of int64; rights: array[0..9] of int64; f: text;begin assign(f,'C:\27-B.txt'); reset(f); readln(f, n); for i := 0 to 9 do begin lefts[i] := 0; rights[i] := 0; end; count := 0; sum := 0; for i := 1 to n do begin readln(f, num); sum := sum + num; if num mod 2 = 1 then count := count + 1; d := count mod 10; if lefts[d] = 0 then lefts[d] := sum; rights[d] := sum; end; maxsum := 0; if count mod 10 = 0 then writeln(sum) else for i := 0 to (count mod
Осталось ещё 2 шага — откроются после входа:
- Шаг 2
- Шаг 3
Бесплатно · займёт минуту