FollowingNim | Topcoder Archive

Problem Statement

Alice and Bob are playing a game of Nim. There are n piles of stones, described by the int[] piles. The i-th pile initially contains piles[i] stones.

There is one modification that Alice and Bob will make to the rules of nim, based on the int[] special. If a move removes exactly special[j] stones from a pile for some j, then the next person must make a move in the same pile. The first person unable to make a move loses (due being unable to make a move in any pile, or unable to make a move in the same pile from the special rule).

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.

Definition

Class:: FollowingNim
Method:: countWinningMoves
Parameters:: int[], int[]
Returns:: int
Method signature:: int countWinningMoves(int[] piles, int[] special)
(be sure your method is public)

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.

Examples

```
{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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.