fork download
copy 
  1. def recursion_zenik(n,k,path=[],debug=False):
  2.     if path and max(path)-min(path)>k:
  3.         if debug:
  4.             print('Zenik rule fail:',path)
  5.         return 0
  6.     if n==0:
  7.         if debug:
  8.             print('Success:',path)
  9.         return 1
  10.     return sum(recursion_zenik(n-i,k,path+[i]) for i in range(1,n+1))
  11.  
  12. def matrix_zenik(n,k, debug = False):
  13.     matrix = []
  14.     for step in range(n+1):
  15.         line = [0]*(step+2)
  16.         matrix.append([line[:] for _ in range(n+1)])
  17.         matrix[step][step][step] = 1 #we have 1 way to step from the land on each step
  18.  
  19.     for step_from in range(1,n):
  20.         for step_to in range(step_from+1,n+1):
  21.             for min_i in range(1,step_from+2):
  22.                 for max_i in range(min_i,min(min_i+k,step_from+1)+1):                
  23.                     min_to_write = min(min_i,step_to-step_from)
  24.                     max_to_write = max(max_i,step_to-step_from)
  25.                     if max_to_write-min_to_write<=k:
  26.                         matrix[step_to][min_to_write][max_to_write] += matrix[step_from][min_i][max_i]
  27.  
  28.     if debug:
  29.         for step in range(n+1):
  30.             print(step,':',',\n'.join(str(line) for line in matrix[step]))
  31.     return sum(sum(line) for line in matrix[n])
  32.  
  33. def check_equal_rec_mat(s):
  34.     for n in range(1,s):
  35.         for k in range(1,s):
  36.             rec = recursion_zenik(n,k)
  37.             mat = matrix_zenik(n,k)
  38.             if rec!=mat:
  39.                 print('\nFAIL: n=',n,'k=',k,'rec=',rec,'mat=',mat)
  40.             else:
  41.                 print('OK',end=' ')
  42.     print()
  43.  
  44. #print('Result =',recursion_zenik(4, 2, debug=False))
  45. #print('Result =',matrix_zenik(4,2,debug=True))
  46. #check_equal_rec_mat(15)
  47. import time
  48. t = time.clock()
  49. print(matrix_zenik(100,100))
  50. print('time = ',time.clock()-t)
  51.  
Success #stdin #stdout 2.41s 15300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
633825300114114700748351602688
time =  2.39042
https://ideone.com/KmIuFW
language:
Python 3 (python  3.9.5)
created:
5 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!