Задание 27

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

После чего необходимо работать уже с этим остатками, а не со всеми данными задачи.

Если вы работаете в С++ или Java на всякий случай используйте long вместо int.

Пример 1

задача

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

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

Даны два входных файла (файл Файл A и файл Файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

В ответе укажите два числа: сначала значение искомой длины для файла А, затем – для файла B.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Общая идея этой задачи состоит в том, что мы будем суммировать все прочитанные числа и запоминать, какой остаток дала та или иная сумма. Если суммы с таким остатком ещё нет, то она просто сохраняется, если уже есть, то сохранённая сумма точно будет меньше, чем новая, ведь новая содержит все элементы, что и предыдущая, имеет тот же остаток, но при этом ещё и свои дополнительные.

Сохранять первую подходящую сумму нам необходимо для того, чтобы после для текущей суммы вычислить её собственный остаток и вычесть сохранённую первую сумму. Тогда оставшиеся элементы будут в сумме делиться на указанное нами, и при этом длина будет максимальной.

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

Java
C++
Python

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Example1 {

    // главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
    // работающая с файлом не запустится
    public static void main(String[] args) throws FileNotFoundException {
        // открываем файл, относительный путь строится от корня проекта
        // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
        Scanner in = new Scanner(new File("src/main/java/problem27/27_A.txt"));
        int n = in.nextInt();

        // массив, хранящий минимальную сумму, имеющую остаток, равный индексу элемента
        int[] minS = new int[43];
        // массив соответствующих длин этих сумм
        int[] ls = new int[43];
        for (int i = 0; i < 43; i++) {
            // заполняем их -1
            minS[i] = -1;
            ls[i] = -1;
        }
        // сумма всех перебранных элементов
        int sum = 0;
        // минимальная длина, задаём просто большое число
        int minL = 100000;
        // максимальная сумма
        int maxSum = 0;
        for (int i = 0; i < n; i++) {
            // читаем число
            int a = in.nextInt();
            // прибавляем его к сумме
            sum += a;
            // получаем остаток от деления суммы на 43
            int r =  sum % 43;
            // если сумма делится нацело, у нас готов ответ
            if (sum % 43 == 0) {
                minL = i + 1;
                maxSum = sum;
                continue;
            }
            // если минимальная сумма имеющая соответствующий остаток не сохранена
            if (minS[r] == -1) {
                // сохраняем сумму в массив минимальных сумм по остаткам с соответствующим индексом
                minS[r] = sum;
                // сохраняем длину последовательности
                ls[r] = i + 1;
            }else{ // если сумма для текущего остатка найдена
                // если выкинув сохранённую сумму, мы получим сумму, большую сохранённой
                if (sum - minS[r] > maxSum) {
                    // сохраняем эту сумму в качестве максимальной
                    maxSum = sum - minS[r];
                    // сохраняем длину, как разность между длиной всех чисел
                    // и длиной последовательности, начинающейся с нулевого
                    // элемента, вычитая которую мы получим сумму, делящуюся на 43
                    minL = i + 1 - ls[r];
                    // если новая сумма равна максимальной, но длина меньше
                } else if (sum - minS[r] == maxSum && i + 1 - ls[r] < minL) {
                    // сохраняем новую длину
                    minL = i + 1 - ls[r];
                }
            }
        }

        // выводим минимальную длину
        System.out.println(minL);

    }
}

#include <iostream>
#include <fstream>
#include <algorithm>

// главный метод программы
int main() {
    // открываем файл
    std::ifstream myfile;
    // бинарник собирается в отдельной папке, поэтому относительный путь такой
    // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
    myfile.open("../problem27/27_B.txt");

    // читаем кол-во
    int n;
    myfile >> n;

    // массив, хранящий минимальную сумму, имеющую остаток, равный индексу элемента
    int minS[43];
    // массив соответствующих длин этих сумм
    int ls[43];
    for (int i = 0; i < 43; i++) {
        // заполняем их -1
        minS[i] = -1;
        ls[i] = -1;
    }

    // сумма всех перебранных элементов
    int sum = 0;
    // минимальная длина, задаём просто большое число
    int minL = 100000;
    // максимальная сумма
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        // читаем число
        int a;
        myfile >> a;
        // прибавляем его к сумме
        sum += a;
        // получаем остаток от деления суммы на 43
        int r = sum % 43;
        // если сумма делится нацело, у нас готов ответ
        if (sum % 43 == 0) {
            minL = i + 1;
            maxSum = sum;
            continue;
        }
        // если минимальная сумма имеющая соответствующий остаток не сохранена
        if (minS[r] == -1) {
            // сохраняем сумму в массив минимальных сумм по остаткам с соответствующим индексом
            minS[r] = sum;
            // сохраняем длину последовательности
            ls[r] = i + 1;
        } else { // если сумма для текущего остатка найдена
            // если выкинув сохранённую сумму, мы получим сумму, большую сохранённой
            if (sum - minS[r] > maxSum) {
                // сохраняем эту сумму в качестве максимальной
                maxSum = sum - minS[r];
                // сохраняем длину, как разность между длиной всех чисел
                // и длиной последовательности, начинающейся с нулевого
                // элемента, вычитая которую мы получим сумму, делящуюся на 43
                minL = i + 1 - ls[r];
                // если новая сумма равна максимальной, но длина меньше
            } else if (sum - minS[r] == maxSum && i + 1 - ls[r] < minL) {
                // сохраняем новую длину
                minL = i + 1 - ls[r];
            }
        }
    }

    // закрываем файл
    myfile.close();
    // выводим максимальное количество
    std::cout << minL << std::endl;


    return 0;
}

# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
f = open('27_A.txt')

# читаем кол-во
n = int(f.readline())

# массив, хранящий минимальную сумму, имеющую остаток, равный индексу элемента
minS = [-1] * 43
# массив соответствующих длин этих сумм
ls = [-1] * 43
# сумма всех перебранных элементов
sum = 0
# минимальная длина, задаём просто большое число
minL = 100000
# максимальная сумма
maxSum = 0
for i in range(n):
    # читаем число
    a = int(f.readline())
    # прибавляем его к сумме
    sum += a
    # получаем остаток от деления суммы на 43
    r = sum % 43
    # если сумма делится нацело, у нас готов ответ
    if sum % 43 == 0:
        minL = i + 1
        maxSum = sum
        continue

    # если минимальная сумма имеющая соответствующий остаток не сохранена
    if minS[r] == -1:
        # сохраняем сумму в массив минимальных сумм по остаткам с соответствующим индексом
        minS[r] = sum
        # сохраняем длину последовательности
        ls[r] = i + 1
    else:  # если сумма для текущего остатка найдена
        # если выкинув сохранённую сумму, мы получим сумму, большую сохранённой
        if sum - minS[r] > maxSum:
            # сохраняем эту сумму в качестве максимальной
            maxSum = sum - minS[r]
            # сохраняем длину, как разность между длиной всех чисел
            # и длиной последовательности, начинающейся с нулевого
            # элемента, вычитая которую мы получим сумму, делящуюся на 43
            minL = i + 1 - ls[r]
            # если новая сумма равна максимальной, но длина меньше
        elif sum - minS[r] == maxSum and i + 1 - ls[r] < minL:
            # сохраняем новую длину
            minL = i + 1 - ls[r]

# выводим минимальную длину
print(minL)

Программа выведет:

Ответ: 185 329329

Пример 2

задача

В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна 12.

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

Даны два входных файла (файл Файл A и файл Файл B), каждый из которых содержит в первой строке количество пар $N (1 \leq N \leq 100000)$ . Каждая из следующих N строк содержит одно натуральное число, не превышающих $10^6$ .

Пример организации исходных данных во входном файле:

Для указанных данных можно выбрать следующие подмножества: {12}; {5, 7}; {5, 7, 12}. Программа должна вывести количество этих множеств – 3. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

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

