Tower Breakers - The Final Battle

  • + 2 comments

    An O(1) python solution using O(1) space

    the idea is to use dynamic programming to find the maximal possible number d[n] such that P_2 will earn exact n coins

    by simple observation, d[130] is already over 1e20 > 1e18, so we only need to store the d[n] values up to n=130

    a reference for the recursive formula can be found here http://oeis.org/A006456

    import math
    from collections import defaultdict
    
    def F(n):
        if n in d:
            return d[n]
        else:
            temp=0
            for k in range(1,int(math.sqrt(n))+1):
                temp+=F(n-k**2)
            d[n]=temp
            return d[n]
        
    def towerBreakers(n):
        ans=0
        while d[ans]<n:
            ans+=1
        print(ans)    
    
    d=defaultdict(int)
    d[0]=1
    F(130)  #d[130]>10**18
        
    for _ in range(int(input())):
        towerBreakers(int(input()))