Программное решение задач ЕГЭ по информатике

Задача 5323. Источник: Поляков. Задание КИМ 27

Страница задачи 5323

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

Входные данные. Даны два входных файла (файл 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

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: