292-Nim游戏.py

'''
你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

 

示例 1：

输入：n = 4
输出：false 
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
示例 2：

输入：n = 1
输出：true
示例 3：

输入：n = 2
输出：true
 

提示：

1 <= n <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nim-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''


'''
Nim游戏，只要数字总数n，能取得的最小值a和能取得的最大值b加起来的和c。有如下关系。
n % c == 0 先手必输，前提是可选的数字要是连续的。
否则，先手只要抢到余数就必胜。

为什么呢？
其实也很简单，你想啊，c相当于每次游戏先手可以控制的两人走的最近的一步。
什么意思呢，就是说，每次两个人报数，是两个数字，不管对方选择了范围内哪个数字。
都可以在第二次报数的时候，把两个人报的数字和凑成c。

这就是上面我说的前提。
比如如果是1，2，3，不管对面报几，你都可以选另一个数字，把总和凑成4。
比如如果是1，2，3，4，不管对面报几，你都可以选另一个数字，把总和凑成5。

所以只要先手抢到了余数，那么剩下的每一轮，先手都可以保证整体前进c。所以必胜。

PS：
如果是不连续的，就比较麻烦。
比如如果是1，2，4，对面报了2，就凑不到5了。就要分成几个情况讨论了。

作者：flying_du
链接：https://leetcode-cn.com/problems/nim-game/solution/python-chao-ji-wu-di-jian-dan-jie-xi-quan-guo-zui-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
'''

class Solution:
    def canWinNim(self, n: int):
        return (n % 4) != 0