RainbowNim
2020 TCO Semi 2 · 2020-11-12 · by lg5293
Problem Statement
Alice and Bob are playing a game with some piles of stones. The i-th pile contains pile[i] stones with color color[i].
In a single turn, a player has two options:
- Take a positive number of stones from a single pile.
- Choose a color, and take at least one stone and a total of at most m stones from piles of that color.
You are given the the description of the piles of the stones and the number m. Return the number of subsets of piles such that Alice will win if she starts the game on just that subset of piles. Return this modulo 998244353.
Constraints
- n will be between 1 and 250, inclusive.
- pile, color will contain exactly n elements.
- Each element of pile will be between 1 and 250, inclusive.
- Each element of color will be between 1 and 250, inclusive.
- m will be between 1 and 250, inclusive.
{1, 1}
{1, 1}
2
Returns: 3
In this case, Alice can win with any non-empty subset of the piles. If there is only one pile, Alice can win by taking all the stones in that pile. If both piles are present, she can take 1 stone from each pile.
{1, 1}
{1, 250}
2
Returns: 2
In this case, Alice can't win if both piles are initially present.
{2, 2}
{1, 1}
3
Returns: 2
{250}
{1}
2
Returns: 1
{17,11,5,8,17}
{1,1,2,2,3}
2
Returns: 30
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RainbowNim with a public method int countSubsets(vector<int> pile, vector<int> color, int m) · 57 test cases · 2 s / 256 MB per case