Manasa和Prime游戏(Hackerrank)

Question

我需要帮助来解决这个问题-

Manasa喜欢NIM游戏，但在玩了这么多次同一个游戏后，有一天她感到无聊。所以她想改变游戏规则。因为她喜欢质数，所以她制定了一条新规则:任何球员只能从桶中取出质数的球。但是有无限的质数。因此，为了保持游戏简单，玩家只能从桶中移除x个球，其中x属于集合S。S={2,3,5,7,11,13}现在整个游戏可以描述如下:给定N个桶和第k个桶具有Ak个球，玩家可以选择一个桶并从x属于S. Manasa的桶中移除x个球。如果他们都打得最好，谁会赢？

Answer 1

下面的代码完美地解决了这个问题：

from itertools import imap
import operator

def mapg(N, A):
  return 0 != reduce(operator.xor, (a%9//2 for a in A), 0)

for _ in xrange(input()):
  N = input()
  A = map(int, raw_input().split())
  print "Manasa" if mapg(N, A) else "Sandy"

Answer 2

java解决方案：

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

public class Solution {  

    public static void main(String[] args) {  
        int t = ni();  
        for(int i=0; i<t; i++){  
            System.out.println(solve());  
        }  
    }  

    public static int[] values = new int[]{0, 0, 1, 1, 2, 2, 3, 3, 4};  
    public static String solve(){  
        int n = ni();  
        long ak;  
        long nimber = 0; //or grundy number  
        for(int i=0; i<n; i++){  
            ak = nl();  
            nimber ^= values[(int) (ak % values.length)];
        }  
        if(nimber > 0) return "Manasa";  
        return "Sandy";  
    }  

    public static Scanner sc = new Scanner(System.in);  
    public static int ni(){  
        return sc.nextInt();  
    }  
    public static long nl(){  
        return sc.nextLong();  
    }  
}  

来自this blog的分析。