Tower Breakers - The Final Battle
Tower Breakers - The Final Battle
+ 1 comment The game isn't explained well ... In the last case H=2 so it's split into 1 and 1 P2 chooses the second tower so how did it become 2^2?
+ 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()))
+ 1 comment According to problem statement x>=2 and k>= 1 and k<=x ;
so for example if n=4; coin =0 (initially) 4=>{2,2} since k >=1 left {2} and coin=1^2=1 now 2=>{1,1} i.e. x=2; now take both coin 2^2=4 so answer = 1+4=5 then why 6 in testcase ...
+ 0 comments biased for p2 i think
+ 1 comment Hi! I am wondering how to pay only 14 coins for tower high 62? According to my calculations the last one that would be possible with 14 coins is 59. Could someone please show me a counterexample of how it is possible? Thank you in advance!
Sort 16 Discussions, By:
Please Login in order to post a comment