BFS по состоянию (mod d, сумма цифр) — задача «Find a Number» РАЗБОР

Что дано

Дано два целых числа $d$ и $s$. Нужно найти наименьшее положительное целое число $N$, удовлетворяющее одновременно двум условиям:

1. $N$ делится нацело на $d$.
2. Сумма десятичных цифр $N$ равна ровно $s$.

Если такого числа не существует, нужно вывести $-1$.

Ограничения

• $1 \le d \le 500$.
• $1 \le s \le 5000$.
• Время — 1 секунда, память — 256 МБ.

«Наименьшее» здесь означает наименьшее значение — то есть сначала наименьшая длина (число цифр), а среди чисел одинаковой длины — наименьшее в лексикографическом порядке.

Формат ввода

В одной строке два целых числа $d$ и $s$.

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

Одна строка: либо искомое число $N$ (без ведущих нулей), либо $-1$, если такого числа нет.

Пример 1

Вход:

13 50

Вывод:

699998

Комментарий: $6 + 9 + 9 + 9 + 9 + 8 = 50$, и $699998 = 13 \cdot 53846$.

Пример 2

Вход:

61 2

Вывод:

1000000000000000000000000000001

Комментарий: число длины $31$, состоит из двух единиц и двадцати девяти нулей; сумма цифр $2$; делится на $61$. Более коротких чисел с суммой цифр $2$, делящихся на $61$, не существует.

Пример 3

Вход:

15 50

Вывод:

-1

Комментарий: $15 = 3 \cdot 5$. Для делимости на $5$ последняя цифра должна быть $0$ или $5$. Для делимости на $3$ сумма цифр должна делиться на $3$. $50$ не делится на $3$ — значит, требуется одновременно сумма цифр $50$ и кратность $3$, что невозможно. Ответ — $-1$.

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

Сумма цифр $50$ — это много. Минимальная длина числа с такой суммой цифр — $\lceil 50 / 9 \rceil = 6$ (если все цифры по $9$, получим $54$, надо немного снизить). Например, $999995$ имеет сумму $50$, но $999995 / 13 = 76922.69\ldots$ — не делится. Среди шестизначных чисел с суммой цифр $50$ нужно найти минимальное, делящееся на $13$.

Лобовой перебор всех шестизначных чисел — $9 \cdot 10^5 = 900\,000$ кандидатов. Для каждого надо посчитать сумму цифр (8 операций) и проверить делимость. Это $7$ миллионов операций — быстро. Но при $s = 5000$ длина числа может быть $\lceil 5000 / 9 \rceil \approx 556$, и перебор шестисотзначных чисел нереалистичен.

Идея: строить число по одной цифре слева направо, и держать в состоянии только то, что нам нужно для проверки финальных условий — текущий остаток по модулю $d$ и накопленную сумму цифр. Тогда конечное число — это путь в графе состояний от стартового $(0, 0)$ до целевого $(0, s)$, и нам нужен кратчайший такой путь, среди равных — лексикографически минимальный.

---

Идея решения

Состояние: пара $(r, c)$ — текущий остаток по модулю $d$ и сумма уже приписанных цифр. Стартовое состояние — $(0, 0)$ (пустое число), целевое — $(0, s)$ (число с остатком $0$ при делении на $d$ и суммой цифр ровно $s$).

Из состояния $(r, c)$ есть до $10$ переходов: приписать цифру $\delta \in \{0, 1, \ldots, 9\}$, перейти в $(r', c')$, где

$$r' = (10 \cdot r + \delta) \bmod d, \qquad c' = c + \delta.$$

Переход в $(r', c')$ возможен, если $c + \delta \le s$ (мы не должны перебрать сумму). Длина пути от $(0, 0)$ до конечного состояния — это число цифр $N$.

Хотим минимальное число: сначала минимальная длина, затем минимальная лексикографически. Идеальный инструмент — BFS: он гарантирует, что в момент первого попадания в каждое состояние мы пришли по кратчайшему пути.

