A和B之间的数字计数(包括),其数字总和等于S.

Question

问题是找到A和B之间的数字计数(包括),其数字总和等于S.

同时在A和B之间打印最小的这个数字(含).

输入:

单线由A,B,S组成.

输出:

两行.

在第一行中,A和B之间的整数数,其总和等于S.

在第二行中,A和B之间的最小数字.

约束:

1 <= A <= B <10 ^ 15

1 <= S <= 135

来源:黑客地球

我的解决方案仅适用于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和B之间的值.

解决此问题的一般方法如下:

• 用数字和S计算小于或等于A-1的值的数量.
• 用数字和S计算小于或等于B的值的数量.
• 从第二个数字中减去第一个数字.

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

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

我们将创建一个表N [D,k,S]来保存这些值.我们知道D最多将是16,而S最多将是136,所以这个表只有10×16×136 = 21,760个条目,这也不算太糟糕.为了填写它,我们可以使用以下基本情况:

• 对于0≤S≤9,N [1,S,S] = 1,因为只有一个一位数字总和到小于10的任何值.
• 如果k≠S,则N [1,k,S] = 0,0≤S≤9,因为没有一位数字,其第一位数不是特定和,总和达到某个值.
• 对于10≤S≤135,N [1,k,S] = 0,因为对于任何大于单个数字的k,没有一位数总和精确为S.
• 对于任何S <0,N [1,k,S] = 0.

然后,我们可以使用以下逻辑来填写其他表条目:

• N [D + 1,k,S] = sum(i从0到9)N [D,i,S-k].

这表示总和为S的第一个数字为k的(D + 1) - 数字的数量由总和到S-k的D位数的数量给出.总和到S-k的D位数的数量由总和到S-k的D位数的数量给出,其第一个数字是0,1,2,...,9,所以我们有总结一下.

填写此DP表只需要时间O(1),事实上,如果您真的关心时间,可以想象它会预先计算并将其硬编码到程序中.

那我们怎么用这个表呢？好吧,假设我们想知道总和到S的数量是多少或等于某个数字X.为此,我们可以一次处理一个X的数字.让我们一次写一个X作为d ₁ ... d _n.我们可以从N [n,d ₁,S]开始.这给出了n位数的数字,其第一个数字是d ₁,总计为S.这可能高估了小于或等于X的值的数量,这些数值总和为S.例如,如果我们的数字是21,111并且我们想要总和精确到12的值的数量,然后查找这个表值将给出我们误差的数字,如29,100,以2开头,长度为5位,但仍然大于X.要处理这个,我们可以移动到数字X的下一个数字.由于第一个数字是2,数字中的其余数字必须总计为10.此外,由于X(21,111)的下一个数字是1,我们现在可以从总数中减去从2个,3个,4个,5个,...,9开始的4位数字的数量,加起来为10.我们可以一次重复这个过程一个数字.

更一般地,我们的算法如下.设X为我们的数字,S为目标总和.写X = d ₁ d ₂ ... d _n并计算以下内容:

# 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]

然后,值result将是小于或等于X的值的数量,其总和精确为S.此算法最多只运行16次迭代,因此它应该非常快.此外,使用此算法和较早的减法技巧,我们可以使用它来计算A和B之间有多少值总和到S.

用数字和S找到[A,B]中的最小值.

我们可以在我们的DP表中使用类似的技巧来找到大于A的数字的最小数字,该数字总和恰好是S.我将把细节留作练习,但作为提示,一次只能工作一个数字,试图找到DP表返回非零值的最小数字.

希望这可以帮助!