Перебор целых корней в фиксированном окне — задача «Кубическое уравнение» РАЗБОР

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

Эта задача — лабораторный стенд для всего перечисленного. Условие совсем простое: дано кубическое уравнение, найти его целые корни. Гарантия, что они лежат в окне $[-100, 100]$, превращает поиск в прямой перебор — мы просто пробуем каждое целое $x$ из окна и проверяем, обращается ли многочлен в ноль.

Звучит как «два цикла назад в учебнике». Но именно на ней удобно проговорить: какой цикл правильный, как корректно организовать условие, и почему int в C++ здесь — мина замедленного действия.

---

Что дано

Дано кубическое уравнение

$$A \cdot x^3 + B \cdot x^2 + C \cdot x + D = 0,$$

где $A, B, C, D$ — целые коэффициенты, $A \ne 0$. Гарантируется, что все целые корни уравнения лежат в диапазоне $[-100, 100]$. У уравнения могут быть и нецелые корни — их искать не нужно.

Требуется вывести все целые корни в порядке возрастания.

Ограничения

• $A \ne 0$
• $|A|, |B|, |C|, |D| \leq 32\,768$
• Все целые корни уравнения находятся в $[-100, 100]$.

Формат ввода

Четыре целых числа $A$, $B$, $C$, $D$ в одной строке (или раздельно — стандартный split по пробелам).

Формат вывода

Целые корни уравнения в порядке возрастания, через пробел.

Пример 1

Вход:

1 -3 0 0

Выход:

0 3

Уравнение: $x^3 - 3x^2 = x^2(x-3) = 0$. Корни: $x = 0$ (двойной) и $x = 3$. Целые различные значения корней — $0$ и $3$.

Пример 2

Вход:

3 -15 18 0

Выход:

0 2 3

Уравнение: $3x^3 - 15x^2 + 18x = 3x(x-2)(x-3) = 0$. Корни: $0, 2, 3$.

Пример 3

Вход:

1 -7 -33 135

Выход:

-5 3 9

Уравнение: $(x+5)(x-3)(x-9) = x^3 - 7x^2 - 33x + 135 = 0$. Корни: $-5, 3, 9$.

Разберём первый пример руками

$A=1, B=-3, C=0, D=0$. Многочлен — $f(x) = x^3 - 3x^2$.

Пробежим $x$ от $-100$ до $100$ и подставим. Для краткости — только окрестность нуля:

Все остальные $x$ из окна — $f(x) \ne 0$ (кубический рост за пределами малых значений). Двойной корень в нуле даёт одно значение в выводе: $0$. Дублей нет, потому что мы перебираем $x$ один раз.

Отсюда ровно та идея, к которой задача нас и подталкивает.

---

Идея решения

Алгоритм в одну фразу.

Прямой перебор: для каждого $x \in [-100, 100]$ вычисляем $f(x) = A x^3 + B x^2 + C x + D$ и собираем те $x$, где $f(x) = 0$.

Почему это работает

Корни — целые, по условию лежат в окне $[-100, 100]$. Окно содержит $201$ значение. Один проход — $O(N)$ итераций при $N = 201$, на каждой — арифметика за $O(1)$. Итого — $\approx 200$ операций умножения и сложения. Уложится в любой лимит времени с гигантским запасом.

Перебор по убыванию или возрастанию выбирается так, чтобы итог уже был в требуемом порядке вывода — здесь это возрастание, значит $x$ идёт от $-100$ до $100$. Сортировать ничего не нужно: естественный порядок цикла совпадает с порядком вывода.

Дубли (двойные/тройные корни) автоматически отсекаются — мы перебираем каждое $x$ один раз. Если $f(x) = 0$ имеет $x_0$ корнем кратности 2, мы добавим $x_0$ в ответ ровно один раз.

Альтернативы и почему они здесь не нужны

