fork download
copy 
  1. def solve(n):
  2. 	# print "solve(%d)" % n
  3. 	if n == 0:
  4. 		return -1
  5. 	if n == 1:
  6. 		return 1
  7. 	dp = [0] * n
  8. 	i = 0
  9.  
  10. 	while dp[0] == 0:
  11. 		x = pow(10, i)
  12. 		# print "x == %d" % x
  13. 		xmodn = x % n		
  14. 		if xmodn == 0:
  15. 			return x
  16. 		dp1 = [0] * n
  17. 		dp1[xmodn] = x
  18. 		for j in range (n-1, -1, -1):
  19. 			dp1[j] = (dp[(j - xmodn) % n] + x) if dp[(j - xmodn) % n] != 0 else dp1[j]
  20. 			# print "dp1[%d] = %d" % (j, dp1[j])
  21.  
  22. 		for j in range(0, n):
  23. 			dp[j] = dp1[j] if dp[j] == 0 else dp[j]
  24. 		# print dp
  25. 		i = i + 1
  26.  
  27. 	return dp[0]
  28.  
  29. for n in range (1, 100):
  30. 	sn = solve(n)
  31. 	print "solve(%d): %d" % (n, solve(n))
  32. 	if sn % n != 0:
  33. 		print "Remainder is %d not 0" % (sn % n)
  34.  
  35. print solve(99998)
Success #stdin #stdout 1.41s 8280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
solve(1): 1
solve(2): 10
solve(3): 111
solve(4): 100
solve(5): 10
solve(6): 1110
solve(7): 1001
solve(8): 1000
solve(9): 111111111
solve(10): 10
solve(11): 11
solve(12): 11100
solve(13): 1001
solve(14): 10010
solve(15): 1110
solve(16): 10000
solve(17): 11101
solve(18): 1111111110
solve(19): 11001
solve(20): 100
solve(21): 10101
solve(22): 110
solve(23): 110101
solve(24): 111000
solve(25): 100
solve(26): 10010
solve(27): 1101111111
solve(28): 100100
solve(29): 1101101
solve(30): 1110
solve(31): 111011
solve(32): 100000
solve(33): 111111
solve(34): 111010
solve(35): 10010
solve(36): 11111111100
solve(37): 111
solve(38): 110010
solve(39): 10101
solve(40): 1000
solve(41): 11111
solve(42): 101010
solve(43): 1101101
solve(44): 1100
solve(45): 1111111110
solve(46): 1101010
solve(47): 10011
solve(48): 1110000
solve(49): 1100001
solve(50): 100
solve(51): 100011
solve(52): 100100
solve(53): 100011
solve(54): 11011111110
solve(55): 110
solve(56): 1001000
solve(57): 11001
solve(58): 11011010
solve(59): 11011111
solve(60): 11100
solve(61): 100101
solve(62): 1110110
solve(63): 1111011111
solve(64): 1000000
solve(65): 10010
solve(66): 1111110
solve(67): 1101011
solve(68): 1110100
solve(69): 10000101
solve(70): 10010
solve(71): 10011
solve(72): 111111111000
solve(73): 10001
solve(74): 1110
solve(75): 11100
solve(76): 1100100
solve(77): 1001
solve(78): 101010
solve(79): 10010011
solve(80): 10000
solve(81): 1111111101
solve(82): 111110
solve(83): 101011
solve(84): 1010100
solve(85): 111010
solve(86): 11011010
solve(87): 11010111
solve(88): 11000
solve(89): 11010101
solve(90): 1111111110
solve(91): 1001
solve(92): 11010100
solve(93): 10000011
solve(94): 100110
solve(95): 110010
solve(96): 11100000
solve(97): 11100001
solve(98): 11000010
solve(99): 111111111111111111
11111000000000011110
https://ideone.com/4red2G
language:
Python (cpython 2.7.16)
created:
9 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!