Вернее, в массиве мы будем хранить количество уже имеющихся подмножеств, сумма которых имеет такой остаток. Тогда если мы получаем новое значение, то мы можем добавить его к любому множеству, а значит, кол-во таких множеств увеличится на столько, сколько их уже было.

Java
C++
Python

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Example2 {

    // главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
    // работающая с файлом не запустится
    public static void main(String[] args) throws FileNotFoundException {
        // открываем файл, относительный путь строится от корня проекта
        // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
        Scanner in = new Scanner(new File("src/main/java/problem27/27-1b.txt"));

        // читаем кол-во чисел
        int n = in.nextInt();
        // создаём массив для подсчёта подмножеств, сумма которых имеет тот
        // или иной остаток от деления на 12
        long[] d = new long[12];

        // читаем сами числа
        for (int i = 0; i < n; i++) {
            // читаем число
            int v = in.nextInt();
            // формируем новый массив остатков
            long[] dc = Arrays.copyOf(d, 12);

            // Перебираем элементы нового массива остатков, т.к.
            // мы должны взять каждый из элементов массива остатков.
            // Кол-во чисел в нём говорит о том, сколько подмножеств имеют остаток
            // от деления суммы своих элементов. новый элемент мы можем добавить к любому
            // из подмножеств. Чтобы получить индекс полученного элемента, мы
            // просто находим остаток от деления суммы текущего остатка, равного i и
            // прочитанного числа. При этом т.к. мы могли взять любое из подмножеств с заданным остатком,
            // то надо прибавить кол-во этих множеств. Если мы не сделаем копию
            // массива, то часть остатков будет использовать уже изменённую сумму
            for (int j = 0; j < 12; j++) {
                dc[(v + j) % 12] += d[j];
            }
            // также необходимо увеличить на 1 кол-во подмножеств, сумма элементов которых
            // будет иметь такой же остаток, как прочитанное число. Здесь мы
            // рассматриваем случай, когда новое подмножество состоит только из прочитанного элемента
            dc[v % 12] += 1;
            // заменяем массив
            d = Arrays.copyOf(dc, 12);
        }
        // выводим кол-во подмножеств, имеющих сумму, делящуюся на 12, т.е имеющую
        // остаток 0
        System.out.println(d[0]);

    }
}

#include <iostream>
#include <fstream>
#include <algorithm>

// главный метод программы
int main() {

    // открываем файл
    std::ifstream myfile;
    // бинарник собирается в отдельной папке, поэтому относительный путь такой
    // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
    myfile.open("../problem27/27-1a.txt");

    // читаем кол-во
    int n;
    myfile >> n;
    // создаём массив для подсчёта подмножеств, сумма которых имеет тот
    // или иной остаток от деления на 12
    long d[12];

    // читаем сами числа
    for (int i = 0; i < n; i++) {
        // читаем число
        int v;
        myfile >> v;
        long  dc[12];
        std::copy(std::begin(d), std::end(d), std::begin(dc));

        // Перебираем элементы нового массива остатков, т.к.
        // мы должны взять каждый из элементов массива остатков.
        // Кол-во чисел в нём говорит о том, сколько подмножеств имеют остаток
        // от деления суммы своих элементов. новый элемент мы можем добавить к любому
        // из подмножеств. Чтобы получить индекс полученного элемента, мы
        // просто находим остаток от деления суммы текущего остатка, равного i и
        // прочитанного числа. При этом т.к. мы могли взять любое из подмножеств с заданным остатком,
        // то надо прибавить кол-во этих множеств. Если мы не сделаем копию
        // массива, то часть остатков будет использовать уже изменённую сумму
        for (int j = 0; j < 12; j++) {
            dc[(v + j) % 12] += d[j];
        }
        // также необходимо увеличить на 1 кол-во подмножеств, сумма элементов которых
        // будет иметь такой же остаток, как прочитанное число. Здесь мы
        // рассматриваем случай, когда новое подмножество состоит только из прочитанного элемента
        dc[v % 12] += 1;
        // заменяем массив
        std::copy(std::begin(dc), std::end(dc), std::begin(d));
    }
    // закрываем файл
    myfile.close();
    // выводим кол-во подмножеств, имеющих сумму, делящуюся на 12, т.е имеющую
    // остаток 0
    std::cout << d[0] << std::endl;
    return 0;
}

# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
f = open('27-1a.txt')

# читаем кол-во
n = int(f.readline())

# создаём массив для подсчёта подмножеств, сумма которых имеет тот
# или иной остаток от деления на 12
d = [0] * 12

# читаем сами числа
for i in range(n):
    # читаем число
    v = int(f.readline())
    # формируем новый массив остатков
    dc = d.copy()

    # Перебираем элементы нового массива остатков, т.к.
    # мы должны взять каждый из элементов массива остатков.
    # Кол-во чисел в нём говорит о том, сколько подмножеств имеют остаток
    # от деления суммы своих элементов. новый элемент мы можем добавить к любому
    # из подмножеств. Чтобы получить индекс полученного элемента, мы
    # просто находим остаток от деления суммы текущего остатка, равного i и
    # прочитанного числа. При этом т.к. мы могли взять любое из подмножеств с заданным остатком,
    # то надо прибавить кол-во этих множеств. Если мы не сделаем копию
    # массива, то часть остатков будет использовать уже изменённую сумму
    for j in range(12):
        dc[(v + j) % 12] += d[j]

    # также необходимо увеличить на 1 кол-во подмножеств, сумма элементов которых
    # будет иметь такой же остаток, как прочитанное число. Здесь мы
    # рассматриваем случай, когда новое подмножество состоит только из прочитанного элемента
    dc[v % 12] += 1
    # заменяем массив
    d = dc.copy()

# выводим кол-во подмножеств, имеющих сумму, делящуюся на 12, т.е имеющую
# остаток 0
print(d[0])

Программа выведет:

Ответ: 87375 93824992247807

Пример 3

задача

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 6 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

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

Даны два входных файла (файл Файл A и файл Файл B)), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

Для указанных входных данных значением искомой суммы должно быть число 36 (выбраны числа 4, 9 и 23, их сумма 36 делится на 6). В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

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

Общая идея заключается в том, что мы будем сохранять разницы между элементами, но сохранять будем их в соответствующие элементы массива только если разница минимальна.

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

Больше 5 пар с одинаковыми остатками точно нет смысла брать, поэтому при решении сначала заполняется массив первых пяти разниц каждого остатка, а потом через рекурсию перебираются все возможные наборы чисел по остаткам.

Из этого набора мы берём самые маленькие, ещё не занятые, разницы. Если в результате эти разницы дают сумму, делящуюся на 6, и при этом сама сумма больше максимально сохранённой, сохраняем её в глобальную переменную