• Решение по формуле Кардано — даёт все три комплексных корня, но из них надо ещё вытаскивать целые с проверкой точности. Лишняя возня.
• Поиск делителей $D$ — теорема о рациональных корнях говорит, что любой целый корень делит свободный член $D$. Это даёт перебор по $\le \sigma_0(|D|)$ кандидатам (количество делителей $D$), что обычно сильно меньше 201. Но: код становится длиннее (ищем все делители $D$, плюс пробуем $0$, плюс знаки), а выигрыш по времени для $|D| \le 32\,768$ практически нулевой. Прямой перебор окна проще и надёжнее.

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

---

Решение: псевдокод

прочитать A, B, C, D
roots ← пустой список
для x от -100 до 100 (включая обе границы):
    значение ← A * x^3 + B * x^2 + C * x + D
    если значение = 0:
        добавить x в roots
вывести элементы roots через пробел

Сложность: $O(N)$ по времени, где $N = 201$. По памяти — $O(R)$, где $R \le 7$ (кубическое уравнение имеет не более 3 различных корней; запас — на всякий случай).

---

Код решения

Переключи вкладку, чтобы посмотреть второй язык. Главная разница: в Python int бесконечной точности, переполнения нет. В C++ обязателен long long для всего — иначе промежуточное произведение A * x * x * x при $|A| = 32\,768$, $|x| = 100$ даёт $\approx 3.27 \cdot 10^{10}$, что выходит за int32 ($\approx 2.15 \cdot 10^9$); после переполнения значение может стать любым, иногда даже случайно нулём — получим ложный «корень».

Комментарии по реализации.

• Границы цикла. В Python range(-100, 101) — правая граница исключающая, поэтому 101, чтобы $x = 100$ тоже попал. В C++ for (int x = -100; x <= 100; ++x) — <=, чтобы не потерять $x = 100$. Типичная ловушка с обеих сторон.
• Чтение в long long (C++). Чтение long long A, B, C, D сразу снимает проблему переполнения: все промежуточные произведения автоматически в 64-битном типе. Альтернатива — читать в int и писать (long long)A * x * x * x — работает, но один пропущенный кастинг и снова получим WA.
• Возведение в степень. Python — x ** 3, целочисленное возведение, читается как формула. C++ — x * x * x напрямую (или $xx \cdot x$, переиспользуя $x^2$).
• Чтение ввода. Python — sys.stdin.read().split() парсит весь ввод сразу; работает и когда $A, B, C, D$ через пробел, и когда каждое на своей строке. C++ — cin >> A >> B >> C >> D с sync_with_stdio(false).
• Мелкая оптимизация (C++). xx = (long long)x * x — считаем $x^2$ один раз и переиспользуем для $x^3 = x^2 \cdot x$ и $B x^2$. Для $N = 201$ выигрыш эстетический, но привычка окупается на больших объёмах.
• Вывод. Через пробел, в одну строку, без trailing-пробела. Финальный '\n' для аккуратности.

---

Проверим на всех примерах из условия

Пример 1: $A=1, B=-3, C=0, D=0$ → ожидание 0 3

Многочлен $f(x) = x^3 - 3x^2$. Перебираем $x \in [-100, 100]$.

• $f(-1) = -1 - 3 = -4$
• $f(0) = 0$ → добавили $0$
• $f(1) = 1 - 3 = -2$
• $f(2) = 8 - 12 = -4$
• $f(3) = 27 - 27 = 0$ → добавили $3$
• $f(4) = 64 - 48 = 16$ — для $x \ge 4$ многочлен растёт ($x^2(x-3) > 0$), нулей не будет.
• $f(-2) = -8 - 12 = -20$ — для $x \le -1$ $x^2$ всегда $\ge 1$, $x - 3 \le -4$, произведение $\le -4$, нулей не будет.

Собранные корни: $[0, 3]$. Ответ: 0 3 ✓.

Пример 2: $A=3, B=-15, C=18, D=0$ → ожидание 0 2 3

Многочлен $f(x) = 3x^3 - 15x^2 + 18x = 3x(x-2)(x-3)$.

• $f(-1) = -3 - 15 - 18 = -36$
• $f(0) = 0$ → добавили $0$
• $f(1) = 3 - 15 + 18 = 6$
• $f(2) = 24 - 60 + 36 = 0$ → добавили $2$
• $f(3) = 81 - 135 + 54 = 0$ → добавили $3$
• $f(4) = 192 - 240 + 72 = 24$ — для $x \ge 4$ многочлен растёт.

