TopCoder problem "LongLongNim" used in SRM 330 (Division I Level Three)

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 int[], and you are also given an int maxN. Return the number of different values of n between 1 and maxN, inclusive, that make the game possible to win for the second player (assuming both players play optimally).



Parameters:int, int[]
Method signature:int numberOfWins(int maxN, int[] moves)
(be sure your method is public)


-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).


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.
Returns: 499
The second player wins when n is even and loses when n is odd.
Returns: 333333333
Similarly to example 0, the second player only wins when n is a multiple of 3.
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.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , misof

Problem categories:

Math, Search