Дана последовательность натуральных чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество чётных элементов кратно k = 10.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел не превышает 2 · 109.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение.
Приведём решение на языке Python.
f = open("27-B.txt")
n = int(f.readline())
lefts = [0 for i in range(10)]
rights = [0 for i in range(10)]
for i in range(10):
lefts[i] = 0
rights[i] = 0
count = 0
sum = 0
for i in range(1, n + 1):
num = int(f.readline())
sum = sum + num
if num % 2 == 0:
count = count + 1
d = count % 10
if lefts[d] == 0:
lefts[d] = sum
rights[d] = sum
maxsum = 0
if count % 10 == 0:
print(sum)
else:
for i in range(1, count % 10 + 1):
if (rights[i] - lefts[i]) > maxsum:
maxsum = rights[i] - lefts[i]
if rights[0] > maxsum:
maxsum = rights[0]
print(maxsum)
Ответ: 4779554 979258630.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Матвея Курченко на языке Python.
f = [int(i) for i in open('27.txt')]
a = [-1] + [i-1 for i in range(1, f[0]+1) if f[i]%2 == 0] + [-1]
Будем последовательно считывать числа из файла. В массив 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 = 0 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 := 1 to (count mod 10) do
if (rights[i] - lefts[i]) > maxsum then maxsum := rights[i] - lefts[i];
if rights[0] > maxsum then maxsum := rights[0];
writeln(maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 4779554, из файла B — 979258630.
Дана последовательность натуральных чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество нечётных элементов кратно k = 10.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма всех чисел не превышает 2 · 109.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение.
Будем последовательно считывать числа из файла. В массив 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 10) do begin
if (rights[i] - lefts[i]) > maxsum then maxsum := rights[i] - lefts[i];
end;
if rights[0] > maxsum then maxsum := rights[0];
writeln(maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 4777208, из файла B — 979268310.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("27-B.txt")
n = int(f.readline())
lefts = [0 for i in range(10)]
rights = [0 for i in range(10)]
for i in range(10):
lefts[i] = 0
rights[i] = 0
count = 0
sum = 0
for i in range(1, n + 1):
num = int(f.readline())
sum = sum + num
if num % 2 == 1:
count = count + 1
d = count % 10
if lefts[d] == 0:
lefts[d] = sum
rights[d] = sum
maxsum = 0
if count % 10 == 0:
print(sum)
else:
for i in range(count % 10 + 1):
if (rights[i] - lefts[i]) > maxsum:
maxsum = rights[i] - lefts[i]
if rights[0] > maxsum:
maxsum = rights[0]
print(maxsum)
Приведём решение Бориса Савельева на языке Python.
Дана последовательность целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных чётных элементов кратно k = 30.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма любой выборки заданных чисел не превышает 2 · 109 по абсолютной величине.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение.
Приведём решение на языке Python.
f = open("27-B.txt")
n = int(f.readline())
lefts = [0 for i in range(30)]
maxsum = 0
for i in range(30):
lefts[i] = 2 * 1000000000
count = 0
sum = 0
for i in range(1, n + 1):
num = int(f.readline())
sum = sum + num
if (num % 2 == 0) and (num > 0):
count = count + 1
d = count % 30
if sum < lefts[d]:
lefts[d] = sum
maxsum = max(maxsum, sum - lefts[d])
print(maxsum)
Ответ: 97011 24932.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение.
Для нахождения искомой суммы найдём сумму всех чисел в файле и, если количество чётных положительных чисел этой суммы не будет кратно 30, вычтем из этой суммы число, являющееся минимальной подсуммой чисел с таким же количеством чётных положительных чисел, кратных 30, как и у суммы всех чисел в файле.
Будем последовательно считывать числа из файла. В массив lefts будем записывать первые встречающиеся суммы с количеством чётных элементов, делящимся на 30 с остатком от нуля до двадцати девяти. Каждое считанное число будем прибавлять к переменной sum. Если очередное встреченное число является чётным и положительным, будем увеличивать значение счётчика count. Каждую итерацию цикла будем проверять, больше ли текущая максимальная сумма в переменной maxsum больше значения выражения sum − lefts[d] (в этом выражении получаем значение новой подсуммы, с количеством чётных положительных чисел кратным 30). Если значение переменной maxsum меньше — обновляем её значение.
Приведём решение задачи на языке Pascal.
var
i, n, num, count, d: integer;
sum, maxsum: int64;
lefts: array[0..29] of int64;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
for i := 0 to 29 do begin
lefts[i] := 2 * 1000000000;
end;
count := 0;
sum := 0;
for i := 1 to n do begin
readln(f, num);
sum := sum + num;
if (num mod 2 = 0) and (num > 0) then count := count + 1;
d := count mod 30;
if sum < lefts[d] then lefts[d] := sum;
maxsum := Max(maxsum, sum - lefts[d]);
end;
writeln(maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 97011, из файла B — 24932.
Дана последовательность целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных нечётных элементов кратно k = 30.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число. Гарантируется, что общая сумма любой выборки заданных чисел не превышает 2 · 109 по абсолютной величине.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.
Ответ:
Решение.
Приведём решение на языке Python.
f = open("27-B.txt")
n = int(f.readline())
lefts = [0 for i in range(n)]
maxsum = 0
for i in range(30):
lefts[i] = 2 * 1000000000
count = 0
sum = 0
for i in range(1, n + 1):
num = int(f.readline())
sum = sum + num
if (num % 2 == 1) and (num > 0):
count = count + 1
d = count % 30
if sum < lefts[d]:
lefts[d] = sum
maxsum = max(maxsum, sum - lefts[d])
print(maxsum)
Ответ: 86097 25057.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение.
Для нахождения искомой суммы найдём сумму всех чисел в файле и, если количество нечётных положительных чисел этой суммы не будет кратно 30, вычтем из этой суммы число, являющееся минимальной подсуммой чисел с таким же количеством нечётных положительных чисел, кратных 30, как и у суммы всех чисел в файле.
Будем последовательно считывать числа из файла. В массив lefts будем записывать первые встречающиеся суммы с количеством нечётных элементов, делящимся на 30 с остатком от нуля до двадцати девяти. Каждое считанное число будем прибавлять к переменной sum. Если очередное встреченное число является нечётным и положительным, будем увеличивать значение счётчика count. Каждую итерацию цикла будем проверять, больше ли текущая максимальная сумма в переменной maxsum больше значения выражения sum − lefts[d] (в этом выражении получаем значение новой подсуммы, с количеством нечётных положительных чисел кратным 30). Если значение переменной maxsum меньше — обновляем её значение.
Приведём решение задачи на языке Pascal.
var
i, n, num, count, d: integer;
sum, maxsum: int64;
lefts: array[0..29] of int64;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
for i := 0 to 29 do begin
lefts[i] := 2 * 1000000000;
end;
count := 0;
sum := 0;
for i := 1 to n do begin
readln(f, num);
sum := sum + num;
if (num mod 2 = 1) and (num > 0) then count := count + 1;
d := count mod 30;
if sum < lefts[d] then lefts[d] := sum;
maxsum := Max(maxsum, sum - lefts[d]);
end;
writeln(maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 86097, из файла B — 25057.
