TinyChessboardNim
SRM 793 · 2020-11-03 · by misof
Problem Statement
Tiny Chessboard Nim is a two-player game played on a tiny 2x2 chessboard.
A position in this game consists of some number of grains of rice placed on each cell of the chessboard.
A valid move in this game consists of:
- choosing either one row or one column of the chessboard
- choosing a positive integer x
- removing exactly x grains of rice from each cell in the chosen row/column
Standard termination rule applies: whoever cannot make a valid move, loses the game.
You are given a position: the
+---+---+ | a | b | +---+---+ | c | d | +---+---+
Return the number of winning moves in the given position.
Constraints
- rice will contain exactly 4 elements.
- Each element of rice will be between 0 and 1,000,000, inclusive.
{4, 7, 7, 4}
Returns: 0
This is a losing position. The second player can use the symmetry to make sure they always have a valid move. E.g., if the first player chooses one row, the second player will choose the other row and the same x as the first player used.
{0, 42, 47, 0}
Returns: 0
Even though there is still some rice on the chessboard, this game is already over.
{1, 2, 3, 4}
Returns: 2
The two winning moves are: select the second row and x = 3, producing the state {1, 2, 0, 1} select the first column and x = 1, producing the state {0, 2, 2, 4} given after after position: move #1: move #2: +---+---+ +---+---+ +---+---+ | 1 | 2 | | 1 | 2 | | 0 | 2 | +---+---+ +---+---+ +---+---+ | 3 | 4 | | 0 | 1 | | 2 | 4 | +---+---+ +---+---+ +---+---+
{2, 0, 3, 4}
Returns: 1
{3, 4, 2, 2}
Returns: 3
Submissions are judged against all 215 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TinyChessboardNim with a public method int countWinningMoves(vector<int> rice) · 215 test cases · 2 s / 256 MB per case