Stone Piles Discussions | Algorithms | HackerRank
  • + 0 comments
    MAXN = 53
    
    G = [-1] * MAXN
    dp = [[-1 for _ in range(15)] for _ in range(MAXN)]
    vis = [[False for _ in range(100000)] for _ in range(MAXN)]
    
    def grundy(pile_size):
        if G[pile_size] != -1:
            return G[pile_size]
        backTrack(pile_size, pile_size)
        
        ret = 0
        while vis[pile_size][ret]:
            ret += 1
        G[pile_size] = ret
        return ret
    
    def getCount(s, k):
        if k == 0:
            return int(s == 0)
        if dp[s][k] != -1:
            return dp[s][k]
        
        ret = 0
        for i in range(1, s // k + 1):
            ret += getCount(s - k * i, k - 1)
        
        dp[s][k] = ret
        return ret
    
    def backTrack(init_pile_size, curr_pile_size, prev=0, xr=0):
        if curr_pile_size == 0:
            if prev:
                vis[init_pile_size][xr] = True
            return
        
        st = prev + 1
        for i in range(st, min(curr_pile_size, init_pile_size - 1) + 1):
            backTrack(init_pile_size, curr_pile_size - i, i, xr ^ grundy(i))
    
    def main():
        import sys
        input = sys.stdin.read
        data = input().split()
        
        t = int(data[0])
        index = 1
        
        for _ in range(t):
            n = int(data[index])
            index += 1
            xr = 0
            
            for _ in range(1, n + 1):
                v = int(data[index])
                index += 1
                xr ^= grundy(v)
            
            if xr:
                print("ALICE")
            else:
                print("BOB")
    
    if __name__ == "__main__":
        main()