Задача по числам

Подскажите идею решения.
Для заданного N (N<=1000) найти минимальное целое положительное число, которое делится на N, и сумма его цифр равна N.

длину перебираешь.

для генерации требуемого n-значного числа (слева направо генерация), используешь динамическое программирование. состояние - пара (сколько цифр уже сгенерировано, текущий остаток).

(сколько цифр уже сгенерировано, текущий остаток).

еще сумму сгенерированных цифр

еще сумму сгенерированных цифр

хотя не... число сгенерированных цифр - не надо в состояние, а то сильно много. Пусть это будет результат динамики, т.е. решай задачу (сумма цифр, остаток по модулю N) -> минимально возможное число цифр в таком числе.

А какие рекуррентные соотоношения будут? Т.е. как будут связаны между собой эти состояния?

А какие рекуррентные соотоношения будут? Т.е. как будут связаны между собой эти состояния?

f[s, m] = 1 + \min_{0<=d<=9, d>=s} f[s-d, (10m+d)%N]

s - сумма цифр
m - модуль (- сгенерированная часть цифр слева имеет этот остаток, и требуется приписать цифры справа, чтобы свести его к нулюю

[quote=гость;12622]f[s, m] = 1 + \min_{0<=d<=9, d>=s} f[s-d, (10m+d)%N]
а с нулём беда, да... давай так: отдельно перебирай сколько нулей приписывать (больше 10 нет смысла), и затем цифру от d=1..9 по формуле выше.

Спасибо за советы. Попробую реализовать.