Задача 5323. Источник: Поляков. Задание КИМ 27
На вход программе поступает последовательность натуральных чисел. Найдите непрерывную подпоследовательность с максимальной суммой, в которой сумма элементов на четных позициях равна сумме элементов на нечетных позициях.
Входные данные. Даны два входных файла (файл A и файл B), содержит в первой строке число N (2 ≤ N ≤ 5 000 000) – количество чисел в последовательности. Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.
Пример входного файла:
7
5
7
5
4
8
2
1
Для этой последовательности искомая подпоследовательность {7, 5, 4, 8, 2}, потому как 7+4+2 = 5+8 = 13. Сумма всех элементов последовательности – 26. Ответ: 26.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Для решения данной задачи сформируем массив префиксных сумм, который будет содержать префиксные суммы для элементов на четных и нечетных позициях. Это позволит быстро находить сумму для любого диапазона, как разность префиксной суммы для конечного элемента и элемента, предшествующего начальному. Циклы организуем от наибольших диапазонов к меньшим. Так же будем проверять, меньше ли текущая сумма найденной максимальной. Если это так, то прерываем внутренний цикл, т.к. большей суммы нам уже не найти, а если это случилось для максимального диапазона внешнего цикла, то выводим результат и прерываем работу программы. На компилируемых языках можно обойтись без данной проверки и получить ответ через несколько десятков секунд, но на языке Python даже с такой проверкой ответ ищется от 2,5 минут, а без нее программа будет перебирать все диапазоны пару часов.
Python
f = open('27-121b.txt')
n = int(f.readline())
a = [int(x) for x in f]
b = [0] * 2
for i in a:
b.append(b[-2] + i)
mx = 0
for i in range(n - 1):
for j in range(n - 1, i, -1):
if i % 2 == 0:
start_even = i
start_odd = i + 1
else:
start_even = i + 1
start_odd = i
if j%2==0:
end_even = j + 2
end_odd = j + 1
else:
end_even = j + 1
end_odd=j + 2
s_even = b[end_even] - b[start_even]
s_odd = b[end_odd] - b[start_odd]
if s_even + s_odd < mx:
if j == n - 1:
print(mx)
exit()
break
if s_even == s_odd:
mx = max(mx, s_even + s_odd)
break
PascalABC
var
i, j, n, z, max, start_even, start_odd, end_even, end_odd, s_even, s_odd: Integer;
a: array [1..146286] of Integer;
f: TEXT;
begin
Assign(f, '27-121b.txt');
Reset(f);
Readln(f, n);
a[1] := 0;
a[2] := 0;
max := 0;
for i := 1 to n do
begin
readln(f, z);
a[i + 2] := a[i] + z;
end;
for i := 1 to n - 1 do
for j := n downto i + 1 do
begin
if i mod 2 = 0 then
begin
start_even := i;
start_odd := i + 1;
end
else
begin
start_even := i + 1;
start_odd := i;
end;
if j mod 2 = 0 then
begin
end_even := j + 2;
end_odd := j + 1;
end
else
begin
end_even := j + 1;
end_odd := j + 2;
end;
s_even := a[end_even] - a[start_even];
s_odd := a[end_odd] - a[start_odd];
if s_even + s_odd < max then
begin
if j = n - 1 then
begin
Writeln(max);
Exit;
end;
break;
end;
if (s_even = s_odd) and (s_even + s_odd > max) then
begin
max := s_even + s_odd;
break;
end;
end;
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-121b.txt");
int n;
f >> n;
int a[n + 2];
a[0] = 0;
a[1] = 0;
int max = 0;
for (int i = 0; i < n; i++)
{
int z;
f >> z;
a[i + 2] = a[i] + z;
}
for (int i = 0; i < n - 1; i++)
for (int j = n - 1; j > i; j--)
{
int start_even, start_odd, end_even, end_odd, s_even, s_odd;
if (i % 2 == 0)
{
start_even = i;
start_odd = i + 1;
}
else
{
start_even = i + 1;
start_odd = i;
}
if (j % 2 == 0)
{
end_even = j + 2;
end_odd = j + 1;
}
else
{
end_even = j + 1;
end_odd = j + 2;
}
s_even = a[end_even] - a[start_even];
s_odd = a[end_odd] - a[start_odd];
if (s_even + s_odd < max)
{
if (j == n - 1)
{
cout << max << endl;
return 0;
}
break;
}
if (s_even == s_odd && s_even + s_odd > max)
{
max = s_even + s_odd;
break;
}
}
}
Ответ
27716 264657904