Найти самый длинный непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3. В первой строке

Lunnyy_Shaman_2059

50

Для того чтобы найти самый длинный непрерывный фрагмент в массиве, сумма элементов которого делится на 3, мы можем использовать следующий алгоритм:

1. Создаем переменные `max_len` и `start_index` и устанавливаем их значения равными нулю.
2. Создаем переменную `current_sum` и устанавливаем ее значение равным нулю.
3. Создаем переменную `mod_index` и устанавливаем ее значение равным -1. Эта переменная будет хранить индекс элемента, сумма элементов до которого делится на 3.
4. Проходим по каждому элементу `a[i]` в массиве, начиная с индекса 1.
- Увеличиваем `current_sum` на значение `a[i]`.
- Вычисляем остаток от деления `current_sum` на 3 и сохраняем его в переменную `remainder`.
- Если `remainder` равен 0, то текущая сумма `current_sum` делится на 3.
- Проверяем, является ли текущий фрагмент длиннее предыдущего найденного самого длинного фрагмента.
- Если да, то обновляем значение `max_len` и `start_index` соответственно.
- Если значение `mod_index` равно -1, то устанавливаем его равным текущему индексу `i`.
- Если значение `mod_index` не равно -1, то проверяем, является ли текущая длина фрагмента больше предыдущего найденного самого длинного фрагмента.
- Если да, то обновляем значение `max_len` и `start_index` соответственно.
- Если значение `remainder` равно 0 и значение `mod_index` не равно -1, то проверяем, является ли текущий фрагмент длиннее предыдущего найденного самого длинного фрагмента.
- Если да, то обновляем значение `max_len` и `start_index` соответственно.
5. Выводим значения `start_index` и `start_index + max_len - 1`.

Давайте реализуем этот алгоритм на языке программирования C++:

cpp

#include 



int main() {

    int N;

    std::cin >> N;



    int a[N];

    for (int i = 0; i < N; i++) {

        std::cin >> a[i];

    }



    int max_len = 0;

    int start_index = 0;

    int current_sum = 0;

    int mod_index = -1;



    for (int i = 0; i < N; i++) {

        current_sum += a[i];

        int remainder = current_sum % 3;



        if (remainder == 0) {

            if (i + 1 > max_len) {

                max_len = i + 1;

                start_index = 0;

            }

        } else {

            if (mod_index == -1) {

                mod_index = i;

            } else if (i - mod_index > max_len) {

                max_len = i - mod_index;

                start_index = mod_index + 1;

            }

        }

    }



    if (max_len > 0) {

        std::cout << start_index + 1 << " " << start_index + max_len << std::endl;

    } else {

        std::cout << -1 << std::endl;

    }



    return 0;

}

Этот код считывает размер массива `N` и его элементы, а затем находит самый длинный непрерывный фрагмент сумма элементов которого делится на 3 и выводит его индексы начала и конца. Если такого фрагмента нет, выводится -1.

Надеюсь, этот обстоятельный ответ помог вам понять, как решить данную задачу. Если есть какие-либо вопросы, не стесняйтесь задавать!