Реши на 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: ```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. - Каждую такую подпоследовательность можно разрушить одной вставкой внутри нее. - Поэтому ответ равен количеству найденных непересекающихся подпоследовательностей.