Java
C++
Python

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Example3 {
    // максимальная подходящая сумма
    static int maxSum = 0;

    // функция для рекуррентного заполнения массива последовательностями
    // остатков, если при этом все их вычесть из исходной суммы и результат
    // будет делиться на 6, тогда по массиву остатков возьмём
    // столько первых разниц, сколько соответствующих остатков задействовано
    static void process(int pos, int[] arr, int[][] d, int fsum) {
        // если массив остатков полностью заполнен
        if (pos == arr.length) {
            // вычитаем из исходной суммы остатки
            int subs = fsum;
            for (int j : arr) {
                subs -= j;
            }
            // если разность делится на 6
            if (subs % 6 == 0) {
                // номера разностей, которые мы ещё не использовали,
                // пока что все равны 0,
                int[] dPs = new int[6];
                // перебираем массив остатков
                for (int i = 0; i < arr.length; i++) {
                    // если задействованный остаток равен ноль или
                    // мы не встретили достаточное кол-во разниц заданного остатка
                    // и они все кончились
                    if (arr[i] == 0 || d[arr[i]][dPs[i]] == 10000000)
                        // заканчиваем выполнение функции
                        return;
                    // вычитаем из исходной суммы соответствующую разницу
                    fsum -= d[arr[i]][dPs[i]];
                    // говорим, что из массива разниц мы взяли ещё одну
                    dPs[i]++;
                }
                // если новая подходящая сумма больше максимальной
                if (fsum > maxSum)
                    // сохраняем новую сумму в качестве максимальной
                    maxSum = fsum;

            }
        } else
            // на место pos в массиве остатков ставим по очереди все остатки
            for (int i = 0; i < arr.length; i++) {
                // для конкретного варианта ставим на меcто pos остаток, равный i
                arr[pos] = i;
                // запускаем рекурсию для следующего положения
                process(pos + 1, arr, d, fsum);
            }
    }

    // главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
    // работающая с файлом не запустится
    public static void main(String[] args) throws FileNotFoundException {
        // открываем файл, относительный путь строится от корня проекта
        // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
        Scanner in = new Scanner(new File("src/main/java/problem27/27-2a.txt"));


        // читаем кол-во чисел
        int n = in.nextInt();
        // создаём массив для подсчёта остатков
        int[][] d = new int[6][6];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                d[i][j] = 10000000;
            }
        }

        // изначально сумма чисел равна 0
        int sum = 0;

        // читаем сами числа
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int delta = Math.abs(a - b);
            int r = delta % 6;

            int pos = 0;
            while (pos < 6 && d[r][pos] <= delta)
                pos++;
            if (pos < 6)
                d[r][pos] = delta;
            sum += Math.max(a, b);
        }

        // если сумма уже делится на 6
        if (sum % 6 == 0) {
            // выводим её
            System.out.println(sum);
            // завершаем работу программы
            return;
        }

        // запускаем перебор остатков
        process(0, new int[]{0, 0, 0, 0, 0, 0}, d, sum);
        // выводим максимальную сумму
        System.out.println(maxSum);


    }
}

#include <iostream>
#include <fstream>
#include <algorithm>

// максимальная подходящая сумма
int maxSum = 0;

// создаём массив для подсчёта подмножеств, сумма которых имеет тот
// или иной остаток от деления на 12
int d[6][6];

// функция для рекуррентного заполнения массива последовательностями
// остатков, если при этом все их вычесть из исходной суммы и результат
// будет делиться на 6, тогда по массиву остатков возьмём
// столько первых разниц, сколько соответствующих остатков задействовано
void process(int pos, int *arr, int fsum) {
    // если массив остатков полностью заполнен
    if (pos == 6) {
        // вычитаем из исходной суммы остатки
        int subs = fsum;
        for (int j = 0; j < 6; j++) {
            subs -= arr[j];
        }
        // если разность делится на 6
        if (subs % 6 == 0) {
            // номера разностей, которые мы ещё не использовали,
            // пока что все равны 0,
            int dPs[6];
            std::fill(std::begin(dPs), std::begin(dPs) + 6, 0);
            // перебираем массив остатков
            for (int i = 0; i < 6; i++) {
                // если задействованный остаток равен ноль или
                // мы не встретили достаточное кол-во разниц заданного остатка
                // и они все кончились
                if (arr[i] == 0 || d[arr[i]][dPs[i]] == 10000000)
                    // заканчиваем выполнение функции
                    return;
                // вычитаем из исходной суммы соответствующую разницу
                fsum -= d[arr[i]][dPs[i]];
                // говорим, что из массива разниц мы взяли ещё одну
                dPs[i]++;
            }
            // если новая подходящая сумма больше максимальной
            if (fsum > maxSum)
                // сохраняем новую сумму в качестве максимальной
                maxSum = fsum;

        }
    } else
        // на место pos в массиве остатков ставим по очереди все остатки
        for (int i = 0; i < 6; i++) {
            // для конкретного варианта ставим на меcто pos остаток, равный i
            arr[pos] = i;
            // запускаем рекурсию для следующего положения
            process(pos + 1, arr, fsum);
        }
}

