Сумма, делящаяся на три

@Ludwig Larsson · Регистрация: 09.07.2021

Студворк — интернет-сервис помощи студентам

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

Входные данные

В первой строке входных данных содержится число N⩽100000. Во второй строке даны N чисел, по модулю не превосходящих 109, — элементы массива.

Выходные данные

Выведите два числа — индексы начала и конца фрагмента. Если таких фрагментов несколько, то выведите фрагмент с минимальным индексом начала.

Если ответа не существует, то выведите единственное число −1.

Примеры
Ввод
5
1 2 3 4 5
Вывод
1 5
Ввод
4
1 2 3 4
Вывод
1 3

Здравствуйте. Фишка задачи состоит в том, что при делении отрицательного числа (в данном случае префиксные суммы при отрицательном вводе) на положительное (3) мы получаем отрицательный остаток (хотя я не знаю, может ли 0 быть отрицательным...), в остальном сложностей вроде быть не должно - но код традиционно не проходит первый тест.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector <int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        p[i] = p[i - 1] + a[i-1];
    int ibest = 0;
    int jbest = 0;
    int imin = 0;
    for (int j = 1; j < n; ++j)
    {
        if ((abs(p[j+1] - p[imin])) % 3 == 0) {
            if (((j+1) - imin) > ((jbest+1) - ibest)) {
                jbest = j;
                ibest = imin;
            }
        }
    }
    if (ibest == 0 && jbest == 0) {
        cout << -1;
    } else {
        cout << ibest + 1 << " " << jbest + 1 << endl;
    }
    return 0;
}

@Catstail · 14.08.2022, 08:19

Сообщение от Ludwig Larsson

при делении отрицательного числа (в данном случае префиксные суммы при отрицательном вводе) на положительное (3) мы получаем отрицательный остаток

- остаток от деления отрицательного кратного трем на 3 равен нулю. Остальные остатки не играют роли.

И я не вполне понял ваш алгоритм. Как вам удалось справиться одним циклом?

Добавлено через 5 минут
Проверьте свой код на примере:

7
2 3 5 1 2 3 4

Ответ будет -1, тогда как правильный: 2 7 (3+5+1+2+3+4=18 и кратно трем)

@Ludwig Larsson · 14.08.2022, 08:31 **[ТС]**

Спасибо. Значит, нужно как-то в корне менять программу так, чтобы использовались ненулевые остатки (что-нибудь странное наподобие массива остатков от деления на 3...). Не хотелось бы, конечно, усложнять этот код, но я действительно не могу понять, что с ним не так, а остатки - единственная зацепка (просто в Сириусе к некоторым задачам есть подсказки, и вот это она и есть).
Алгоритм не мой, у нас ему в разных вариациях посвящена целая тема

Добавлено через 7 минут
Кажется, я поняла, в чём дело. Программа выводит верный ответ при
7
3 3 5 1 2 3 4
Т.е всё хорошо, когда интересующий нас участок начинается с первого элемента. Подумаю, как исправить остальные случаи

@Volga_ · 14.08.2022, 08:45

Ludwig Larsson, предлагаю вам код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
bool chk(int a[], int imin, int imax)
{
    int s = 0;
    for (int i = imin; i <= imax; i++) s += a[i];
    return (s % 3 == 0);
}
int main()
{
    int n; std::cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) std::cin >> a[i];
    int imin = 0, imax = 0, lmax = 0;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
            if (chk(a, i, j) && lmax < j - i)
            {
                lmax = j - i;
                imin = i;
                imax = j;
            }
    }
    if (lmax) std::cout << imin + 1 << " " << imax + 1;
    else std::cout << -1;
    delete[] a;
    return 0;
}

Тест работы:

Code
1
2
3
7
3 3 5 1 2 3 4
1 7

@Ludwig Larsson · 14.08.2022, 08:46 **[ТС]**

Если кому-нибудь нужно, вот рабочая программа через 2 цикла. Но мне необходимо сделать через один, так что тема актуальна

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector <int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        p[i] = p[i - 1] + a[i-1];
    int ibest = 0;
    int jbest = 0;
    int imin = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; ++j)
        {
            if ((p[j+1] - p[imin]) % 3 == 0) {
                if (((j+1) - imin) > ((jbest+1) - ibest)) {
                    jbest = j;
                    ibest = imin;
                }
            }
        }
        imin += 1;
    }
    if (ibest == 0 && jbest == 0) {
        cout << -1;
    } else {
        cout << ibest + 1 << " " << jbest + 1 << endl;
    }
    return 0;
}

@Volga_ · 14.08.2022, 09:20

Сообщение от Volga_

предлагаю вам код:

Можно сократить мой код (без функции):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
int main()
{
    int n; std::cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) std::cin >> a[i];
    int ibest = 0, jbest = 0, lmax = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int s = a[i];
        for (int j = i + 1; j < n; j++)
        {
            s += a[j];
            if (s % 3 == 0 && lmax < j - i)
            {
                lmax = j - i;
                ibest = i + 1;
                jbest = j + 1;
            }
        }
    }
    if (lmax) std::cout << ibest << " " << jbest;
    else std::cout << -1;
    delete[] a;
    return 0;
}

