YetAnotherNim
TCO12 Semifinal 1 · 2012-03-27 · by crazyb0y
Problem Statement
Alice and Bob are playing a famous game called Nim. In this game, they first set up n piles of stones. The piles are labeled 1 through n. For each i, the number of stones on the i-th pile is between 1 and m, inclusive. Once the piles are set up, Alice and Bob alternate in taking turns. In their turn, each player chooses one of the piles and removes some stones from the pile (at least one, possibly all of them). The game ends when all piles are empty. The player unable to make a valid move loses. (In other words, the player who removed the very last stone wins.)
Since Alice and Bob are both brilliant, they soon learned how to play Nim and both started playing it optimally. Nowadays, they don't even need to play the game. They simply look at the initial setup of piles and compute who will win the game. It is no surprise that this gets a bit boring after some time.
Therefore they came up with an improved version of the game. The new version looks as follows:
- They both agree on the values n, m (with meanings as mentioned above), and k (explained below). For convenience, m+1 will always be a power of 2.
- Alice picks the sizes of the n piles.
- Bob selects exactly k consecutive piles and throws the remaining piles away. That is, for some i, Bob selects the piles i through i+k-1.
- Alice may remove some of the piles. (She is allowed to remove as many as she wants, but not all of them. She is allowed to remove no piles. The piles she removes do not have to be consecutive.)
- With the remaining piles Bob and Alice play a game of Nim. In this game, Bob takes the first turn.
Alice wants to win the game.
Clearly, the key to winning the game is picking a good sequence of pile sizes in the second step of the above description.
You are given the
Notes
- Two sequences of pile sizes are considered different if there is some i such that the number of stones on the i-th pile differs. For example, the sequences (2,5,7) and (2,7,5) are considered different.
Constraints
- n will be between 1 and 1,000,000,000 (10^9), inclusive.
- m will be between 1 and 1,000,000,000 (10^9), inclusive.
- m + 1 will be a power of 2.
- k will be between 1 and n, inclusive.
100 1 30 Returns: 1
There is only one valid setup: 100 piles with one stone each. In step 3, Bob will select exactly 30 of these piles. (It does not matter which 30, as they all look the same.) In step 4, Alice will remove 28 of them, leaving Bob with two piles, each with one stone. In the game of Nim, Bob takes one of the stones, Alice the other one, and she wins. Hence there is one setup such that Alice wins the game.
100 15 1 Returns: 0
Regardless of what Alice does in step 2, after step 3 there will only be one pile of stones. Nothing will happen in step 4, as Alice has to leave at least one pile of stones. In the game of Nim, Bob will simply take all the stones from that pile and win the game. So there are no setups such that Alice wins.
100 15 2 Returns: 15
In step 3, Bob will pick two of the 100 piles. Alice cannot throw anything away in step 4, because if she does, only one pile will remain and Bob easily wins the game of Nim. So the game of Nim will be played with the two piles Bob selected. Bob wins the game of Nim if and only if the piles have different sizes. So in order to win the game, Alice has to make sure that Bob picks two equal piles in step 3. The only way to force this is by choosing the same size for each of the 100 piles in step 2. As the maximal pile size is 15, there are exactly 15 winning setups.
1 1 1 Returns: 0
100 31 10 Returns: 908629681
Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class YetAnotherNim with a public method int solve(int n, int m, int k) · 106 test cases · 2 s / 256 MB per case