有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定先手玩家必胜还是必败?

---

描述

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定先手玩家必胜还是必败?

若必胜，返回true，否则返回false。

样例

输入: 1
输出: true

输入: 4
输出: true
解释: 先手玩家第一轮拿走一个硬币，此时还剩三个，这时无论后手玩家拿一个还是两个，下一次先手玩家都可以把剩下的硬币拿完。

挑战

O(1) 时间复杂度且O(1) 存储。

思路

博弈论问题：

有 n 个硬币排成一条线。两个参赛者 A 和 B 轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

当n=1时，A必胜（拿1个）；

当n=2时，A必胜（拿2个）；

当n=3时，A必败（A不管拿1个还是2个，B都可以将剩下的棋子一次拿完）；

当n=4时，A必胜（A拿1个，剩3个，转化为B先手必败）；

当n=5时，A必胜（A拿2个，同上）；

当n=6时，A必败（A不管拿1个还是2个，B都可以将棋子拿到只剩3个，转化为A先手必败）；

……

当n=9时，A必败（A不管拿1个还是2个，B都可以将棋子拿到只剩6个，转化为A先手必败）；

综上，

当n%3 == 0时，A不管拿1个还是2个，B都可以将棋子转化为A先手必败的情况；

同样，当n%3 != 0时，A都可以将棋子转化为B先手必败的情况。

代码

class Solution {
public:
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    bool firstWillWin(int n) {
        // write your code here
        if(n%3 == 0){
            return false;
        }
        else{
            return true;
        }
    }
};

补充

关于博弈论问题的总结，见浅谈算法——博弈论