- The shorter the code is, the harder the problem is.
- First we need to realize that we
don't care about the valueof each stone, we just need to know their remainder against
s % 3.
- There will be
0, 1, 2three situations.
0will be used as a chance to shift choices. Both opponents will use
0when they don’t want to choose!.
- It doesn’t have any impact on the outcome!
- Now, if either
count2is 0, then
Alice will def loseon round 3. Such as
1, 1, 1or
2, 2, 2.
- If Alice wants to win, just choose the smaller one between
count2BECAUSE if Alice choose the smaller one which is
1, then in the following sequences, Bob will ALWAYS choose
1and Alice will ALWAYS choose
2, then because Bob will
exhaust his choices first, and he has to choose Alice’s 2, which leads to his loss.
- It gives Alice another choice to choose again!
- Apparently, if Alice wants to win, the sequence will end like below
- So as long as
|count1 - count2| > 2, we can also form these kinds of sequences to make Bob exhaust his choice first, and has to resort to Alice’s choices.
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[i] is the value of the
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
true if Alice wins and
false if Bob wins.
Input: stones = [2,1]