game-theory - Manasa 和 Prime 游戏 (Hackerrank)

Question

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

Manasa 喜欢 NIM 游戏，但在同一个游戏中玩了很多次，有一天她觉得无聊。所以她想改变游戏规则。由于她喜欢素数，她制定了一条新规则：任何玩家只能从桶中取出素数的球。但是有无限的素数。所以为了保持游戏简单，玩家只能从一个桶中取出 x 个球，其中 x 属于集合 S。 S={2,3,5,7,11,13} 现在整个游戏可以描述为如下：给定 N 个桶和第 k 个桶有 Ak 数量的球，玩家可以选择一个桶并从该桶中取出 x 个球，其中 x 属于 S。 Manasa 对桑迪采取第一步。如果他们两个都发挥最佳，谁会赢？

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

从这个博客分析。