// главный метод программы
int main() {
    // открываем файл
    std::ifstream myfile;
    // бинарник собирается в отдельной папке, поэтому относительный путь такой
    // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
    myfile.open("../problem27/27-2b.txt");

    // читаем кол-во
    int n;
    myfile >> n;
    // создаём массив для подсчёта остатков
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            d[i][j] = 10000000;
        }
    }

    // изначально сумма чисел равна 0
    int sum = 0;

    // читаем сами числа
    for (int i = 0; i < n; i++) {
        int a;
        myfile >> a;
        int b;
        myfile >> b;
        int delta = std::abs(a - b);
        int r = delta % 6;

        int pos = 0;
        while (pos < 6 && d[r][pos] <= delta)
            pos++;
        if (pos < 6)
            d[r][pos] = delta;
        sum += std::max(a, b);
    }

    // если сумма уже делится на 6
    if (sum % 6 == 0) {
        // выводим её
        std::cout << sum << std::endl;
        // завершаем работу программы
        return 0;
    }

    // запускаем перебор остатков
    int init[] = {0, 0, 0, 0, 0, 0};
    process(0, init, sum);
    // выводим максимальную сумму
    std::cout << maxSum << std::endl;

    return 0;
}

# максимальная подходящая сумма
maxSum = 0


# функция для рекуррентного заполнения массива последовательностями
# остатков, если при этом все их вычесть из исходной суммы и результат
# будет делиться на 6, тогда по массиву остатков возьмём
# столько первых разниц, сколько соответствующих остатков задействовано
def process(pos, arr, d, fsum):
    global maxSum
    # если массив остатков полностью заполнен
    if pos == len(arr):
        # вычитаем из исходной суммы остатки
        subs = fsum
        for j in arr:
            subs -= j

        # если разность делится на 6
        if subs % 6 == 0:
            # номера разностей, которые мы ещё не использовали,
            # пока что все равны 0,
            dPs = [0] * 6
            # перебираем массив остатков
            for i in range(len(arr)):
                # если задействованный остаток равен ноль или
                # мы не встретили достаточное кол-во разниц заданного остатка
                # и они все кончились
                if arr[i] == 0 or d[arr[i]][dPs[i]] == 10000000:
                    # заканчиваем выполнение функции
                    return
                # вычитаем из исходной суммы соответствующую разницу
                fsum -= d[arr[i]][dPs[i]]
                # говорим, что из массива разниц мы взяли ещё одну
                dPs[i] += 1

                # если новая подходящая сумма больше максимальной
            if fsum > maxSum:
                # сохраняем новую сумму в качестве максимальной
                maxSum = fsum


    else:
        # на место pos в массиве остатков ставим по очереди все остатки
        for i in range(len(arr)):
            # для конкретного варианта ставим на меcто pos остаток, равный i
            arr[pos] = i
            # запускаем рекурсию для следующего положения
            process(pos + 1, arr, d, fsum)

# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
f = open('27-2b.txt')

# читаем кол-во 
n = int(f.readline())

# читаем кол-во
# создаём массив для подсчёта подмножеств, сумма которых имеет тот
# или иной остаток от деления на 12
d = [[10000000] * 6] * 6

# изначально сумма чисел равна 0
sum = 0

# читаем сами числа
for i in range(n):
    # читаем строку файла
    line = f.readline()
    # получаем элементы
    elems = line.split(' ')
    # объём хранилища - первый элемент
    a = int(elems[0])
    # кол-во файлов - второй
    b = int(elems[1])

    delta = abs(a - b)
    r = delta % 6

    pos = 0
    while pos < 6 and d[r][pos] <= delta:
        pos += 1
    if pos < 6:
        d[r][pos] = delta
    sum += max(a, b)

# если сумма уже делится на 6
if sum % 6 == 0:
    # выводим её
    print(sum)
else:
    # запускаем перебор остатков
    init = [0, 0, 0, 0, 0, 0]
    process(0, init, d, sum)
    # выводим максимальную сумму
    print(maxSum)

Программа выведет:

108444 401536398

Ответ: 108444 401536398

Пример 4

задача

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, состоящие более чем из ста элементов. Необходимо определить количество таких последовательностей, сумма элементов которых кратна 1111.

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

В ответе укажите два числа: сначала значение искомой суммы для файла A, затем - для файла B.

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

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

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

