fork download
  1. lookup = {}
  2.  
  3. def lothar(n):
  4. if n not in lookup:
  5. if n == 1:
  6. lookup[n] = 0
  7. elif not n % 2:
  8. lookup[n] = lothar(n / 2)[0] + 1
  9. else:
  10. lookup[n] = lothar(n*3 + 1)[0] + 1
  11.  
  12. return lookup[n], n
  13.  
  14.  
  15. tests = int(raw_input())
  16. for i in range(1, 1000001):
  17. lothar(i)
  18. while tests:
  19. a, b = [int(x) for x in raw_input().split()]
  20. print max(lookup[x] for x in range(a, b+1))
  21. tests -= 1
Time limit exceeded #stdin #stdout 5s 99264KB
stdin
99
1 1000000
4 1000000
9 1000000
16 1000000
25 1000000
36 1000000
49 1000000
64 1000000
81 1000000
100 1000000
121 1000000
144 1000000
169 1000000
196 1000000
225 1000000
256 1000000
289 1000000
324 1000000
361 1000000
400 1000000
441 1000000
484 1000000
529 1000000
576 1000000
625 1000000
676 1000000
729 1000000
784 1000000
841 1000000
900 1000000
961 1000000
1024 1000000
1089 1000000
1156 1000000
1225 1000000
1296 1000000
1369 1000000
1444 1000000
1521 1000000
1600 1000000
1681 1000000
1764 1000000
1849 1000000
1936 1000000
2025 1000000
2116 1000000
2209 1000000
2304 1000000
2401 1000000
2500 1000000
2601 1000000
2704 1000000
2809 1000000
2916 1000000
3025 1000000
3136 1000000
3249 1000000
3364 1000000
3481 1000000
3600 1000000
3721 1000000
3844 1000000
3969 1000000
4096 1000000
4225 1000000
4356 1000000
4489 1000000
4624 1000000
4761 1000000
4900 1000000
5041 1000000
5184 1000000
5329 1000000
5476 1000000
5625 1000000
5776 1000000
5929 1000000
6084 1000000
6241 1000000
6400 1000000
6561 1000000
6724 1000000
6889 1000000
7056 1000000
7225 1000000
7396 1000000
7569 1000000
7744 1000000
7921 1000000
8100 1000000
8281 1000000
8464 1000000
8649 1000000
8836 1000000
9025 1000000
9216 1000000
9409 1000000
9604 1000000
9801 1000000
stdout
Standard output is empty