LongLongNim
SRM 330 · 2006-12-13 · by soul-net
Problem Statement
LongLongNim is a game played by two players who alternate turns. n coins are arranged in a pack. A valid move consists of removing exactly X coins from the pack, where X is an element of the set moves. If a player cannot perform a valid move during his turn, he loses the game, and the other player, of course, wins.
You are given the set moves as a
Constraints
- maxN will be between 1 and 1000000000 (109), inclusive.
- moves will contain between 1 and 22 elements, inclusive.
- Each element of moves will be between 1 and 22, inclusive.
- moves will be sorted in strictly increasing order (i.e., no duplicates).
20
{1,2,3}
Returns: 5
If n is a multiple of 4, the second player can win by simply removing 4-L coins each time, where L is the number of coins the first player removed on his last turn. If n is not a multiple of four, the first player can always choose to remove the remainder of dividing n by 4, thereby leaving a multiple of 4 and the second player in. After that, he just uses the strategy described at the beginning to win. Altogether, the second player only wins if n is a multiple of 4, and there are 5 multiples of 4 between 1 and 20.
999
{1}
Returns: 499
The second player wins when n is even and loses when n is odd.
1000000000
{1,2}
Returns: 333333333
Similarly to example 0, the second player only wins when n is a multiple of 3.
6543
{2,4,7,11,20}
Returns: 1637
Any player who is left with 0 or 1 coin loses because the least number of coins that can be removed is 2.
1
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22}
Returns: 1
Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LongLongNim with a public method int numberOfWins(int maxN, vector<int> moves) · 99 test cases · 2 s / 256 MB per case