fork download 
  1. import itertools
  2.  
  3. import sys
  4. sys.setrecursionlimit(100000)
  5.  
  6.  
  7. answers = {}
  8. def memoize(func):
  9.     def f(*args):
  10.         if args not in answers:
  11.             answers[args] = func(*args)
  12.         return answers[args]
  13.     return f
  14.  
  15. def split_along(s, points):
  16.     points = [0] + points + [len(s)]
  17.     for a,b in zip(points, points[1:]):
  18.         yield s[a:b]
  19.  
  20. def special_partition(s):
  21.     split_points = []
  22.     for i in range(len(s)):
  23.         if any(s[i:].startswith(prefix) for prefix in ("211131", "211132", "23113", "21321" "2322")):
  24.             split_points.append(i+1)
  25.     return list(split_along(s, split_points))
  26.  
  27. f = lambda s: "".join(str(len(list(v)))+k for k,v in itertools.groupby(s))
  28.  
  29. def g(s,x):
  30.     for i in range(x):
  31.         s = f(s)
  32.     return s
  33.  
  34. def show_sequence(s, max):
  35.     for x in range(max):
  36.         print g(s,x)
  37.  
  38. min_visited_depth = float("inf")
  39.  
  40. @memoize
  41. def size(s, n, m=None):
  42.     global min_visited_depth
  43.     if n < min_visited_depth:
  44.         #print n,
  45.         min_visited_depth = n
  46.  
  47.     if len(s) > 100:
  48.         raise Exception("failed to cleave efficiently on {}".format(s))
  49.     if n == 0:
  50.         return len(s)
  51.     pieces = special_partition(s)
  52.     piece_sizes = [size(f(piece), n-1, m) for piece in pieces]
  53.     result = sum(piece_sizes)
  54.     if m: result = result % m
  55.     return result
  56.  
  57. try:
  58.     print size("3", 500, 100)
  59. except Exception as e:
  60.     print e.message
Time limit exceeded #stdin #stdout 5s 14264KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZCy7gG
language:
Python (cpython 2.7.16)
created:
10 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!