1. # your code goes here
2. import re
3.
4. def find_n_nums(n):
5. very_big_number = 1e12
6.
7. min_sum = very_big_number
8. for i in range(1,23):
9. #print('looking for sum',i)
10. val = min_num_with_sum(i)
11. #print('starting from',val)
12. s = val
13. for _ in range(n-1):
14. val = next_num_with_sum(val)
15. #print(val,end=' ')
16. s += val
17. if s>very_big_number:
18. break
19. #print('digit sum',i,'number sum',s)
20. min_sum = min(min_sum,s)
21. return min_sum
22.
23. def min_num_with_sum(s):
24. if s<10:
25. return s
26. elif s<19:
27. return (s-9)*10+9
28. else:
29. return (s-18)*100+99
30.
31. def next_num_with_sum(v):
32. #print('want to find next to',v)
33. v = str(v)
34. #looking for 'XXXX9999X0000' pattern
35. match = re.search(r'9*\d?0*\$',v)
36. #print('match is',match)
37. v = [0]+[int(d) for d in v]
38. #print(v)
39. tail_len = len(match.group(0)) #at least 1
40. tail_sum = sum(v[-tail_len:]) - 1
41. #print('v',v,'tail sum=',tail_sum,end=' ')
42. v[-tail_len-1] += 1 #it is not 9
43. new_tail = [int(d) for d in str(min_num_with_sum(tail_sum))]
44. #print(new_tail)
45. new_tail = [0]*(tail_len-len(new_tail))+new_tail
46. #print('new_tail',new_tail)
47. v[-tail_len:] = new_tail
48. #print('v',v,int(''.join(str(d) for d in v)))
49. return int(''.join(str(d) for d in v))
50.
51. n = int(input())
52. print(find_n_nums(n))
53.
Success #stdin #stdout 0.81s 9728KB
stdin
5000
stdout
193969045