Реши задачу на python и c++

Ниже решение задачи на двух языках: Python и C++. Задача: дан массив a длины n и число k. Нужно минимальное количество дней вставить внутрь календаря так, чтобы не осталось ни одного непустого подотрезка, сумма элементов которого равна k. Вставляемые дни можем заполнить любыми целыми числами.

Идея

• Любой подотрезок [l..r], сумма равна k, делает проблему “нужны вставки” активной: чтобы этот подотрезок перестал существовать как непрерывный, нужно вставить хотя бы один элемент внутри него. Таким образом задача эквивалентна минимальному набору точек разрыва между соседними элементами (между i и i+1, т.е. между позициями 1..n-1) так, чтобы каждый подотрезок, сумма которого равна k, содержал хотя бы одну такую точку разрыва.
• Это классическая задача о минимальном количестве точек, которые пересекают все интервалы ( stabbing/хитинг сет для интервалов). Для интервалов оптимальным жестким алгоритмом является жадный: ставим точку в правый конец первого по завершению интервала, удаляем все интервалы, пересекаемые этой точкой, и повторяем.
• Проблема в том, что может быть много таких подотрезков (особенно если есть нули). Мы можем обойтись без явного перечисления всех подотрезков: пройдём по r от 1 до n и проверим, существует ли подотрезок, заканчивающийся в r, сумма которого равна k и который не пересекается с уже поставленными разрыва(ами). Пусть last_cut — индекс последнего поставленного разрыва (между last_cut и last_cut+1). Подотрезок [l..r] не пересекает этот разрыв тогда, когда l > last_cut.
• Сумма подотрезка [l..r] равна k тогда, если prefix[r] - prefix[l-1] = k, где prefix[i] — префикс сумма. Значит, существует l такое, что prefix[l-1] = prefix[r] - k. Если мы хотим, чтобы подотрезок не пересекался с предыдущими разрывами, то l-1 должен быть не меньше last_cut, то есть t = l-1 ∈ [last_cut, r-1].
• Для быстрых проверок создаём для каждого значения префиксной суммы список всех индексов i, для которых prefix[i] = значение. Тогда для каждого r ищем есть ли t в списке prefix[r]-k, который лежит в диапазоне [last_cut, r-1]. Это делается бинарным поиском.
• Если такой t существует, ставим новый разрыв между r-1 и r, т.е. last_cut = r-1, и увеличиваем ответ.

Сложность: O(n log n) — один бинарный поиск на каждом r. Память: O(n).

Python (решение)

import sys
import bisect

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    k = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    # Префиксные суммы
    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] + a[i - 1]

    # Для каждого значения префикса сохраняем список позиций i (от 0 до n)
    pos = {}
    for i, val in enumerate(pref):
        if val not in pos:
            pos[val] = []
        pos[val].append(i)

    last_cut = -1  # последний поставленный разрыв между last_cut и last_cut+1
    ans = 0

    for r in range(1, n + 1):
        target = pref[r] - k
        if target in pos:
            lst = pos[target]
            # Найти первый t >= last_cut
            idx = bisect.bisect_left(lst, last_cut)
            if idx < len(lst) and lst[idx] <= r - 1:
                # Существует подотрезок [l..r] с суммой k и l-1 = lst[idx] >= last_cut
                ans += 1
                last_cut = r - 1

    print(ans)

if __name__ == "__main__":
    solve()

C++ (решение)

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

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

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // Префиксные суммы
    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i - 1];

    // карта префиксных значений -> вектор индексов
    unordered_map<long long, vector<int>> pos;
    pos.reserve(n * 2);
    for (int i = 0; i <= n; ++i) {
        pos[pref[i]].push_back(i);
    }

    long long last_cut = -1; // последний разрыв между last_cut и last_cut+1
    int ans = 0;

    for (int r = 1; r <= n; ++r) {
        long long target = pref[r] - k;
        auto it = pos.find(target);
        if (it != pos.end()) {
            const vector<int>& lst = it->second;
            // Найти первый индекc t >= last_cut
            auto itlb = lower_bound(lst.begin(), lst.end(), (int)last_cut);
            if (itlb != lst.end() && *itlb <= r - 1) {
                // существует подотрезок [l..r] с суммой k, не пересекающий предыдущий разрыв
                ++ans;
                last_cut = r - 1;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

Коротко о примерах

• Пример 1: n=5, k=1, массив большие числа. Нет подотрезков суммы 1 => ответ 0.
• Пример 2: n=5, k=4, массив [-4, 3, 5, 0, 1]. Есть подотрезок, сумма которого равна 4 (например, -4+3+5 и т.д.). Один разрыв внутри этого подотрезка достаточно, чтобы уничтожить все такие подотрезки. Ответ 1.