题目描述

Alice 和 Bob 在玩一个游戏，他们俩轮流从一堆石头中移除石头，Alice 先进行操作。

• Alice 在第一次操作中移除 恰好 10 个石头。
• 接下来的每次操作中，每位玩家移除的石头数 恰好 为另一位玩家上一次操作的石头数减 1。

第一位没法进行操作的玩家输掉这个游戏。

给你一个正整数 n 表示一开始石头的数目，如果 Alice 赢下这个游戏，请你返回 true，否则返回 false。

样例

输入：n = 12

输出：true

解释：

Alice 第一次操作中移除 10 个石头，剩下 2 个石头给 Bob。
Bob 无法移除 9 个石头，所以 Alice 赢下游戏。

输入：n = 1

输出：false

解释：

Alice 无法移除 10 个石头，所以 Alice 输掉游戏。

限制

• 1 <= n <= 50

算法

(模拟) $O(n)$

1. 直接模拟两个人的游戏过程，用一个布尔变量判断当前是谁的回合。

时间复杂度

• 游戏最多进行 $O(n)$ 次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canAliceWin(int n) {
        int t = 10;
        bool ans = false;

        while (n >= t) {
            n -= t;
            t--;
            ans = !ans;
        }

        return ans;
    }
};