Разбор задачи «Курьерский маршрут»

Идея задачи

Дан массив B длины N. Нужно разбить его на несколько непустых подряд идущих отрезков так, чтобы:

• каждый элемент входил ровно в один отрезок;
• суммы всех отрезков были одинаковыми;
• число отрезков было как минимум 2;
• количество отрезков было минимальным.

Если такого разбиения нет, нужно вывести -1.

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

Главное наблюдение

Пусть сумма всех элементов массива равна S.

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

\[ \frac{S}{k} \]

Это означает, что число k обязательно делит сумму S.

То есть искать ответ среди всех чисел от 2 до N не нужно. Достаточно рассматривать только такие k, которые делят S.

Но и это ещё не всё.

Нам нужно найти минимальное количество отрезков. Если некоторое число k подходит, а k составное, то у него есть простой делитель p. В таком случае имеет смысл сначала проверить именно меньшие простые делители.

В данной задаче достаточно перебрать простые делители числа |S| в порядке возрастания и проверить, можно ли разбить массив на p частей.

Как только нашли первый подходящий p, это и будет ответом.

Почему достаточно проверять простые делители суммы

Пусть существует корректное разбиение на k частей, где k >= 2.

Тогда:

\[ S = k \cdot t, \]

где t — сумма каждой части.

Если k составное, то у него есть простой делитель p. Тогда p тоже делит S.

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

Именно поэтому алгоритм такой:

1. Находим сумму S.
2. Если S != 0, раскладываем |S| на простые делители.
3. Для каждого простого делителя p проверяем, можно ли разбить массив на p подряд идущих частей с суммой S / p.
4. Первый подходящий p и есть ответ.

Как проверять фиксированное число частей

Пусть мы хотим проверить, можно ли разбить массив на k частей.

Тогда сумма каждой части должна быть равна:

\[ \text{target} = \frac{S}{k} \]

Дальше идём слева направо и накапливаем текущую сумму.

• Если текущая сумма стала равна target, значит очередной отрезок завершён.
• Сбрасываем текущую сумму в 0 и продолжаем.

• В конце нужно проверить, что:

  • мы набрали ровно k частей;
  • остатка не осталось.

Это делается за один проход по массиву.

Почему такая проверка корректна

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

Если таким способом набралось ровно k частей и ничего не осталось, значит разбиение существует.

Если нет — значит разбиения на k частей с такой суммой не существует.

Особый случай: общая сумма равна нулю

Если S = 0, формула

\[ \text{target} = \frac{S}{k} \]

даёт 0 для любого k.

Значит каждая часть тоже должна иметь сумму 0.

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

Для этого достаточно проверить, существует ли префикс с суммой 0, который заканчивается не в последнем элементе.

Почему этого достаточно?

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

Если такого префикса нет, то разбить на две непустые части с равными суммами нельзя, а значит и ответа нет.

Пошаговый алгоритм

1. Считываем N и массив B.
2. Находим сумму S.
3. Если N < 2, сразу выводим -1.

4. Если S = 0:

   • идём по префиксам, кроме полного массива;
   • если встретили префикс с суммой 0, выводим 2;
   • иначе выводим -1.

5. Если S != 0:

   • находим все различные простые делители числа |S|;
   • сортируем их по возрастанию;
   • для каждого простого делителя p проверяем, можно ли разбить массив на p частей с суммой S / p;
   • как только нашли подходящее p, выводим его.
6. Если ни один делитель не подошёл, выводим -1.

Доказательство корректности

Докажем, что описанный алгоритм всегда выдаёт правильный ответ.

Лемма 1

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

Доказательство. Если сумма каждого из k отрезков равна t, то сумма всего массива равна k * t. Значит, S делится на k. Лемма доказана.

Лемма 2

Для фиксированного k и target = S / k жадная проверка слева направо корректно определяет, существует ли разбиение на k подряд идущих частей с суммой target.

Доказательство. Любое корректное разбиение на подряд идущие части обязано последовательно завершать части в некоторый момент времени при просмотре массива слева направо. Жадная проверка делает ровно это: закрывает текущую часть, когда её сумма становится равной target. Если в конце набралось ровно k частей и остатка нет, значит найдено корректное разбиение. Если этого не произошло, то никакое разбиение на k подряд идущих частей с суммой target невозможно. Лемма доказана.

Лемма 3

Если S = 0 и существует префикс с суммой 0, заканчивающийся не в последнем элементе, то ответ равен 2.

Доказательство. Этот префикс образует первую непустую часть с суммой 0. Оставшаяся часть тоже непуста и имеет сумму 0, потому что сумма всего массива равна 0. Значит существует разбиение на две части, а меньше двух частей по условию быть не может. Следовательно, ответ равен 2. Лемма доказана.

Лемма 4

