Нужно найти самый длинный непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3. Входные
Нужно найти самый длинный непрерывный фрагмент в массиве a1,a2...aN, сумма элементов которого делится на 3. Входные данные В первой строке входного файла задано число N≤100000. Во второй строке входного файла следуют N чисел, модуль которых не превышает 109 — элементы массива. Выходные данные Выведите два числа — индексы начала и конца фрагмента. Если таких фрагментов несколько, выведите фрагмент с наименьшим начальным индексом. Если ответа не существует, выведите число -1. Примеры Ввод Вывод 4 1 2 3 4 1 3 5 1 2 3 4 5 1 5
Маргарита 41
Данная задача можно решить следующим образом.Сначала создадим два словаря: dict_1 и dict_2, в которых ключами будут остатки от деления суммы элементов на 3. Значением словаря dict_1 будет список индексов, сумма элементов до которых делится на 3 без остатка, а значением словаря dict_2 будет список индексов, сумма элементов до которых после деления на 3 имеет остаток 1.
Далее идем по элементам массива слева направо и для каждого элемента выполняем следующие действия:
1. Если элемент делится на 3 без остатка, то добавляем его индекс в список значений словаря dict_1 с ключом 0.
2. Если элемент после деления на 3 имеет остаток 1, то добавляем его индекс в список значений словаря dict_2 с ключом 1.
3. Если элемент после деления на 3 имеет остаток 2, то добавляем его индекс в список значений словаря dict_1 с ключом 2.
После обработки всех элементов массива, найдем самый длинный непрерывный фрагмент с суммой элементов, делящихся на 3, используя словарь dict_1 и суммируя элементы с индексами из этого фрагмента.
Если такой фрагмент не найден, будем искать непрерывный фрагмент с суммой элементов, после деления на 3 имеющих остаток 1. Используем для этого словарь dict_2.
Если ни один из фрагментов не найден, выводим число -1.
В результате получим индексы начала и конца найденного фрагмента.
Давайте разберем наш пример:
Число N равно 4. Вторая строка содержит 4 элемента: 1, 2, 3, 4.
Создаем пустые словари dict_1 и dict_2.
Обрабатываем первый элемент 1:
- 1 делится на 3 без остатка, добавляем его индекс (0) в список значений словаря dict_1 с ключом 0.
Обрабатываем второй элемент 2:
- 2 после деления на 3 имеет остаток 2, добавляем его индекс (1) в список значений словаря dict_1 с ключом 2.
Обрабатываем третий элемент 3:
- 3 делится на 3 без остатка, добавляем его индекс (2) в список значений словаря dict_1 с ключом 0.
Обрабатываем четвертый элемент 4:
- 4 после деления на 3 имеет остаток 1, добавляем его индекс (3) в список значений словаря dict_2 с ключом 1.
Результат:
dict_1 = {0: [0, 2], 2: [1]}
dict_2 = {1: [3]}
На этом этапе нам осталось найти самый длинный непрерывный фрагмент с суммой элементов, делящихся на 3. В нашем случае это фрагмент с индексами от 0 до 2, который соответствует последовательности [1, 2, 3].