blob: d114bfdfba960e33e787d2ed37fafbf0819dbebf (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#!/opt/local/bin/python
#
# See ../README.md
#
#
# Run as: python ch-2.py < input-file
#
cache = {}
def _count (target, this_fib, prev_fib):
key = str (target) + ";" + str (this_fib)
if not (key in cache):
if target < this_fib:
cache [key] = 0
elif target == this_fib:
cache [key] = 1
else:
cache [key] = \
_count (target - this_fib, this_fib + prev_fib, this_fib) + \
_count (target, this_fib + prev_fib, this_fib)
return cache [key]
def count (target):
return (_count (target, 1, 1))
import fileinput
for line in fileinput . input ():
print (count (int (line)))
|
