CandyBowlGame
SRM 855 · 2024-05-22 · by misof
Problem Statement
The candy game is played with N bowls of candies. The bowls are arranged in a row and numbered from 0 to N-1 sequentially.
The game is played by two players who take alternating turns. The player unable to take a valid turn loses the game. Each turn, the current player has two options:
- Select a bowl that currently contains at least two candies. Eat exactly two of those candies.
- Select an odd number k. Select a bowl x >= k that currently contains at least k candies. Take exactly k candies from bowl x and place them into bowl (x-k).
(For example, suppose you select the odd number k = 3. If bowl 10 contains 100 candies, you may select x = 10. You will then take the k = 3 candies from bowl x = 10, leaving 97 candies there, and you will add those three candies to whatever is in bowl x-k = 7.)
You are given the initial distribution of some candies: the
You are also given E extra candies that have to be added to the bowls. (You must add each of the E candies to one of the bowls.)
A distribution of candies is winning if the player who starts the game has a winning strategy - i.e., a strategy such that the starting player following that strategy is guaranteed to win the game, regardless of what their opponent does.
Consider all different candy distributions that can be obtained by starting with the distribution C and then adding the E extra candies. Among them, count all winning ones. Return their count modulo 10^9 + 7.
Notes
- Candies are indistinguishable. Hence, different distributions of candies into bowls are simply different N-tuples of non-negative integers.
Constraints
- C will have between 1 and 100 elements, inclusive.
- Each element of C will be between 0 and 10^9, inclusive.
- E will be between 0 and 10^6, inclusive.
{4}
3
Returns: 1
The position in which the only bowl (bowl 0) contains 7 candies is winning. This is because the only valid move is to eat two candies. After the first, second, and first player again do so, the bowl will have only one candy left, and at that point the second player will lose the game as there are no valid moves left.
{0, 0, 0, 0, 0, 0, 1}
0
Returns: 0
The position described by this C is losing. The only valid move is to take the only candy and move it one bowl to the left. Eventually, the second player will move the candy into bowl 0 and then the first player will lose.
{0, 0, 0, 0, 0, 5, 0}
0
Returns: 1
The first player has a winning move: they can start by moving all five candies to bowl 0. Then the second player is forced to eat two of them, the first player eats another two, and then the second player loses the game (with one candy left in bowl 0).
{1, 0, 0}
2
Returns: 4
In this input we are asked to consider the following six configurations: {3, 0, 0}, {2, 1, 0}, {2, 0, 1}, {1, 2, 0}, {1, 1, 1}, and {1, 0, 2}. Four of them are winning, two are losing.
{0, 0, 0}
0
Returns: 0
The first player loses the game immediately.
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CandyBowlGame with a public method int win(vector<int> C, int E) · 56 test cases · 2 s / 256 MB per case