Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

题目大意：

你正在和朋友玩下面的Nim游戏：桌子上有一堆石头，每一次你们轮流取1至3颗石头。最后一个取走石头的人就是赢家。第一轮由你先取。

你们俩都很聪明并且掌握玩游戏的最佳策略。编写函数，给定石头的个数，判断你是否可以赢得游戏。

例如，如果堆中有4颗石头，那么你一定不会赢得游戏：无论你第一轮取走1，2，还是3颗石头，下一轮你的朋友都可以取走余下的所有石头。

提示：

如果堆中有5颗石头，你可以找出确保自己能赢的取石子策略吗？

解题思路：

由于是我们先拿，那么3个以内(包括3个)的石子，我们直接赢，如果共4个，那么我们一定输，因为不管我们取几个，下一个人一次都能取完。如果共5个，我们赢，因为我们可以取一个，然后变成4个让别人取，根据上面的分析我们赢，所以我们列出1到10个的情况如下：

1 Win

2 Win

3 Win

4 Lost

5 Win

6 Win

7 Win

8 Lost

9 Win

10 Win

由此我们可以发现规律，只要是4的倍数个，我们一定会输，所以对4取余即可。

class Solution(object):
    def canWinNim(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n%4!=0