Собранные корни: $[0, 2, 3]$. Ответ: 0 2 3 ✓.

Пример 3: $A=1, B=-7, C=-33, D=135$ → ожидание -5 3 9

Многочлен $f(x) = x^3 - 7x^2 - 33x + 135 = (x+5)(x-3)(x-9)$.

• $f(-5) = -125 - 175 + 165 + 135 = 0$ → добавили $-5$
• $f(0) = 135$
• $f(3) = 27 - 63 - 99 + 135 = 0$ → добавили $3$
• $f(9) = 729 - 567 - 297 + 135 = 0$ → добавили $9$
• $f(8) = 512 - 448 - 264 + 135 = -65$
• $f(10) = 1000 - 700 - 330 + 135 = 105$
• $f(-6) = -216 - 252 + 198 + 135 = -135$
• Между ${-5, 3, 9}$ функция действительно меняет знак на каждом корне (как и должно быть для кубики с тремя различными вещественными корнями).

Собранные корни: $[-5, 3, 9]$. Ответ: -5 3 9 ✓.

Все три примера дают эталонные ответы. Код корректен.

---

Крайние случаи, на которых можно споткнуться

1. Граница окна: $x = -100$ и $x = 100$ должны попасть в перебор

В Python: range(-100, 101) — правая граница исключающая. Если написать range(-100, 100), потеряем $x = 100$.

В C++: for (int x = -100; x <= 100; ++x) — <=, не <. Если написать <, потеряем $x = 100$.

Цена ошибки — потеря одного из крайних корней. Тесты обычно содержат пример с граничным корнем, поэтому ошибка ловится сразу — но только если тест включает $x = -100$ или $x = 100$.

2. Переполнение int в C++

При $|A| = 32\,768$ и $|x| = 100$:

$$|A \cdot x^3| = 32\,768 \cdot 10^6 = 3.276 \cdot 10^{10},$$

а максимум int32 — $2^{31} - 1 \approx 2.147 \cdot 10^9$. Превышение в 15 раз. После переполнения значение может стать любым — например, случайно 0, и алгоритм добавит ложный корень.

Решение: читать $A, B, C, D$ в long long, тогда все промежуточные произведения автоматически в 64-битной арифметике. Запас — long long выдерживает до $9.2 \cdot 10^{18}$, что в $2.8 \cdot 10^8$ раз больше нашего максимума.

В Python такой проблемы нет — int без границ.

3. Кратные корни

$f(x) = (x - 2)^3 = x^3 - 6x^2 + 12x - 8$ имеет тройной корень $x = 2$. Наш цикл проверяет $x = 2$ один раз и добавляет в ответ один раз. Это совпадает с форматом вывода («целые корни в порядке возрастания» — каждый раз указанный одним числом).

Если бы задача требовала «корни с кратностями» — пришлось бы дополнительно искать кратность каждого найденного корня (например, делить многочлен на $(x - r)$ и снова искать корни). Здесь этого не нужно.

4. Нет целых корней в окне

Условие гарантирует, что если целые корни есть, они в $[-100, 100]$. Но не гарантирует, что они вообще существуют. Например, $x^3 - 2 = 0$: единственный вещественный корень $x = \sqrt[3]{2} \approx 1.26$ — не целый, целых корней нет вообще.

В таком случае roots остаётся пустым, и мы выводим пустую строку (или сразу \n). Это допустимый ответ для acmp; формат «корней нет — пустой вывод» естественно вытекает из формата «корни через пробел» при пустом списке.

5. $D = 0$

Уравнение становится $A x^3 + B x^2 + C x = x(A x^2 + B x + C) = 0$, где $x = 0$ всегда корень. Наш цикл найдёт $x = 0$ автоматически, плюс возможные корни квадратного множителя — без специальной обработки.

6. Линейное / квадратное вырождение?

