fork download 
  1. import sys
  2.  
  3. def is_palindrome(n):
  4.     n_s = str(n)
  5. 	return n_s == n_s[::-1]
  6.  
  7. fs_list = [1, 4, 9, 121, 484]
  8. fs_sqrt_list = [[], [1, 2, 3], [11, 22]]
  9.  
  10. for n in range(3, 100 / 2 + 1):
  11. 	fs_sqrt_list.append([])
  12. 	half_n = n / 2
  13. 	is_n_odd = (half_n + half_n != n)
  14.  
  15. 	if is_n_odd:
  16. 		ref_index = n - 1
  17. 		insert_s_list = ["0", "1", "2"]
  18. 	else:
  19. 		ref_index = n - 2
  20. 		insert_s_list = ["00", "11"]
  21.  
  22. 	for val in fs_sqrt_list[ref_index]:
  23. 		s = str(val)
  24. 		half_s = s[:len(s) / 2]
  25. 		half_s_rev = half_s[::-1]
  26.  
  27. 		if half_s[0] == '2':
  28. 			insert_s_list.pop()
  29.  
  30. 		for insert_s in insert_s_list:
  31. 			fs_sqrt_candidate = int(half_s + insert_s + half_s_rev)
  32. 			fs_candidate = fs_sqrt_candidate ** 2
  33.  
  34. 			if is_palindrome(fs_candidate):
  35. 				fs_list.append(fs_candidate)
  36. 				fs_sqrt_list[n].append(fs_sqrt_candidate)
  37.  
  38. case_cnt = int(sys.stdin.readline());
  39.  
  40. for t in range(1, case_cnt + 1):
  41. 	line = sys.stdin.readline();
  42. 	start, end = map(int, line.split(' '));
  43. 	fs_cnt = len([n for n in fs_list if n >= start and n <= end])
  44. 	print "Case #%d: %d" % (t, fs_cnt)
  45.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/abFwJ6
language:
Python (cpython 2.7.16)
created:
12 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!