Если S != 0, то если ответ существует, алгоритм найдёт его среди простых делителей |S|.

Доказательство. По лемме 1 корректное число частей должно делить S. В рамках данной задачи ответ ищется среди минимальных возможных кандидатов, и алгоритм проверяет простые делители |S| по возрастанию. Как только найден первый подходящий делитель, меньшего допустимого ответа уже быть не может. Лемма доказана.

Теорема

Алгоритм выводит правильный ответ для каждого допустимого входа.

Доказательство. Случай S = 0 корректен по лемме 3. Случай S != 0 корректен по леммам 1, 2 и 4. Следовательно, во всех случаях алгоритм выдаёт правильный ответ. Теорема доказана.

Оценка сложности

Пусть S — сумма элементов массива.

• Вычисление суммы: O(N).
• Разложение числа |S| на простые множители: O(\sqrt{|S|}).
• Каждая проверка делителя: O(N).

Итоговая сложность:

\[ O(N \cdot d + \sqrt{|S|}), \]

где d — количество различных простых делителей числа |S|.

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

Память:

\[ O(N) \]

из-за хранения массива.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

bool can_split_into_k_parts(const vector<int>& b, int k, long long target) {
    long long current_sum = 0;
    int parts = 0;

    for (int x : b) {
        current_sum += x;
        if (current_sum == target) {
            parts++;
            current_sum = 0;
        }
    }

    return (current_sum == 0 && parts == k);
}

int solve(int n, const vector<int>& b) {
    if (n < 2) {
        return -1;
    }

    long long total_sum = 0;
    for (int x : b) {
        total_sum += x;
    }

    if (total_sum == 0) {
        long long prefix_sum = 0;
        for (int i = 0; i + 1 < n; i++) {
            prefix_sum += b[i];
            if (prefix_sum == 0) {
                return 2;
            }
        }
        return -1;
    }

    long long x = llabs(total_sum);
    vector<int> prime_divisors;

    for (long long d = 2; d * d <= x; d++) {
        if (x % d == 0) {
            prime_divisors.push_back((int)d);
            while (x % d == 0) {
                x /= d;
            }
        }
    }
    if (x > 1) {
        prime_divisors.push_back((int)x);
    }

    sort(prime_divisors.begin(), prime_divisors.end());

    for (int p : prime_divisors) {
        long long target = total_sum / p;
        if (can_split_into_k_parts(b, p, target)) {
            return p;
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    cout << solve(n, b) << '\n';
    return 0;
}

Реализация на Python

import sys


def can_split_into_k_parts(b, k, target):
    current_sum = 0
    parts = 0

    for x in b:
        current_sum += x
        if current_sum == target:
            parts += 1
            current_sum = 0

    return current_sum == 0 and parts == k


def solve(n, b):
    if n < 2:
        return -1

    total_sum = sum(b)

    if total_sum == 0:
        prefix_sum = 0
        for i in range(n - 1):
            prefix_sum += b[i]
            if prefix_sum == 0:
                return 2
        return -1

    x = abs(total_sum)
    prime_divisors = []

    d = 2
    while d * d <= x:
        if x % d == 0:
            prime_divisors.append(d)
            while x % d == 0:
                x //= d
        d += 1

    if x > 1:
        prime_divisors.append(x)

    prime_divisors.sort()

    for p in prime_divisors:
        target = total_sum // p
        if can_split_into_k_parts(b, p, target):
            return p

    return -1


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    b = list(map(int, data[1:1 + n]))
    print(solve(n, b))


if __name__ == "__main__":
    main()

Типичные ошибки

1. Пытаться перебирать все k от 2 до N

Такой подход слишком медленный и не использует главное свойство задачи: число частей должно делить сумму массива.

2. Забыть про случай S = 0

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

3. Проверять только количество частей, но не проверять остаток

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

4. Неправильно работать с отрицательной суммой

Разлагать на делители нужно число |S|, а целевая сумма части вычисляется как S / p с исходным знаком.

5. Использовать тип int для общей суммы

Сумма может быть большой, поэтому нужен тип long long в C++.

Небольшой пример вручную

Рассмотрим массив:

-2 4 2 1 1 -1 3

Сумма массива:

S = 8

Простые делители числа 8:

2

Пробуем k = 2. Тогда каждая часть должна иметь сумму:

8 / 2 = 4

Идём слева направо:

• -2 + 4 + 2 = 4 — первая часть готова;
• 1 + 1 - 1 + 3 = 4 — вторая часть готова.

Получили ровно 2 части, значит ответ равен 2.

Итого

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

Главные идеи:

• если массив делится на k равносуммовых подряд идущих частей, то k делит общую сумму;
• для фиксированного k проверка делается за один линейный проход;
• случай нулевой суммы надо разбирать отдельно.