@Ludwig Larsson · 14.08.2022, 09:29 **[ТС]**

Большое Вам спасибо! Но всё равно не проходит по времени

@TheCalligrapher · 14.08.2022, 10:14

Сообщение от Ludwig Larsson

Но всё равно не проходит по времени

Правильное решение этой задачи здесь обсуждалось не так давно. Нет необходимости начинать все сначала.

Учитывая, что участник Volga_ отметился и в той теме тоже, не ясно, зачем он снова изобретает квадратичные решения, когда известно линейное. Весь смысл этой задачи заключается именно в нахождении линейного решения.

Добавлено через 4 минуты

Сообщение от Catstail

И я не вполне понял ваш алгоритм. Как вам удалось справиться одним циклом?

Задача "Сумма, делящаяся на 3"

Задача прекрасно решается одним циклом.

Сообщение от Ludwig Larsson

Фишка задачи состоит в том, что при делении отрицательного числа (в данном случае префиксные суммы при отрицательном вводе) на положительное (3) мы получаем отрицательный остаток

Задача "Сумма, делящаяся на 3"

Но что у вас там понаписано в коде - не ясно. Боюсь, то там все намного хуже, чем просто "фишка при делении отрицательного числа".

ФедосеевПавел · 14.08.2022, 12:36

Ludwig Larsson, правильно начинаете, но не доводите алгоритм до завершения.

Есть особенность получения остатков от деления отрицательных чисел, о которой говорил TheCalligrapher
Задача "Сумма, делящаяся на 3"

Сообщение от TheCalligrapher

Одна проблема, которая бросается в глаза: в языке С++ операторы / и % реализуют не Евклидово деление, а деление с округлением к нулю. Поэтому если в массиве встретятся отрицательные числа, то код не будет работать правильно. Для отрицательных значений оператор % будет давать отрицательные результаты, в результате чего у вас все накроется медным тазом.
Вам нужно отдельно обрабатывать вычисление % 3 для отрицательных значений. Вам нужно чтобы -5 % 3 давало 1 (как в Евклидовом делении), а в С++ -5 % 3 дает -2.

Т.е. для получения элементов массива p[] нужно преобразовать формулу

C++
1
2
3
4
5
6
int sum=0;
for(int i=0; i<n; i++)
{
  sum = ((sum+a[i])%3)+3)%3;
  p[i] = sum;
}

Теперь в элементе массива p[i] остаток от деления суммы элементов a[0]+...+a[i] на 3.
Предположим, что в элементах p[min] и p[max] (причём min<max) находятся одинаковые числа - остатки от деления на 3. Значит, сумма элементов a[] от индекса min+1 до индекса max - делится на 3.

Осталось найти крайний слева и крайний справа элементы p[] для каждого из возможных остатков - и отрезок между ними будет одним из кандидатов на рассмотрение результата - самого длинного отрезка.
И стоит принять во внимание, что для остатка 0 рассматривается сумма от первого элемента массива, не так, как для других остатков.

После решения таким способом, можно начать улучшать программу.
1. Нетрудно заметить, что массив a[] используется лишь для заполнения массива p[]. Значит массив p[] можно не заводить, а префиксную сумму помещать сразу в a[].
2. Да и сам массив p[] тоже не нужен - от него требуется лишь помощь в поиске индексов первого и последнего вхождения каждого из трёх возможных остатков от деления на три префиксной суммы. Значит можно обойтись массивами left[3] и right[3], в которых будут сохраняться соответственно крайние левый и правый индексы вхождения в p[] соответствующих остатков от деления.

Т.е. обойтись без массива a[] и заполнять массивы left[] и right[] по мере чтения элементов a[] из потока.

@Royal_X · 14.08.2022, 18:14

Сообщение от ФедосеевПавел

в языке С++ операторы / и % реализуют не Евклидово деление, а деление с округлением к нулю

там не деление с округлением к нулю, а отбрасывание дробной части.
Modulo (%) в С++ и С# не является математической функцией modulo, а работает как remainder.

В математике принято в формуле modulo использовать floored definition:

Code
1
a % b = a - b * floor(a/b)

C++, C# используют truncated definition:

Code
1
a % b = a - b * truncate(a/b)

В Википедии есть таблица по языкам: https://en.wikipedia.org/wiki/Modulo_operation

@TheCalligrapher · 14.08.2022, 18:23

Сообщение от Royal_X

там не деление с округлением к нулю, а отбрасывание дробной части.

И в чем же заключается разница между "округлением к нулю" и "отбрасыванием дробной части"?

@Royal_X · 14.08.2022, 18:55

Сообщение от TheCalligrapher

И в чем же заключается разница между "округлением к нулю" и "отбрасыванием дробной части"?

