36 lines
695 B
Python
36 lines
695 B
Python
#!/usr/bin/env python3
|
|
|
|
# See 144
|
|
|
|
def main(m, bound):
|
|
n = m
|
|
tbl = []
|
|
while p(m, n, tbl) < bound: n += 1
|
|
return n, p(m, n, tbl)
|
|
|
|
def p(m, n, tbl=False):
|
|
if n < m:
|
|
return 1
|
|
if tbl==False:
|
|
tbl = []
|
|
if n-m >= len(tbl):
|
|
r = 2*p(m, n-1, tbl) - p(m, n-2,tbl) + p(m, n-m-1, tbl)
|
|
tbl.append(r)
|
|
return tbl[n-m]
|
|
|
|
def p2(m, n):
|
|
#doesnt work why?
|
|
if n < m:
|
|
return 1
|
|
matrix = [1]+[0]*m
|
|
matrix[-1] = 1
|
|
for _ in range(3,n):
|
|
bm = matrix[-1]
|
|
for i in range(m, 0, -1):
|
|
matrix[i] = matrix[i-1]
|
|
matrix[-1] += bm
|
|
matrix[0] += bm
|
|
return sum(matrix)
|
|
|
|
print(main(50, 10**6)[0])
|