fork download
copy 
  1. # your code goes here
  2. import time
  3. import sys
  4. import functools 
  5. from math import sqrt
  6.  
  7. #print(f' sys.getrecursionlimit()={sys.getrecursionlimit()}')
  8. i=0
  9. sys.setrecursionlimit(1000000)
  10. #@functools.lru_cache()
  11. #- без нього f(1024)вираховується більше 10 хвилин, а з ним 5 секунд 21:43
  12. @functools.lru_cache(maxsize=None)
  13. def f(x):
  14.     global i
  15.     i +=1
  16.     if i%750==0: print(i)
  17.     if x <=1: return 0
  18.     return 1 + min( [f(m + x // m - 2)  for m in range(int(sqrt(x))+1,0,-1) if x%m==0]  )
  19.  
  20. x = int(input("дай целое!"))
  21. t0 = time.clock()
  22. print( f(x))
  23. t1 = time.clock()
  24. print (t1-t0, '  i=', i)
  25. print(f.cache_info())
Success #stdin #stdout 2.04s 164060KB
comments (?)
stdin
copy 
100000
stdout
copy 
дай целое!750
1500
2250
3000
3750
4500
5250
6000
6750
7500
8250
9000
9750
10500
11250
12000
12750
13500
14250
15000
15750
16500
17250
18000
18750
19500
20250
21000
21750
22500
23250
24000
24750
25500
26250
27000
27750
28500
29250
30000
30750
31500
32250
33000
33750
34500
35250
36000
36750
37500
38250
39000
39750
40500
41250
42000
42750
43500
44250
45000
45750
46500
47250
48000
48750
49500
50250
51000
51750
52500
53250
54000
54750
55500
56250
57000
57750
58500
59250
60000
60750
61500
62250
63000
63750
64500
65250
66000
66750
67500
68250
69000
69750
70500
71250
72000
72750
73500
74250
75000
75750
76500
77250
78000
78750
79500
80250
81000
81750
82500
83250
84000
84750
85500
86250
87000
87750
88500
89250
90000
90750
91500
92250
93000
93750
94500
95250
96000
96750
97500
98250
99000
99750
7
1.9721340000000003   i= 100000
CacheInfo(hits=483848, misses=100000, maxsize=None, currsize=100000)
https://ideone.com/aV9Z8p
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
secret

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!