Bowling Pins

                            Solution in C :

In  C  :






#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char str[301];
int dp[301],a[4000];

int main(){
  int T,N,c,i,j;
  for(dp[0]=0,i=1;i<301;i++){
    memset(a,0,sizeof(a));
    for(j=0;j<=i-1-j;j++)
      a[dp[j]^dp[i-1-j]]=1;
    for(j=0;j<=i-2-j;j++)
      a[dp[j]^dp[i-2-j]]=1;
    for(j=0;a[j];j++);
    dp[i]=j;
  }
  scanf("%d",&T);
  while(T--){
    scanf("%d%s",&N,str);
    for(i=c=j=0;i<N;i++){
      if(str[i]=='I')
        c++;
      else if(str[i]=='X' && i && str[i-1]=='I'){
        j^=dp[c];
        c=0;
      }
    }
    j^=dp[c];
    if(j)
      printf("WIN\n");
    else
      printf("LOSE\n");
  }
  return 0;
}
                        

                        Solution in C++ :

In  C++  :








#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn = 305;

int nim[Maxn];
int t;
int n;
char str[Maxn];

int main() {
    for (int i = 1; i < Maxn; i++) {
        set <int> S;
        for (int j = 0; j < i; j++)
            S.insert(nim[j] ^ nim[i - 1 - j]);
        for (int j = 0; j + 1 < i; j++)
            S.insert(nim[j] ^ nim[i - 2 - j]);
        while (S.find(nim[i]) != S.end()) nim[i]++;
    }  
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%s", str);
        int res = 0;
        for (int i = 0; i < n; i++) if (str[i] == 'I') {
            int j = i;
            while (j < n && str[j] == 'I') j++;
            res ^= nim[j - i];
            i = j;
        }
        printf("%s\n", res? "WIN": "LOSE");
    }
    return 0;
}
                    

                        Solution in Java :

In  Java :







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

	static int[] nim = new int[301];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		while(t-- > 0) {
			int n = in.nextInt();
			String s = in.next();
			List<Integer> list = new ArrayList<Integer>();
			int count = 0;
			for(int i = 0; i < s.length(); i++) {
				char ch = s.charAt(i);
				if(ch == 'I') {
					count++;
				} else {
					if(count != 0)
						list.add(count);
					count = 0;
				}
			}
			if(count > 0)
				list.add(count);

			int result = 0;
			for(int i = 0; i < list.size(); i++) {
				result ^= grundy(list.get(i));
			}
			if(result <= 0) {
				System.out.println("LOSE");
			} else {
				System.out.println("WIN");
			}
		}
		in.close();
	}

	private static int mex(List<Integer> arr) {
		int mex = 0;
		while(arr.contains(mex))
			mex++;
		return mex;
	}

	private static int grundy(int n) {
		if(nim[n] != 0)
			return nim[n];
		if(n == 0) {
			nim[0] = 0;
			return 0;
		}
		if (n == 1) {
			nim[1] = 1;
	        return (1);
		}
	    if (n == 2) {
			nim[2] = 2;
	        return (2);
	    }

		List<Integer> list = new ArrayList<Integer>();
		for(int i = 1, j = 0, k = 0; i <= n; i++) {
			int x, y;
			if(i <= n / 2) {
				x = grundy(j);
				y = grundy(n - j - 2);
				j++;
			} else {
				x = grundy(k);
				y = grundy(n - k - 1);
				k++;
			}
			list.add(x ^ y);
		}
		nim[n] = mex(list);
		return nim[n];
	}
}
                    

                        Solution in Python : 
                            
In  Python3 :






def game_from(board: str) -> list:
    game = []
    count = 0
    for c in board:
        if c == 'I':
            count += 1
        elif count > 0:
            game.append(count)
            count = 0
    if count > 0:
        game.append(count)
    return game


def moves_for(n: int, hits: [int]) -> [list]:
    moves = []
    for hit in hits:
        left = 0
        right = n - hit
        while left <= right:
            if left == 0 and right == 0:
                continue
            elif right < 1 <= left:
                moves.append([left])
            elif left < 1 <= right:
                moves.append([right])
            else:
                moves.append([left, right])
            left += 1
            right -= 1
    return moves


def mex_of(s: set) -> int:
    mex = 0
    while mex in s:
        mex += 1
    return mex


def g_of(n: int, cache: dict) -> int:
    if n < 3:
        return n
    else:
        result = cache.get(n, None)
        if result is not None:
            return result
        moves = moves_for(n, [1,2])
        s = set()
        for move in moves:
            if len(move) == 1:
                s.add(g_of(move[0], cache))
            else:
                s.add(g_of(move[0], cache) ^ g_of(move[1], cache))
        result = mex_of(s)
        cache[n] = result
        return result


def winner(board: str, cache: dict) -> str:
    game = game_from(board)
    g = 0
    for i in game:
        g ^= g_of(i, cache)
    return 'WIN' if g != 0 else 'LOSE'


n = int(input().strip())
c = {}

for i in range(n):
    input()
    g = list(input().strip())
    print(winner(g, c))