Tower Breakers - The Final Battle Discussions | Algorithms

4 years ago+ 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()))