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?

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()))

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 ...

biased for p2 i think

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!