S*****B
发帖数: 404 | 1 Summing up the individual digits for each number from 0 to k(0<=k<=10000000)
, return how many times the most common sum occurs.
Examples: k=10 gives 2 (since 1 and 10 both sum up to 1) k=50 gives 6(since
5, 14, 23, 32, 41, 50 all sum up to 5).
因为要处理的数很大 所以肯定不能用循环来处理
我的思路是 找到最大的可能的数
比如50 最大的结果是49 -》4+9 =13
所以的出现的结果可能都是在1-13 的范围之内
分解这1-13的可能出现的结果并统计个数
又没有好的公式或者思路 比较卡壳了
或者其他的思路呢
谢谢各位大侠~ | h**6
发帖数: 4160 | 2 从0到9999999各位数之和的范围为0到63，显然32的出现次数最多。
具体次数，可以把1 1 1 1 1 1 1 1 1 1自卷积7次即可。 | d*******l
发帖数: 338 | 3 这种数字和的问题卷积确实非常好使，鉴于k不一定是10的整次方，具体做起来还要麻
烦一些。下面是一个python的实现：
def conv(a, b):
r = [];
n = len(a);
m = len(b);
a += [0] * m;
b += [0] * n;
for i in xrange(n+m):
t = 0;
for j in xrange(i+1):
t += a[j]*b[i-j];
r.append(t);
return r;
def sum(n):
ret = 0
while(n > 0):
ret += n % 10;
n /= 10;
return ret;
def addV(a, b):
l = min(len(a), len(b));
for i in xrange(l):
a[i] += b[i];
def solve(k):
res = [0] * 100;
n = k / 10;
s = sum(n);
for i in xrange(s, s+k%10+1):
res[i] = 1;
v = [1] * 10;
while(n):
d = n%10;
s = sum(n/10);
if d > 0:
addV(res, [0] * s + conv([1] * d, v));
v = conv(v, [1] * 10);
n /= 10;
mx = 0;
p = 0;
for i in xrange(100):
if res[i] > mx:
(p, mx) = (i, res[i]);
return (p, mx);
if __name__ == '__main__':
k = int(raw_input());
print solve(k); |
|
