Реши на python

Задача: дан массив изменений веса a[1..n] и число k. Нужно минимальное количество новых дней (с любыми значениями) так вставить, чтобы в итоговом массиве не было ни одного непустого подпериода, сумма которого равна k.

Ключевая идея:

• Любое вставление дня можно рассматривать как разрезание массива на части так, чтобы больше не было подпериодов суммой k.
• Минимальное число вставок равно максимальному числу непересекающихся подпоследовательностей (подмассивов) исходного массива, сумма которых равна k.
• Если мы greed-однозначно находим такие подподмассивы слева направо и после каждой найденной подпоследовательности «разрываем» массив (начинаем поиск с конца найденной подпоследовательности), то получаем максимальное число непересекающихся подпоследовательностей, что и является ответом.

Алгоритм:

• Итерируем i от 1 до n, поддерживаем префиксную сумму pref.
• Храним множество (словарь) префиксных сумм текущего «окна» и их индексы. Изначально есть префикс sum 0 на позиции 0.
• Если существует i и j (i < j) такие, что pref[j] - pref[i] = k, то нашли подподмассив [i+1..j] с суммой k. Увеличиваем ответ и «перезапускаем» окно после j: оставляем в хранилище только префикс pref[j] на позиции j.
• Иначе добавляем текущий pref[j] в хранилище и продолжаем.

Сложность: время O(n), память O(n) в худшем случае.

Пример реализации на Python:

def min_insertions_no_k_sum(a, k):
    # Префикс sums: pref(i) — сумма первых i элементов (i от 0..n)
    pref = 0
    # seen хранит префиксные суммы в текущем окне и их индекс (1-based для i)
    # Изначально окно начинается до первого элемента: pref 0 на позиции 0
    seen = {0: 0}
    ans = 0  # минимальное количество вставок (ответ)
    n = len(a)

    for i, x in enumerate(a, 1):  # i = 1..n
        pref += x
        if (pref - k) in seen:
            # нашли подпорядок [seen[pref-k] + 1 .. i] с суммой k
            ans += 1
            # restart окна после i: разрешенные i' >= i
            seen = {pref: i}
        else:
            seen[pref] = i

    return ans


# Пример использования
if __name__ == "__main__":
    # Вход может быть считан так: n, k затем n чисел a_i
    # Например:
    # 5 6
    # 1 5 1 2 -3
    # print(min_insertions_no_k_sum([1,5,1,2,-3], 6))

    # Реалистичное чтение из stdin:
    import sys
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        sys.exit(0)
    n, k = data[0], data[1]
    arr = data[2:2+n]
    print(min_insertions_no_k_sum(arr, k))

Краткое объяснение примера:

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