A和B（含）之间位数和等于S的数字计数

Question

问题是要找出A和B（包括A和B）之间的数字总数等于S。

同时打印A和B（含）之间的最小数字。

输入：

由A、B、S组成的单线。

输出：

两行。

在第一行中，A和B之间的整数数，其位数之和等于S。

在第二行中，A和B之间的最小数字。

约束：

1.

1.

来源：黑客地球

我的解决方案只适用于30%的输入。对此最好的解决方案是什么？

我现在使用的算法计算最小数字的和，然后在十位数的每次更改后再次计算和。以下是Python中的解决方案：

def sum(n):
    if (n<10):return n
    return n%10 + sum(n/10)

stri = raw_input()

min = 99999
stri = stri.split(" ")

a= long  (stri[0])
b= long  (stri[1])
s= long  (stri[2])

count= 0
su = sum(a)

while a<=b :        
if (a % 10 == 0 ):
    su = sum(a)
    print a 
if ( s == su):
    count+=1
    if (a<= min):
        min=a 
a+=1
su+=1
print count 
print min 

Answer 1

这里有两个独立的问题：在具有正确数字和的数字之间找到最小的数字，以及在具有该数字和的范围内找到值的数量。我将分别讨论这些问题。

解决这一问题的一般办法如下：

• 用数字和S计算小于或等于A-1的值的数目。

为此，我们应该能够使用动态编程方法。我们将尝试回答以下形式的查询：

有多少个D数字，第一个数字是k，其数字总和是S？

我们将创建一个表N[D，k，S]来保存这些值。我们知道D最多是16，S最多是136，所以这个表只有10×16×136=21760个条目，这并不太糟糕。要填写它，我们可以使用以下基本情况：

• N[1， S， S]=1表示0≤S≤9，因为只有一个一位数可以求和到小于10的任何值。
• N[1， k， S]=0表示0≤S≤9，如果k≠S，因为第一个数字不是特定总和的一位数没有求和到某个值。
• 对于10≤S≤135，N[1， k， S]=0，因为对于任何大于一位数的k，没有一位数的总和可以精确地等于S。
• N[1， k， S]=0对于任何S

然后，我们可以使用以下逻辑来填充其他表条目：

null

这就是说，第一个数字是k的（D 1）位数加起来等于S的是D位数加起来等于S k的个数。加起来等于S k的D位数加起来等于S k的D位数的个数是D位数加起来等于S k的个数，其第一个数字是0，1，2。。。，所以我们必须总结一下。

填写这个DP表只需要O（1）的时间，事实上，如果您真的关心时间，您可以想象您可以预先计算它并将其硬编码到程序中。

那么我们如何使用这张桌子呢？好吧，假设我们想知道有多少个和S相加的数字小于或等于某个数字X。要做到这一点，我们可以一次处理一个X的数字。让我们把X一次写一个数字，作为d_{1。。。dn。我们可以从N[N，d<1，S]开始。这为我们提供了n位数字的数量，其第一位数字为d，总计为S。这可能高估了总计为S的小于或等于X的值的数量。例如，如果我们的数字为21111，我们希望总计为12的值的数量，然后，查找此表值将为29100等数字提供误报，这些数字以2开头，长度为五位数，但仍大于X。要处理此问题，我们可以移动到数字X的下一位。由于第一位数字是2，因此数字中的其余数字总和必须为10。此外，由于X（21111）的下一个数字是1，我们现在可以从总数中减去从2、3、4、5开始的4位数。。。，9加起来就是10。然后我们可以一次重复一位数字的过程。}

一般来说，我们的算法如下。设X为我们的数字，S为目标和。写入X=d_{1d2。。。dn并计算以下各项：}

# Begin by starting with all numbers whose first digit is less than d[1].
# Those count as well.
result = 0
for i from 0 to d[1]:
    result += N[n, i, S]

# Now, exclude everything whose first digit is d[1] that is too large.
S -= d[1]
for i = 2 to n:
    for j = d[i] to 8:
        result -= N[n, d[i], S]
    S -= d[i]

然后，结果的值将是小于或等于X的值的数目，这些值的总和正好是S。该算法最多只能运行16次迭代，因此应该非常快。此外，使用此算法和早期的减法技巧，我们可以使用它来计算A和B之间的多少个值加起来正好是S。

我们可以对DP表使用类似的技巧来查找大于总和正好为S的数字的最小数字。我将把细节作为练习，但作为提示，一次工作一个数字，尝试查找DP表返回非零值的最小数字。

希望这有帮助！