Также отдельно надо увеличивать это количество для каждой суммы, которая сама по себе делится на заданное число. Ведь складывающие эту сумму элементы тоже являются подпоследовательностью. Просто она включает в себя все прочитанные элементы.

Java
C++
Python

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class Example4 {

    // главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
    // работающая с файлом не запустится
    public static void main(String[] args) throws FileNotFoundException {
        // открываем файл, относительный путь строится от корня проекта
        // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
        Scanner in = new Scanner(new File("src/main/java/problem27/27-3B.txt"));
        int n = in.nextInt();
        // число, на которое должна делиться подпоследовательность
        int d = 1111;
        // минимальная длина последовательности
        int m = 100;

        // списки индексов элементов, сумма всех элементов до которого включительно
        // даёт соответствующий остаток. Например: в динамическом списке под индексом
        // 5 будут запоминаться индексы всех элементов, сумма до которых имеет остаток
        // равный 5
        ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
        for (int i = 0; i < d; i++) {
            rs.add(new ArrayList<>());
        }

        // сумма всех прочитанных элементов изначально равна 0
        int sum = 0;
        // кол-во подпоследовательностей делящихся на заданное число - тоже
        int cnt = 0;
        // читаем числа
        for (int i = 0; i < n; i++) {
            // Читаем число
            int a = in.nextInt();
            // прибавляем его к сумме
            sum += a;
            // если элементов уже больше заданной границы и при этом сумма сама по себе
            // делится на заданное число
            if (i > m && sum % d == 0)
                // увеличиваем кол-во подпоследовательностей на 1
                cnt++;

            // получаем список индексов всех элементов сумма всех чисел до которых
            // имеет соответствующий остаток
            ArrayList<Integer> rPoses = rs.get(sum % d);

            // перебираем индексы всех элементов, сумма до которых имеет
            // такой эже остаток, если мы вычтем суммы всех элементов
            // до прочитанного эту сумму, то это будет сумма подпоследовательности
            // начиная со следующего после сохранённого в динамическом списке
            // индекса. При этом она будет делиться на заданное число
            // поэтому перебираем все индексы элементов, сумма до которых
            // имеет такой же остаток
            for (Integer rPos : rPoses)
                // если при этом расстояние между положением прочитанного элемента
                // и перебираемым индексом больше заданной длины
                if (i - rPos > m)
                    // значит подпоследовательность будет допустимое
                    // число элементов и при этом будет делиться на заданное число
                    cnt++;

            // добавляем в список индексов номер прочитанного элемента
            rPoses.add(i);

        }

        // выводим кол-во последовательностей, делящихся на
        // заданное число
        System.out.println(cnt);

    }
}

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

// главный метод программы
int main() {
    // открываем файл
    std::ifstream myfile;
    // бинарник собирается в отдельной папке, поэтому относительный путь такой
    // можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
    myfile.open("../problem27/27-3B.txt");

    // читаем кол-во
    int n;
    myfile >> n;
    // число, на которое должна делиться подпоследовательность
    int d = 1111;
    // минимальная длина последовательности
    int m = 100;

    // списки индексов элементов, сумма всех элементов до которого включительно
    // даёт соответствующий остаток. Например: в динамическом списке под индексом
    // 5 будут запоминаться индексы всех элементов, сумма до которых имеет остаток
    // равный 5
    std::vector<std::vector<int>> rs;
    for (int i = 0; i < d; i++) {
        std::vector<int> v;
        rs.push_back(v);
    }

    // сумма всех прочитанных элементов изначально равна 0
    int sum = 0;
    // кол-во подпоследовательностей делящихся на заданное число - тоже
    int cnt = 0;
    // читаем числа
    for (int i = 0; i < n; i++) {
        // Читаем число
        int a;
        myfile >> a;
        // прибавляем его к сумме
        sum += a;
        // если элементов уже больше заданной границы и при этом сумма сама по себе
        // делится на заданное число
        if (i > m && sum % d == 0)
            // увеличиваем кол-во подпоследовательностей на 1
            cnt++;

        // получаем список индексов всех элементов сумма всех чисел до которых
        // имеет соответствующий остаток
        // ОБЯЗАТЕЛЬНО ИСПОЛЬЗУЙТЕ ССЫЛКУ &, иначе будете работать с копией вектора,
        // которая уничтожится в конце итерации
        std::vector<int> & rPoses = rs[sum % d];

        // перебираем индексы всех элементов, сумма до которых имеет
        // такой эже остаток, если мы вычтем суммы всех элементов
        // до прочитанного эту сумму, то это будет сумма подпоследовательности
        // начиная со следующего после сохранённого в динамическом списке
        // индекса. При этом она будет делиться на заданное число
        // поэтому перебираем все индексы элементов, сумма до которых
        // имеет такой же остаток
        for (int rPos: rPoses)
            // если при этом расстояние между положением прочитанного элемента
            // и перебираемым индексом больше заданной длины
            if (i - rPos > m)
                // значит подпоследовательность будет допустимое
                // число элементов и при этом будет делиться на заданное число
                cnt++;

        // добавляем в список индексов номер прочитанного элемента
        rPoses.push_back(i);
    }

    // выводим кол-во последовательностей, делящихся на
    // заданное число
    std::cout << cnt;


    return 0;
}

# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
f = open('27-3B.txt')

# читаем кол-во
n = int(f.readline())

# число, на которое должна делиться подпоследовательность
d = 1111
# минимальная длина последовательности
m = 100

# списки индексов элементов, сумма всех элементов до которого включительно
# даёт соответствующий остаток. Например: в динамическом списке под индексом
# 5 будут запоминаться индексы всех элементов, сумма до которых имеет остаток
# равный 5
rs = []
for i in range(d):
    rs.append([])

# сумма всех прочитанных элементов изначально равна 0
sum = 0
# кол-во подпоследовательностей делящихся на заданное число - тоже
cnt = 0

#print(n // 1000)

# читаем числа
for i in range(n):
    # Читаем число
    a = int(f.readline())
    # прибавляем его к сумме
    sum += a
    # если элементов уже больше заданной границы и при этом сумма сама по себе
    # делится на заданное число
    if i > m and sum % d == 0:
        # увеличиваем кол-во подпоследовательностей на 1
        cnt += 1

    #if i % 1000 == 0:
    #    print(i // 1000)

    # получаем список индексов всех элементов сумма всех чисел до которых
    # имеет соответствующий остаток
    rPoses = rs[sum % d]

    # перебираем индексы всех элементов, сумма до которых имеет
    # такой эже остаток, если мы вычтем суммы всех элементов
    # до прочитанного эту сумму, то это будет сумма подпоследовательности
    # начиная со следующего после сохранённого в динамическом списке
    # индекса. При этом она будет делиться на заданное число
    # поэтому перебираем все индексы элементов, сумма до которых
    # имеет такой же остаток
    for rPos in rPoses:
        # если при этом расстояние между положением прочитанного элемента
        # и перебираемым индексом больше заданной длины
        if i - rPos > m:
            # значит подпоследовательность будет допустимое
            # число элементов и при этом будет делиться на заданное число
            cnt += 1

    # добавляем в список индексов номер прочитанного элемента
    rPoses.append(i)

# выводим кол-во последовательностей, делящихся на
# заданное число
print(cnt)

Программа выведет:

1619987709

Ответ: 267 1619987709

В Python такое решение работает сильно дольше, чем на Java и C++. Поэтому если Вы используете его, то придётся подождать несколько минут. Чтобы видеть прогресс, раскомментируйте строки в исходнике

    # print(n // 1000)
    ...
    #if i % 1000 == 0:
    #    print(i // 1000)

Тогда сначала программа выведет, сколько тысяч чисел будет обработано, а потом будет выводить номер каждой обработанной тысячи.

Задания для самостоятельного выполнения

Файлы для задач

Пример 1​

Пример 2​

Пример 3​

Пример 4​

Пример 1

Пример 2

Пример 3

Пример 4