fork download
  1. import sys, time
  2.  
  3. def digdp(s):
  4. cn = len(s)
  5. dp = [[0,0] for z in range(9*cn+11)]
  6. dp[0][0] = 1
  7.  
  8. for i in range(cn):
  9. ndp = [[0,0] for z in range(9*cn+11)]
  10. for j in range(cn*9 + 1):
  11. for d in range(10):
  12. if j + d > cn*9: continue
  13. if d < int(s[i]): ndp[j+d][1] += dp[j][0]
  14. elif d == int(s[i]): ndp[j+d][0] += dp[j][0]
  15. ndp[j+d][1] += dp[j][1]
  16. dp = ndp
  17.  
  18. rtn = []
  19. for z in dp: rtn.append(z[0] + z[1])
  20. return rtn
  21.  
  22.  
  23. for line in sys.stdin:
  24. X, Y = line.split()
  25. X1 = str(int(X) - 1) # X-1
  26.  
  27. vx = digdp(X1) if X1 != '-1' else [0]
  28. vy = digdp(Y)
  29.  
  30. for i in range(len(vx)): vy[i] -= vx[i]
  31.  
  32. print( "{} {} --> {}".format(X, Y, max(vy)))
  33.  
Success #stdin #stdout 0.66s 9488KB
stdin
0 9999 
1234567 9876543 
1 500000000000
12345678909 498765432123
0 9223372036854775807
0 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
stdout
0 9999 --> 670
1234567 9876543 --> 459034
1 500000000000 --> 20406732610
12345678909 498765432123 --> 20000965162
0 9223372036854775807 --> 293347961657308060
0 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 --> 138681178063913146486663255108385891670476531416644888545033078503482282975641730091720919340564340