FollowingNim
SRM 789 · 2020-08-28 · by lg5293
Problem Statement
Alice and Bob are playing a game of Nim.
There are n piles of stones, described by the
There is one modification that Alice and Bob will make to the rules of nim, based on the
Alice is wondering how many initial moves are winning in the game given she goes first. Two moves are different if they remove a different number of stones or they remove stones from different piles.
Constraints
- piles will contain between 1 and 50 elements, inclusive.
- Each element of piles will be between 1 and 100, inclusive.
- special will contain between 1 and 50 elements, inclusive.
- Each element of special will be between 1 and 100, inclusive.
- Elements of special will be distinct.
- Elements of special will be in ascending order.
{5, 2}
{2}
Returns: 1
There are two piles of stones. If a player takes 2 stones from a pile, the other player is forced to make a move in the same pile. Alice can win by taking 2 stones from the second pile. Bob is forced to make a move on the second pile and is unable to since it is now empty. This is her only winning move.
{10, 10}
{3, 7}
Returns: 0
Alice has no winning moves in this case. For instance, if Alice takes 3 stones from the first pile, Bob is forced to move in the first pile and can make a move taking 7 stones. Alice then loses since she is forced to take stones from an empty pile.
{9, 9}
{3, 7}
Returns: 4
Alice can win by taking either 3 or 7 from either pile.
{1}
{10}
Returns: 1
{89, 98, 85, 82, 94, 96, 91, 71, 69, 76, 78, 80, 9}
{1, 8, 31, 38, 39}
Returns: 5
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FollowingNim with a public method int countWinningMoves(vector<int> piles, vector<int> special) · 136 test cases · 2 s / 256 MB per case