Хитрость с лексикографической минимальностью: если при обходе очередного слоя BFS перебирать переходы в порядке цифр $\delta = 0, 1, \ldots, 9$, то первое попадание в каждое состояние будет через цифру с минимальным значением. Однако нам нужно лексикографически минимальное число, а не минимальное по последней цифре. BFS сам по себе этого не даёт: к одному и тому же состоянию могут вести разные слова разной структуры.

Спасает симметрия задачи. Заметим: на состояние «след внутри числа» влияет только сумма приписанных цифр и текущий остаток. Если в одну и ту же $(r', c')$ можно прийти из двух разных предков через цифры $\delta_1 < \delta_2$, то стоит выбрать тот переход, который ведёт к меньшему числу — а это переход с меньшей цифрой на текущей позиции, при условии, что префикс предка тоже минимален.

Формально это решается так: при BFS храним для каждого состояния parent[(r', c')] = ((r, c), δ). Если состояние посещаем впервые — записываем. Поскольку BFS гарантирует кратчайший путь, а слой выходит из меньшей цифры раньше большей, первое попадание даёт минимальный путь.

Здесь важно одно тонкое условие: первая цифра $N$ не должна быть нулём. Поэтому стартовые переходы из $(0, 0)$ перебираем по $\delta = 1, 2, \ldots, 9$ (не от $0$), а из остальных состояний — по $\delta = 0, 1, \ldots, 9$.

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

Кратчайший путь. BFS на любом графе с единичными весами находит кратчайший путь по числу рёбер. У нас каждое ребро добавляет одну цифру, то есть увеличивает длину числа на $1$. Значит, кратчайший путь от $(0, 0)$ до $(0, s)$ — это минимальная длина числа $N$.

Лексикографически минимальное среди кратчайших. Внутри одного слоя BFS перебираем переходы в порядке возрастания $\delta$. Когда новое состояние $(r', c')$ попадается в первый раз, мы пришли:

• либо из самого «раннего» предка (минимальный путь в предка по конструкции BFS),
• либо через минимальную возможную цифру среди равных предков-кандидатов (потому что перебор отсортирован).

Здесь полезно мысленно представить рекурсивный аргумент: путь в $(r', c')$ — это путь в предка $(r, c)$ + цифра $\delta$. Среди всех таких пар (длина пути в предка $=$ оптимум) минимальное число лексикографически — это путь с минимальным $\delta$ при тех же предках; при разных предках с одинаковой длиной — выбор предка, в котором префикс минимален. BFS обходит вершины по слоям, поэтому когда мы посещаем $(r', c')$ из $(r, c)$ в момент времени $t$, состояние $(r, c)$ уже было посещено раньше (в момент $t - 1$), и его parent фиксирован. Перебор по $\delta$ от $0$ к $9$ внутри слоя обеспечивает, что среди всех путей одинаковой длины выбран минимальный лексикографически.

Условие первой цифры. Из стартового состояния первый шаг — цифра, которая станет старшим разрядом числа. Если разрешить $\delta = 0$, путь будет описывать число с ведущим нулём — не валидно. Поэтому первый шаг — только $\delta \ge 1$.

Размер графа состояний

Состояний $(r, c)$ всего $d \cdot (s + 1) \le 500 \cdot 5001 = 2\,500\,500$. Рёбер — до $10 \cdot$ числа состояний, то есть $\approx 2.5 \cdot 10^7$. BFS с такой сложностью укладывается в секунду по времени; по памяти — $O(d \cdot s)$ массив парентов и посещённости.

---

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

visited[d][s+1] = false
parent[d][s+1] = (prev_state, digit)
visited[0][0] = true
очередь ← [(0, 0)]

пока очередь не пуста:
    (r, c) ← взять из очереди
    если (r, c) = (0, s):
        // дошли до цели; реконструкция ниже
        break
    начало = 1 если (r, c) = (0, 0) иначе 0       // запрет ведущего нуля
    для δ от начало до 9:
        если c + δ > s: continue
        r' ← (10 * r + δ) mod d
        c' ← c + δ
        если visited[r'][c']:
            continue
        visited[r'][c'] = true
        parent[r'][c'] = ((r, c), δ)
        очередь.добавить((r', c'))

если не visited[0][s]:
    вывести -1
иначе:
    реконструировать строку цифр от (0, 0) к (0, s) через parent
    вывести строку

