fork download 
  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
comments (?)
stdin 
5000
stdout 
193969045
https://ideone.com/JtIJmu
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!