#P2594. Coin Flipping Game
Coin Flipping Game
Coin Flipping Game
There is an n × m grid of coins. Two players, Dongdong and Xixi, play the following game. On each turn, a player may choose a connected block of coins and flip all coins in that block. However, the move is only valid if there exists a coin in the chosen block (called the pivot) such that:
- Every other coin in the block is located in the upper‐left direction of this coin (that is, either directly above or directly to its left, or both),
- This coin is flipped from tail (back side) to head (front side).
Two players take turns making moves, with Dongdong moving first. A player who is unable to make a valid move loses. Assuming both players play optimally, determine whether Dongdong has a winning strategy.
Observation: Note that a valid move always involves flipping at least one coin that is currently tail (the pivot coin) to head. A trivial move is to select a single coin that is tail; in this move the coin is flipped to head. More generally, any connected block chosen must lie entirely in a sub‐matrix whose bottom‐right coin (the pivot) is tail before the move, and all other coins in that block lie in its upper-left region.
This game is impartial, and its outcome can be determined by computing the nim‐sum over all coins – where the coin at position \((i,j)\) (with 0‐based indices) is assigned a Grundy value of \(i \oplus j\). Dongdong can force a win if and only if the overall nim‐sum over every coin that is initially tail is nonzero.
Important: The initial configuration of coins is such that all coins are tails. Thus, the nim‐sum is defined as
[ G = \bigoplus_{i=0}^{n-1}\bigoplus_{j=0}^{m-1} (i \oplus j), ]
Dongdong wins if \(G \neq 0\), and loses otherwise.
inputFormat
The first line contains two integers n
and m
--- the dimensions of the coin grid.
It is guaranteed that the grid contains exactly n × m
coins, and initially all coins are tails.
outputFormat
Output a single string: Yes
if Dongdong has a winning strategy, or No
otherwise.
sample
1 1
No