Сложность: $O(d \cdot s \cdot 10) = O(d \cdot s)$.

---

Код решения

Различия между языками здесь сводятся к двум деталям: в C++ нужно аккуратно работать с памятью под массивы парентов размера $d \cdot s$, в Python — следить, чтобы реконструкция через список не делала $O(n^2)$ конкатенаций строк.

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

• Тип под произведение. В вычислении r * 10 + delta максимальное $r \le d - 1 \le 499$, поэтому $r \cdot 10 + \delta \le 4999$ — int хватает в обоих языках, переполнения нет.
• break вместо continue при nc > s. Внутри цикла по $\delta$ от меньших к большим, как только c + delta > s, дальше тем более не подойдёт. Это микро-оптимизация, но при $s$ близком к нулю и больших $d$ заметно ускоряет.
• Память под parent в C++. Линейный массив int размера $d \cdot (s + 1) \le 2.5 \cdot 10^6$ — это $10$ МБ под par_r и столько же под par_c. Для par_digit используем char (1 байт), экономим. В сумме укладываемся в лимит памяти.
• Реконструкция в Python. Собираем цифры в list, после цикла делаем reverse() и "".join(...) — это $O(n)$. Конкатенация s = digit + s в цикле дала бы $O(n^2)$ — на ответе длины $5000$ это $25 \cdot 10^6$ операций над строками, медленно.
• Особый случай $s = 0$. В оригинальных ограничениях $s \ge 1$, но код всё равно обрабатывает: при $s = 0$ единственное «число» с суммой цифр $0$ — это $0$, но оно не положительное. Возвращаем $-1$.

---

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

Пример 1: $d = 13$, $s = 50$

Целевое состояние — $(0, 50)$. Длина пути в BFS до этого состояния — $6$ (минимум по слоям). Восстановление пути от $(0, 50)$ к $(0, 0)$ даёт цифры $8, 9, 9, 9, 9, 6$ (читаем от последней к первой), после реверса — $6, 9, 9, 9, 9, 8$, то есть $699998$. Проверяем:

• $6 + 9 + 9 + 9 + 9 + 8 = 50$ ✓
• $699998 \bmod 13$: $699998 = 13 \cdot 53846 + 0$, остаток $0$ ✓

Ответ: $699998$ ✓

Пример 2: $d = 61$, $s = 2$

Длина — $31$. BFS обнаруживает: из $(0, 0)$ можно пойти в $(1, 1)$ через цифру $1$ (но дальше нужно ещё $1$ для суммы $2$, и достичь остатка $0$ при основе $10^k \bmod 61$). $10^k \bmod 61$ периодично; первый раз $10^k \equiv 60 \pmod{61}$ при $k$ таком, что $10^k + 1 \equiv 0$. Этот $k = 30$, поэтому длина пути $30 + 1 = 31$, число $\underbrace{1\,0\,0\ldots\,0}_{29 \text{ нулей}}\,1$.

Ответ: $1\underbrace{0\ldots 0}_{29}1$ (31 цифра) ✓

Пример 3: $d = 15$, $s = 50$

$15 = 3 \cdot 5$. Делимость на $3$ — сумма цифр должна делиться на $3$. $50 \bmod 3 = 2 \ne 0$. Значит, целевое состояние $(0, 50)$ недостижимо: для любого числа, делящегося на $3$, сумма цифр кратна $3$. BFS обходит все достижимые состояния и не находит $(0, 50)$.

Ответ: $-1$ ✓

---

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

1. Делитель $d = 1$

Делятся на $1$ все числа. Тогда задача сводится к «найти минимальное число с суммой цифр $s$». BFS аккуратно даёт минимум: цифр $\lceil s / 9 \rceil$, конкретнее — $s - 9 \cdot (\lceil s / 9 \rceil - 1)$ старшая цифра, дальше всё девятки.

2. Сумма $s = 1$

Минимальное число с суммой цифр $1$ — это $10^k$ для некоторого $k$. Конкретное $k$ — минимальное такое, что $10^k \equiv 0 \pmod d$. Для $d$, у которого в разложении только $2$ и $5$ — такое $k$ существует. Иначе ответа нет (например, $d = 3$ → ответ $-1$).

