HackerRank Tower Breakers The Final Battle problem solution

In this HackerRank Tower Breakers – The Final Battle problem solution Our unsung tower-breaking heroes (players P1 and P2) only have one tower left, and they’ve decided to break it for a special game commemorating the end of 5 days of Game Theory! The rules are as follows:

1. P1 always moves first, and both players always move optimally.
2. Initially, there is 1 tower of height N.
3. The players move in alternating turns. The moves performed by each player are different:
4. At each turn, P1 divides the current tower into some number of smaller towers. If the turn starts with a tower of height H and P1 breaks it into smaller towers, the following condition must apply: H = h1 + h2 +…+ Hx, where H1 denotes the height of the ith new tower.
5. At each turn, P2 chooses some tower K of the X new towers made by P1 (where 1 <= K <= X). Then P1 must pay the square of K coins to P2. After that, P1 gets another turn with tower Hk and the game continues.
6. The game is over when no valid move can be made by P1, meaning that H = 1.
7. P1’s goal is to pay as few coins as possible, and P2’s goal is to earn as many coins as possible.

Can you predict the number of coins that P2 will earn?

Problem solution in Python.

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

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
    private ArrayList<Long> maxN;
    
    public static void main(String[] args) {
        Solution solver = new Solution();
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; ++i) {
            long N = in.nextLong();
            System.out.println(solver.getAnswer(N));
        }
    }
    
    private int getAnswer(long N) {
        if (maxN == null) {
            maxN = new ArrayList<>();
            maxN.add(1L);
        }

        while (maxN.get(maxN.size() - 1) < N) {
            findNextMaxN();
        }
        
        int i = 0;
        while (N > maxN.get(i)) {
            ++i;
        }
        return i;
    }
    
    private void findNextMaxN() {
        int cost = maxN.size();
        long L = maxN.get(cost - 1);
        long R = 2 * L + 100;
        while (L + 1 < R) {
            long M = (L + R) / 2;
            if (trySplit(M, cost)) {
                L = M;
            } else {
                R = M;
            }
        }
        maxN.add(L);
    }
    
    private boolean trySplit(long N, int cost) {
        long sum = N;
        int pos = 1;
        while (sum > 0) {
            if (pos * pos > cost) { return false; }
            long cur = maxN.get(cost - pos * pos);
            sum -= cur;
            pos++;
        }
        return true;
    }
}

Problem solution in C++.

#include <algorithm>
#include <iostream>

using namespace std;

long long dp[128];

int main() {
    dp[4] = 2;
    for (int x = 5; ; x++) {
        int k = 1;
        while ((k + 1) * (k + 1) <= x)
            k++;
        long long n = 0;
        while (k >= 1) {
            int y = x - k * k;
            n += y < 4 ? 1 : dp[y];
            k--;
        }
        dp[x] = n;
        if (n > 1e18)
            break;
    }
    int t; cin >> t;
    while (t--) {
        long long n; cin >> n;
        int x = 1;
        while (dp[x] < n)
            x++;
        cout << x << 'n';
    }
    return 0;
}

Problem solution in C.

#include<stdio.h>
int main()
{
    unsigned long a[200];
    int limit,i;
    a[0]=a[1]=a[2]=a[3]=1;
    for(i=4;i<200;i++)
    {
        a[i]=0;
        for(int j=1;j*j<=i;j++)
        a[i]=a[i]+a[i-j*j];
        if(a[i]>=1000000000000000000ul)
        break;
    }
    limit=i+1;
    int n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        unsigned long t;
        scanf("%lu",&t);
        for(int j=4;j<limit;j++)
        if(a[j]>=t)
        {
            printf("%dn",j);
            break;
        }
    }
}