Игорь решил заняться спортом и изменить свой вес. ...

Вот краткое и рабочее решение.

Идея:

• Пусть $x$ — «нелюбимое» число.
• Рассмотрим префиксные суммы $p_0=0, p_i=\sum_{j=1}^i a_j$.
• Нежелательный подотрезок с суммой $x$ существует тогда и только тогда, когда для некоторого текущего префикса $p$ уже встречался префикс $p-x$.
• Будем идти слева направо и хранить множество префиксных сумм внутри текущего сегмента (между двумя вставками).
  Если при добавлении $a_i$ обнаруживаем, что $p_{\text{new}}-x$ уже был в множестве, значит без вставки появится плохой подотрезок, — вынужденно делаем одну вставку перед $a_i$, увеличиваем ответ и начинаем новый сегмент: очищаем множество до $\{0\}$ и «пересчитываем» текущий префикс как если бы сегмент начинался прямо перед $a_i$.

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

Сложность: $O(n)$ по времени и $O(n)$ по памяти.

Код (C++17)

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

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

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

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

    unordered_set<long long> seen;
    seen.reserve((size_t)n * 2 + 10);
    seen.insert(0);            // префикс внутри текущего сегмента
    long long pref = 0;        // префикс внутри текущего сегмента
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        long long next_pref = pref + a[i];
        if (seen.count(next_pref - x)) {
            // вставляем день прямо перед a[i]
            ++ans;
            seen.clear();
            seen.insert(0);
            pref = a[i];       // новый сегмент начинается перед a[i]
            // гарантировано, что a[i] != x, значит конфликта тут не будет
            seen.insert(pref);
        } else {
            pref = next_pref;
            seen.insert(pref);
        }
    }

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

Пример из условия:

text
Ввод:
5 1
1000000 1000000 1000000 1000000 1000000

Вывод:
0

(ни один подотрезок не суммируется в 1, поэтому вставки не нужны).

Рассмотрим задачу подробно.

---

🧠 Формулировка задачи

Дан массив из n чисел a_1, a_2, ..., a_n и число x, которое Игорь ненавидит.
Нужно вставить минимальное количество чисел (в любое место), чтобы не было ни одного непустого подотрезка массива с суммой, равной x.

---

⚠️ Ограничения

• Вставленные числа могут быть любые.
• В массиве нет элементов, равных x.
• Нужно минимизировать количество вставок.

---

✅ Идея решения

1. Используем префиксные суммы.

2. Любой подотрезок с суммой x означает:

   prefix_sum[j] - prefix_sum[i-1] == x
   => prefix_sum[j] - x == prefix_sum[i-1]

3. То есть при добавлении нового элемента мы проверяем:

   существует ли уже такой префикс, что prefix_sum_now - x == existing_prefix
   Если да, значит есть подотрезок с суммой x.

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

---

🧩 Алгоритм

• Храним текущую префиксную сумму s.
• Храним множество seen из всех префиксов, встреченных в текущем сегменте.
• Если s - x ∈ seen, то вставляем новый элемент (считаем как новую секцию).
• Очищаем seen, начинаем отслеживать с текущего элемента.

---

💡 Пример на входе

text
5 4
-4 3 5 0 1

Пояснение:

• Префиксы: 0, -4, -1, 4, 4, 5
• На 4-м элементе (0): префикс = 4, а 4 - 4 = 0 — уже есть => вставка
• Ответ: 1

---

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

python
def min_insertions_to_avoid_sum_x(n, x, a):
    seen = set()
    seen.add(0)
    prefix = 0
    ans = 0

    for val in a:
        prefix += val
        if (prefix - x) in seen:
            # нужно вставить день, начинаем новый сегмент
            ans += 1
            seen = {0}
            prefix = val
            seen.add(prefix)
        else:
            seen.add(prefix)

    return ans

# Примеры
print(min_insertions_to_avoid_sum_x(5, 1, [1000000, 1000000, 1000000, 1000000, 1000000]))  # 0
print(min_insertions_to_avoid_sum_x(5, 4, [-4, 3, 5, 0, 1]))  # 1

---

📌 Вывод

Метод работает за $O(n)$ по времени и памяти.
Мы гарантированно получаем минимальное количество вставок, чтобы в массиве не было подотрезков с суммой x.

Хочешь — могу переписать решение на C++, Java или другом языке.

Вот полный код на C++, реализующий описанный алгоритм:

---

✅ Решение задачи на C++

cpp
#include <iostream>
#include <unordered_set>
using namespace std;

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

    int n;
    long long x;
    cin >> n >> x;

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

    unordered_set<long long> seen;
    seen.insert(0); // Префикс 0 в начале
    long long prefix = 0;
    int insertions = 0;

    for (int i = 0; i < n; ++i) {
        prefix += a[i];
        if (seen.count(prefix - x)) {
            // Найдена запрещённая сумма -> вставляем элемент
            ++insertions;
            seen.clear();
            seen.insert(0);
            prefix = a[i];  // начинаем с текущего элемента
            seen.insert(prefix);
        } else {
            seen.insert(prefix);
        }
    }

    cout << insertions << '\n';

    delete[] a;
    return 0;
}

---

📥 Пример входных данных

Ввод:

text
5 4
-4 3 5 0 1

Вывод:

1

---

📌 Пояснение

• Используется unordered_set для хранения префиксов в текущем сегменте.
• Как только возникает совпадение по префиксной сумме (то есть потенциальный подотрезок с суммой x), делается вставка и начинается новый сегмент.

---

Если нужно — могу переписать это в стиле class, или с пояснениями к каждому шагу.