Условие гарантирует $A \ne 0$, поэтому уравнение всегда строго кубическое. Случаи $A = 0, B \ne 0$ (квадратное) или $A = B = 0, C \ne 0$ (линейное) исключены — обрабатывать их не нужно.

---

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

1. Off-by-one на правой границе цикла. range(-100, 100) или for (x = -100; x < 100; ++x) — теряет корень $x = 100$. На тестах с граничным корнем — мгновенный WA. Запоминать как мускульную память: «правая граница — +1 в range, <= в C++».
2. int вместо long long в C++. Переполнение даёт случайные значения и ложные корни. Самая частая ошибка на этой задаче — даже у опытных участников; ловится анализом «какой максимум промежуточного произведения?». На каждой задаче с произведениями нескольких чисел этот анализ — обязательный шаг.
3. Сортировка roots.sort() после цикла. Не вредит, но избыточно: цикл уже идёт в возрастающем порядке. Лишняя строка кода — лишний шанс что-то сломать (например, случайно отсортировать по модулю).
4. Поиск нецелых корней. Если попытаться вместо целочисленного перебора применить, например, метод Ньютона — найдутся вещественные корни, и придётся их дополнительно фильтровать, проверяя «целое или нет» с заданной точностью. Здесь это лишняя работа: задача требует только целые, и они гарантированно в окне.
5. Чтение через scanf("%d") или cin >> int_var с последующим хранением в int, а потом (long long) каст внутри произведения. Технически работает, если каст не забыт ни в одном месте. Практически — рано или поздно один каст забывается. Безопаснее объявить переменные сразу как long long.
6. Печать roots через перевод строки вместо пробела. Формат вывода — через пробел в одной строке. На acmp проверка обычно строгая по формату. print(*roots) в Python даёт правильный формат через пробел; print('\n'.join(map(str, roots))) — нет.
7. Деление вместо равенства. Иногда участники проверяют корень условием A * x**3 + B * x**2 + C * x + D == 0 через деление многочлена на $(x - r)$ и проверку остатка. Для прямого перебора это лишнее — достаточно сравнить значение с нулём напрямую.

---

Анализ сложности

• Время: $O(N)$, где $N = 201$. На каждой итерации — $O(1)$ арифметика. Итог — около 200 умножений и сложений, время ничтожное.
• Память: $O(R)$, где $R$ — количество найденных корней, $R \le 3$. Можно вообще обойтись без массива и печатать корни по ходу цикла, но накопление в roots чище — отделяет вычисление от форматирования вывода.

---

Что ещё полезно потренировать

Задачи на простой перебор кандидатов с проверкой за $O(1)$. Все — с возраст-нейтральных платформ.

• Codeforces Div.4 / Div.3 уровень 800–1100, тег brute force + implementation — типичные задачи «перебери все $x$ из небольшого окна, проверь условие». На начальном этапе — десятки одинаковых паттернов, отличающихся только формой условия.
• acmp.ru, раздел «Простые задачи» — «Делители числа», «Простые числа в диапазоне», «Совершенные числа» — все построены на той же конструкции: цикл по окну + проверка свойства внутри.
• Яндекс Контест: тренировки по основам алгоритмов — открытые подборки начального уровня содержат целый кластер «перебор + проверка», полезный для отработки техники до автоматизма.

Следующий шаг — задачи, где прямой перебор уже не помещается в лимит, и на смену приходит более экономичный обход (бинпоиск по ответу, два указателя, префиксные суммы). Этим темам посвящены следующие посты в серии «Алгоритмические основы» — они закрывают переход «перебор → структура данных».

---

Итого

• Идея: прямой перебор $x \in [-100, 100]$, проверка $f(x) = 0$ за $O(1)$.
• Сложность: $O(N)$ по времени, $N = 201$. По памяти — $O(R)$, $R \le 3$.
• Главная ловушка: переполнение int в C++ при $A \cdot x^3$. Решение — long long для всех коэффициентов и промежуточных произведений.
• Вторая ловушка: off-by-one на правой границе цикла. range(-100, 101) в Python, x <= 100 в C++.
• Корни выводятся в естественном порядке возрастания, потому что цикл идёт от $-100$ к $100$ — сортировка не нужна.