Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.
Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice’s turn).
Assuming both players play optimally, return true if Alice wins and false if Bob wins.
條件
- 玩家必須避免拿取石頭總和為 3 的倍數
- Alice 開局
- 若石頭被拿光，Bob 自動獲勝 (即過程中皆未發生 sum 被 3 整除時，Bob 自動獲勝)
解題方式：
先處理石堆，轉換為 3 的餘數
餘數 1 開局
拿取餘數 目前總和 1 1 1 2 2 4 1 5 2 7 1 8 2 10
會發現無論使用 餘數 1 或 餘數 2 開局，為避免成為 3 的倍數，取石會進入固定循環。
以此做為解題前提，可知餘數 = 0 的石堆在遊戲中會相互抵消 (只需考慮有奇數堆或是偶數堆)
Source Code
def stoneGameIX(self, stones: List[int]) -> bool:
memo = [0]*3
for stone in stones:
memo[stone%3] += 1
# 情況 1：0-石頭為偶數個
if memo[0] % 2 == 0:
# 為避免拿到被 3 整除的 sum，餘數 0 的石堆只會在玩家間互相抵消 (不須考慮)
# 一旦餘數 = 1 和 餘數 = 2 的石堆皆存在，Alice 可選擇較少者開局 -> 必定獲勝
# 其中一個是 0 -> Alice 會因為下一回合無石堆可選而輸掉
return memo[1] >= 1 and memo[2] >= 1
# 情況 2：0-石頭為奇數個
else:
# 主導權會落入後手 (第一人為避免 sum 被 3 整除，故絕不可選)
# 2.1 相差 == 2：Alice 會拿到最後一堆，根據條件 3 -> Bob 自動獲勝
# 2.2 相差 < 2 ：Alice 無論選 餘數 1 或是 2，都會因為踩到 sum 可被 3 整除而輸掉
# 2.3 相差 > 2 ：與 2.2 相反的情況，Alice 獲勝
return abs(memo[1] - memo[2]) > 2