вроде есть разница в представлении чисел в дополнительном коде (two’s complement)

Rounding to zero and truncation or chopping are sometimes thought to mean the same thing. However, the results produced by rounding to zero and truncation are different for unsigned and two's complement numbers.
To illustrate this point, consider rounding a 5-bit unsigned number to zero by dropping (truncating) the two least significant bits. For example, the unsigned number 100.01 = 4.25 is truncated to 100 = 4. Therefore, truncating an unsigned number is equivalent to rounding to zero or rounding to floor.
Now consider rounding a 5-bit two's complement number by dropping the two least significant bits. At first glance, you may think truncating a two's complement number is the same as rounding to zero. For example, dropping the last two digits of -3.75 yields -3.00. However, digital hardware performing two's complement arithmetic yields a different result. Specifically, the number 100.01 = -3.75 truncates to 100 = -4, which is rounding to floor.

@TheCalligrapher · 14.08.2022, 19:33

Сообщение от Royal_X

вроде есть разница в представлении чисел в дополнительном коде (two’s complement)

А какое отношение two’s complement имеет к представлению дробных чисел?

Сообщение от Royal_X

Rounding to zero and truncation or chopping are sometimes thought to mean the same thing. However, the results produced by rounding to zero and truncation are different for unsigned and two's complement numbers.
To illustrate this point, consider rounding a 5-bit unsigned number to zero by dropping (truncating) the two least significant bits. For example, the unsigned number 100.01 = 4.25 is truncated to 100 = 4. Therefore, truncating an unsigned number is equivalent to rounding to zero or rounding to floor.
Now consider rounding a 5-bit two's complement number by dropping the two least significant bits. At first glance, you may think truncating a two's complement number is the same as rounding to zero. For example, dropping the last two digits of -3.75 yields -3.00. However, digital hardware performing two's complement arithmetic yields a different result. Specifically, the number 100.01 = -3.75 truncates to 100 = -4, which is rounding to floor.

Вышепроцитированное - это какие-то рассуждения, завязанные на какие-то местечковые доморощенные соглашения и термины, которые в приведенной цитате не оговорены.

Во-первых, почему-то предполагается, что truncation - это обнуление младших битов. С чего бы это вдруг?

Во-вторых, приводятся примеры дробных чисел, но при этом ведется речь об unsigned и two's complement представлениях. Я могу лишь навскидку предположить, что скорее всего речь идет об fixed point представлении дробных чисел.

То есть фактически процитированный кусок - это что-то из разряда "Мы с Васей решили попробовать поиграться с fixed point представлением дробных чисел, и если мы с Васей будет делать вот так, то в результате получится вот эдак. При этом термином truncation мы с Васей называем просто обнуление младших битов".

@Royal_X · 14.08.2022, 20:28

TheCalligrapher, ок, значит я был неправ

@art21kirichenko · 30.07.2024, 09:39

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> s(6, -1);
    int mmax = -1;
    int maxlen = 0;
    int m = 0;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        if (s[m % 3] < 0)
            s[m % 3] = i;
        m = (((m + a) % 3) + 3) % 3;
        if (s[m % 3] >= 0) {
            s[(m % 3) + 3] = i;
            if (s[(m % 3) + 3] - s[m % 3] + 1 > maxlen) {
                maxlen = s[(m % 3) + 3] - s[m % 3] + 1;
                mmax = m % 3;
            }
        }
    }
    if (mmax >= 0)
        cout << s[mmax] + 1 << " " << s[mmax + 3] + 1;
    else
        cout << mmax;
}

Продолжая вашу тему, могу сказать, что код принял Сириус

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Ludwig Larsson 3 / 3 / 1 Регистрация: 09.07.2021 Сообщений: 34
	14.08.2022, 08:31 [ТС]
	Спасибо. Значит, нужно как-то в корне менять программу так, чтобы использовались ненулевые остатки (что-нибудь странное наподобие массива остатков от деления на 3...). Не хотелось бы, конечно, усложнять этот код, но я действительно не могу понять, что с ним не так, а остатки - единственная зацепка (просто в Сириусе к некоторым задачам есть подсказки, и вот это она и есть). Алгоритм не мой, у нас ему в разных вариациях посвящена целая тема Добавлено через 7 минут Кажется, я поняла, в чём дело. Программа выводит верный ответ при 7 3 3 5 1 2 3 4 Т.е всё хорошо, когда интересующий нас участок начинается с первого элемента. Подумаю, как исправить остальные случаи 0

@Ludwig Larsson 3 / 3 / 1 Регистрация: 09.07.2021 Сообщений: 34
	14.08.2022, 09:29 [ТС]
	Большое Вам спасибо! Но всё равно не проходит по времени 0

@Royal_X 6147 / 2840 / 1040 Регистрация: 01.06.2021 Сообщений: 10,348
	14.08.2022, 20:28
	TheCalligrapher, ок, значит я был неправ 0

Сумма, делящаяся на три

Решение