HackerRank A stones game problem solution

In this HackerRank A stones game problem solution Koga and Ryuho, new generation Athena’s saints, are training to improve their control over the cosmos. According to the ancient Masters, a saint’s power to control the cosmos strengthens, when one allows the energy of the universe to flow within the body and then concentrates it. This energy can even be used to explore objects.

Today’s training is based on a game, and the goal is to use as little cosmos as possible to win. Two saints play as follows:

Initially, there are N piles of stones; pile 1 has 1 stone, pile 2 has 2 stones, and so on. Thus, the ith pile has I stones. The saints take turns and in each turn, a saint must select a non-empty pile and destroy at least half of the stones in it. The winner is the saint who destroys the last available stone.

Problem solution in Python.

#!/usr/bin/env python3

import sys

from functools import lru_cache
@lru_cache(maxsize=None)
def grundy(n):
    if n==0:
        return 0
    S = [grundy(m) for m in range(n//2+1)]
    g = 0
    while g in S:
        g += 1
    return g

def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        L = N.bit_length()
        G = 1  # for the single 1
        if N&1==0:  # value L if appears an odd nb of times (i.e. N even)
            G ^= L
        D = 1
        if G!=1:
            GA = 1<<(G.bit_length()-1)
            A = 1<<(GA-1)
            GB = G^GA
            B = min((1<<GB)-1, A>>1) if GB else 0
            D = A-B
        sys.stdout.write('%dn' % D)

main()

Problem solution in Java.

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

public class AStoneGame {

    private static int log2(int val) {
        return 31 - Integer.numberOfLeadingZeros(val);
    }

    private static int solve(int val) {
        if (val <= 1) return val;

        int maxNim = log2(val) + 1;
        int maxNimCnt = val - (1 << (maxNim - 1)) + 1;

        if (maxNimCnt % 2 == 0) return 1;

        int nimToReduce = 1 << log2(maxNim);

        int targetNim = maxNim;
        targetNim = targetNim ^ nimToReduce;
        targetNim = targetNim ^ 1;

        int targetValueToReduce = (1 << (nimToReduce - 1));
        int reduceTo = (1 << (targetNim)) - 1;
        int minCut = targetValueToReduce / 2 + targetValueToReduce % 2;

        return targetValueToReduce - minCut >= reduceTo ? targetValueToReduce - reduceTo : minCut;
    }

    public static void main(String[] params) throws Exception {
        Scanner scanner = new Scanner(System.in);
        OutputWriter writer = new OutputWriter(System.out);

        int t = Integer.valueOf(scanner.nextLine());
        for (int i = 0; i < t; ++i) {
            writer.printInt(solve(Integer.valueOf(scanner.nextLine())));
            writer.newLine();
        }
        writer.flush();
    }

    static class OutputWriter {
        private static final int outBufferSize = 1 << 25;

        private PrintStream out;
        private byte[] outBuffer = new byte[outBufferSize];
        private int outByteCnt = 0;
        private byte[] intToStringBuffer = new byte[11];

        public OutputWriter(PrintStream out) {
            this.out = out;
        }

        public void flush() {
            out.write(outBuffer, 0, outByteCnt);
        }

        public void printInt(int val) {
            int outBufferPos = intToStringBuffer.length;
            if (val == 0) {
                outBufferPos = intToStringBuffer.length - 1;
                intToStringBuffer[outBufferPos] = '0';
            } else {
                boolean minus = false;
                if (val < 0) {
                    minus = true;
                    val = -val;
                }
                while (val != 0) {
                    byte digitChar = (byte)(val % 10 + '0');
                    intToStringBuffer[--outBufferPos] = digitChar;
                    val = val / 10;
                }
                if (minus) intToStringBuffer[--outBufferPos] = '-';
            }

            System.arraycopy(intToStringBuffer, outBufferPos, outBuffer, outByteCnt, intToStringBuffer.length - outBufferPos);
            outByteCnt += intToStringBuffer.length - outBufferPos;
        }

        public void newLine() {
            outBuffer[outByteCnt++] = 'n';
        }
    }
}

Problem solution in C++.

#include <cstdio>
#include<iostream>
#include<cassert>
using namespace std;
int tab[32][32];
inline void compute(){
    register int i, j, sfx, tfx;
    for (i = 1; i <= 31; ++i)
        for (j = 0; j < i; ++j) {

            sfx = 1 << (i - 1);
            if (j == 0){
                tab[i][j] = sfx;
            } else if (i - j == 1) {
                tab[i][j] = sfx >> 1;
            } else {
                tfx = (1 << j) - 1;
                tab[i][j] = sfx - tfx;
            }
        }
}
const int TEST = 10;
int main() {
    compute();
    int t;
    cin >> t;
    assert(1 <= t && t <= 1e6);
    register int N, X, tot, targ, px, i, ans, tx, mx;
    while (scanf("%d", &N) != EOF) {
        assert(1 <= N && N <= 1e9);
        if (N == 1 || N == 2) {printf("1n");continue;}
        X = 1, px = 1;
        while(X <= N) {X <<= 1; ++px;}
        X >>= 1, --px;
        tot = N - X + 1;
        if (tot & 1) {
            targ = 1 ^ px, ans = X - 1, mx = px - (tot == 1);
            for (i = 2; i <= mx; ++i) {
                tx = targ ^ i;
                if (tx < i) {
                    if (ans == -1 || ans > tab[i][tx])
                        ans = tab[i][tx];
                }
            }
            printf("%dn", ans);
        }
        else printf("1n");
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int t;
    scanf("%dn", &t);
    for (int i = 0; i < t; i++) {
        int n;
        scanf("%dn", &n);
        int nimber = 1;
        int topnimber = floor(log2(n)) + 1;
        if (!(n&1)) nimber ^= topnimber;
        int changenimber = 1<< (int)floor(log2(nimber));
        int tonumber = changenimber ^ nimber;
        int minchangepile = 1<<(changenimber - 1);
        int maxtopile = (1<<tonumber) - 1;
        if (maxtopile * 2 > minchangepile) maxtopile = minchangepile / 2;
        int answer = minchangepile - maxtopile;
        printf("%dn", answer);
    }
    return 0;
}