3. Маленькие $d$ при большом $s$

$d \le 500$, $s$ до $5000$. Состояний — $2.5 \cdot 10^6$. Очередь BFS работает быстро; реконструкция — линейна по ответу (до $5000$ цифр). Никаких проблем со временем.

4. Состояние $(0, s)$ совпадает с $(0, 0)$

Только при $s = 0$, что не входит в ограничения. На всякий случай в коде явно отрабатываем это через проверку.

5. Длина ответа очень большая

При $s$ близком к $5000$ длина ответа может быть до $5000$ цифр. Печать через "\n" в конце; в Python — одна sys.stdout.write за весь вывод (не построчная печать в цикле); в C++ — стандартная << строки.

---

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

1. Разрешённая ведущая цифра $0$. Если из $(0, 0)$ перебирать $\delta = 0$, в очередь попадёт $(0, 0)$ повторно (или сразу будет помечено как посещённое). Безобидно для BFS, но если случайно разрешить, ответ может начаться с нуля. Проверять явно в коде стартовое условие.
2. Кэширование через dict в Python. На $2.5 \cdot 10^6$ состояний dict работает в 5–8 раз медленнее list[list[...]]. На пограничных тестах даёт TL. Двумерный массив фиксированного размера — обязательно.
3. Реконструкция в неверном порядке. Идём от конца к началу, собираем цифры. Если забыть reverse() — выведем перевёрнутое число.
4. Очередь BFS на list в Python. list.pop(0) — $O(n)$. На $2.5 \cdot 10^6$ операций это $O(n^2)$ — миллиарды операций. Только collections.deque.
5. Хранение пути в состоянии BFS. Соблазн положить в очередь не $(r, c)$, а $(r, c, \text{строка цифр пока})$. Это убивает память ($O(n)$ строк длины до $n$ = $O(n^2)$ = $25 \cdot 10^6$ символов в худшем случае, и каждая копия строки требует выделения). Только индексы — parent отдельно.
6. Несимметричный учёт «первой цифры». Если start = 1 применяется только к одной ветке кода, но не ко второй — где-то проскочит ноль. Проверка (r == 0 && c == 0) должна стоять прямо в основном цикле.
7. Переполнение в C++ при индексации. $d \cdot (s + 1) \le 500 \cdot 5001 \approx 2.5 \cdot 10^6$. int хватает, переполнения нет, но vector<int> такого размера — это $10$ МБ. В стеке нельзя — только в куче.

---

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

• Время: $O(d \cdot s)$ — каждое состояние посещается один раз; из каждого — до $10$ переходов; всего $\le 2.5 \cdot 10^7$ элементарных операций.
• Память: $O(d \cdot s)$ под visited, parent. Очередь BFS в худшем случае — все состояния, тоже $O(d \cdot s)$.
• Длина выходной строки: до $s$ цифр (когда все цифры — единицы) или до $\lceil s / 9 \rceil$ при «оптимальной» структуре. На печать уходит $O(\text{длина ответа})$ операций.

---

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

• Codeforces 1801A «The Very Beautiful Blanket» — конструктивная задача на свойство $a \oplus b$, тренирует «строить ответ по позициям», как и наша «строить число по разрядам».
• Codeforces 1495D «BFS Trees» — BFS-обход графа с восстановлением путей, та же техника «отдельные массивы под parent» в чистом виде.
• Codeforces 1244C «The Football Season» — поиск решения линейного уравнения в малых числах, похожий шаблон «состояние компактно, перебор по дополнительной оси».
• acmp.ru задача 191 «Гирлянда» — DP с двумерным состоянием на сетке, шаблон «состояние полностью описывает оставшуюся задачу».

---

Итого

• Идея: BFS в графе состояний $(r, c)$ — остаток по модулю $d$ и накопленная сумма цифр; переход — добавление цифры; восстановление числа из массива parent.
• Сложность: $O(d \cdot s)$ время и память.
• Ловушки: запрет ведущего нуля, очередь — только deque, кэш — только массив, не dict; реконструкция — собрать цифры, потом reverse.