You are viewing a single comment's thread. Return to all 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()))
Seems like cookies are disabled on this browser, please enable them to open this website
Tower Breakers - The Final Battle
You are viewing a single comment's thread. Return to all 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