ulvis.paste.net

Paste Search Dynamic
Recent pastes
strList
  1. import math
  2.  
  3. def sliceIntoMultiplesOf5(s):
  4.         print(s)
  5.         def isPowerOf5(s):
  6.                 print("s = ",s)
  7.                 x = int(s, 2)
  8.                 print("x = ",x)
  9.                 n = int(math.log2(x) / math.log2(5))
  10.                 print("n = ",n,"\n\n")
  11.                 return 5 ** n == x
  12.  
  13.         # initialize
  14.         n = len(s)
  15.         f = [-1] * n
  16.         # dp
  17.         for i in range(n):
  18.                 if isPowerOf5(s[:i+1]):
  19.                         print("Power of 5")
  20.                         f[i] = 1
  21.                         continue
  22.                 print(f)
  23.                 for j in range(i):
  24.                         print("j = ",j," i = ",i)
  25.                         # pieces do not start with 0
  26.                         if f[j] == -1 or s[j+1] == '0' or not isPowerOf5(s[j+1:i+1]):
  27.                                 print("check")
  28.                                 continue
  29.                         if f[i] == -1:
  30.                                 f[i] = f[j] + 1
  31.                         else:
  32.                                 f[i] = min(f[i], f[j] + 1)
  33.         # result
  34.         return f[n-1]
  35.  
  36.  
  37. # test case
  38. strList = [
  39. "1011"
  40. ]
  41.  
  42. for s in strList:
  43.         print(sliceIntoMultiplesOf5(s))
Parsed in 0.010 seconds