DivNim
SRM 845 · 2023-03-02 · by misof
Problem Statement
DivNim is a version of the NIM game.
This version is played with a whiteboard. At any moment during the game there is a collection of (not necessarily distinct) positive integers written on the board. Two players take alternating turns. In each turn, the current player chooses one number (let's call it X), erases it and in its place writes a proper divisor of X. The game ends when there are no more moves left.
For example, if the board has the numbers { 1, 12, 27, 12 }, the current player can either erase one of the 12s and then write 1, 2, 3, 4, or 6 instead of it, or they can erase the 27 and replace it with 1, 3, or 9.
DivNim can be played in two ways: in normal play the player who's unable to make a move loses, and in misere play that player wins the game.
You are going to play a game of DivNim against Shawn, the local DivNim champion who always plays optimally.
You already made the agreement that all starting numbers will be between lo and hi, inclusive.
Some such numbers are already on the whiteboard; these are given in the
Before the game starts you have to add exactly one additional number N to the whiteboard. (The number you add must be within the allowed range. It can be a duplicate of a number already on the board.) Then, Shawn will be the one to take the first turn of the game.
For each mode of play, count the number of ways in which you can choose N so that you can win the game (if you play optimally). Return a
Constraints
- lo will be between 1 and 10^12, inclusive.
- hi will be between lo and 10^12, inclusive.
- hi - lo will not exceed 10^5.
- board will contain between 0 and 50 elements, inclusive.
- Each element of board will be between lo and hi, inclusive.
1
12
{}
Returns: {1, 5 }
The board is empty, so you will be playing only with the number N you'll add to the board. If you are playing with the normal rule, you can only win if you choose N = 1 (in which case Shawn immediately has no valid move and loses). In all other scenarios Shawn erases your N, writes down 1 instead, and then you lose. If you are playing with the misere rule, you should choose one of the available primes (2, 3, 5, 7, or 11) as your N. If you choose N = 1, Shawn wins immediately, and in all other scenarios Shawn can make sure that he wins after your first move.
12
12
{12, 12, 12, 12, 12}
Returns: {1, 1 }
You must add a sixth 12 to the board. This creates a symmetric position, and in both modes of play you can use that symmetry to your advantage and defeat Shawn.
10
30
{12, 16, 29, 24, 28}
Returns: {6, 6 }
1
12
{1, 1, 1}
Returns: {1, 5 }
As you cannot do anything with a 1 written on the whiteboard, this example is essentially the same as Example #0.
1
30
{4, 8}
Returns: {10, 10 }
xor = 1 but items aren't small only
1
30
{4, 7, 8}
Returns: {1, 1 }
xor = 0 but items aren't small only
Submissions are judged against all 113 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DivNim with a public method vector<int> solve(long long lo, long long hi, vector<long long> board) · 113 test cases · 2 s / 256 MB per case