题目链接:2029. 石子游戏 IX
分情况讨论。
石子的价值仅其模 3 后的余数会对局面产生影响, 以此将石子分为三组。
若 Alice 先移除 1, 那 Bob 只能移除 1,接着 Alice 只能移除 2,接着 Bob 只能移除 1,以此类推,石子被移除的序列是 1121212121...;
若 Alice 先移除 2,那 Bob 只能移除 2,接着 Alice 只能移除 1,接着 Bob 只能移除 2,以此类推,石子被移除的序列是 221212121...。
同时,0 石子会对序列长度产生影响,但是不会对非 0 石子被移除的顺序产生影响。
如果 0 石子的数目是偶数,那么它不会对局面产生任何影响:
- 此时 Alice 若选择
1和2类石子中,数目更少(如果相等,任意选一种) 的那种,就能赢; - 但若只有一种石子(即没有
1类或2类石子),那么 Bob 必赢。
如果 0 石子的数目是奇数,那么意味着,Bob 可能在面临输的情况下反转:
- 若两类石子数目相等,那么无论 Alice 选择哪种策略,都可以移除所有石子,Alice 输;
- 如果两类石子的数目相差
1,那么会在 Bob 回合移除所有石子,Alice 输; - 如果两类石子数目相差
2,那么会在 Alice 回合移除所有石子,Alice 输; - 如果两类石子数目相差大于等于
3,那么 Bob 最终只能选择凑成3的倍数,Bob 输。
from collections import Counter
from typing import List
class Solution:
def stoneGameIX(self, stones: List[int]) -> bool:
stones = Counter(map(lambda stone: stone % 3, stones))
if stones.get(0, 0) & 1 == 0:
return stones.get(1, 0) >= 1 and stones.get(2, 0) >= 1
return abs(stones.get(1, 0) - stones.get(2, 0)) > 2