SPOJ-INUMBER（似乎无法在时限内开发解决方案） [英] SPOJ - INUMBER (Can't seem to develop a solution within the time limit)
问题描述
我正在尝试在SPOJ INUMBER 上解决此问题。
问题陈述如下：
I'm trying to solve this problem on SPOJ INUMBER.
Problem statement is as follows:
对于给定的数字 n 找出可除以 n 的最小正整数，其位数之和等于 n 。
For the given number n find the minimal positive integer divisable by n, with the sum of digits equal to n.
输入
t –测试用例数，然后是t个测试用例。 （t< = 50）
测试案例描述：
n -使得 0< n< = 1000
t – the number of test cases, then t test cases follow. (t <= 50)
Test case description:
n - integer such that 0 < n <= 1000
输出
对于每个测试用例输出
OUTPUT
For each test case output the required number (without leading zeros).
示例：
Input:
2
1
10
Output:
1
190
我只能想到一种蛮力解决方案，它从0-9逐位模拟数字并形成dfs结构并反复检查是否可以被n整除。
I can only think of a brute force solution emulating the number digit by digit from 0-9 and forming a dfs structure and repeatedly checking whether it's divisible by n or not.
在这里问我的问题之前，我在互联网上仔细搜索了这个问题，但没有找到任何详细的解释。他们中的大多数都是未记录的原始代码，而其他人只是提供了解决方案的一个参考。
我真的很想解决这个问题，不仅是要点，而且是要学习一些新知识。
Before asking my question here, I did a meticulous search on this problem on the internet and couldn't found any detailed explanation. Most of them were undocumented raw code and others were giving just a jist of the solution.
I'm really interested in solving this problem not just for the points but to learn something new.
感谢帮助Stackoverflow社区：）
Thanks for the help Stackoverflow community :)
推荐答案
您可以
让 num（p，q）是具有位数总和的最小位数 p ，其余模数 n 等于 q 。
Let num(p, q) be the minimum number of digits with digit sum p and remainder mod n equal to q.
我们想找到 num（n，0）。然后，我们可以贪婪地构建最小的数字。
We want to find num(n, 0). Then, we can greedily build the smallest such number.
我们从状态（0，0）开始。从状态（x，y）可以进入状态：
We start from the state (0, 0). From a state (x, y) you can get to a state:
(x + j, (y * 10 + j) % n)
每个数字 j 。
保持跟踪添加的每个数字 j 然后从（n，0）回溯到（0，0）。
Keep track of each digit j you add and then backtrack from (n, 0) to (0, 0).
有一些实现细节需要弄清楚。如果遇到困难，我会在网上找到一些实现：在topcoder上和在github 。
There are some implementation details to figure out. If you get stuck, I have found some implementations online: on topcoder and on github.
这篇关于SPOJ-INUMBER（似乎无法在时限内开发解决方案）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
